Rating 900

2137B 有趣的数列

来源：CodeForces Round 1047 (Div. 3)-B. Fun Permutation

Tags: 构造算法 数学 数论

给定一个大小为 $n$ 的排列$^{\text{∗}}$ $p$。

你的任务是找到一个大小为 $n$ 的排列 $q$,使得对于所有 $1 \leq i<n$,满足 $\operatorname{GCD}$ $^{\text{†}}$ $(p_i+q_i, p_{i+1}+q_{i+1}) \geq 3$。换句话说,任意相邻两个位置的和的最大公约数至少为 $3$。

可以证明这总是可行的。

$^{\text{∗}}$ 一个长度为 $m$ 的排列是指一个由 $1$ 到 $m$ 的 $m$ 个不同整数按任意顺序组成的数组。例如,$[2,3,1,5,4]$ 是一个排列,但 $[1,2,2]$ 不是排列($2$ 在数组中出现两次),$[1,3,4]$ 也不是排列($m=3$ 但数组中出现了 $4$)。

$^{\text{†}}$ $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数 (GCD)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2\cdot 10^5$)。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ ($1 \leq p_i \leq n$)。

保证给定的数组构成一个排列。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$。

输出

对于每个测试用例,在新的一行输出排列 $q$。如果有多个可能的答案,输出任意一个即可。

测试用例

输入

3
3
1 3 2
5
5 1 2 4 3
7
6 7 1 5 4 3 2

输出

2 3 1
4 5 1 2 3
2 1 3 7 5 6 4

注意

在第一个测试用例中,$\operatorname{GCD}(1+2,3+3)=3\geq 3$ 且 $\operatorname{GCD}(3+3,2+1)=3\geq3$,因此输出是正确的。

2136B 类似位集的问题

来源：Codeforces Round 1046 (Div. 2)-B. Like the Bitset

Tags: 构造算法 贪心 双指针

给定一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$ 和一个整数 $k$。

Aquawave 想要构造一个长度为 $n$ 的排列$^{\text{†}}$ $p$,使得对于每个满足 $s_i=\mathtt{1}$ 的 $1\le i\le n$,以下条件成立:

• 对于每个长度至少为 $k$(即 $r - l + 1 \geq k$)且覆盖位置 $i$(即 $l \leq i \leq r$)的区间 $[l, r]$ ($1\le l\le r\le n$),$p_l, p_{l+1}, \ldots, p_r$ 中的最大值 不能 是 $p_i$。

注意:对于 $s_i = \mathtt{0}$ 的索引 没有 此类约束。

你需要找到这样的一个排列,或者确定这样的排列不存在。

$^{\text{∗}}$ 二进制字符串是指每个字符只能是 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^{\text{†}}$ 长度为 $n$ 的排列是指一个由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序组成的数组。例如,$[2,3,1,5,4]$ 是一个排列,但 $[1,2,2]$ 不是排列($2$ 在数组中出现两次),$[1,3,4]$ 也不是排列($n=3$ 但数组中出现了 $4$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq n$) —— 分别是 $s$ 的长度和语句中的整数。

第二行包含长度为 $n$ 的二进制字符串 $s$ ($s_i = \mathtt{0}$ 或 $\mathtt{1}$)。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例:

• 如果至少存在一个可能的排列:
  • 在第一行输出 "YES";
  • 在第二行输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$,所有 $p_i$ 互不相同) —— 你构造的排列。
• 否则,在单行输出 "NO"。

你可以以任意大小写形式输出标记。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定响应。

如果有多个答案,你可以输出其中任意一个。

测试用例

输入

6
2 1
00
4 3
0010
5 2
11011
7 5
1111110
8 4
00101011
10 2
1000000010

输出

YES
1 2
YES
1 4 3 2
NO
NO
YES
6 5 2 3 4 8 1 7
YES
1 2 3 4 5 6 7 9 8 10

注意

在第一个测试用例中,你可以输出任意一个长度为 $n = 2$ 的排列,因为所有的 $s_i$ 都等于 $\mathtt{0}$。

在第二个测试用例中,$p=[1, 4, 3, 2]$ 是一个有效的答案,因为:

• 唯一满足 $s_i = \tt{1}$ 的位置是 $i = 3$。存在三个不同的覆盖索引 $3$ 且长度至少为 $k=3$ 的区间 $[l, r]$:$[1, 3]$、$[1, 4]$ 和 $[2, 4]$;
• 并且,对于这三个区间中的每一个,$p_l, \ldots, p_r$ 中的最大值应该是 $p_2 = 4$,它不等于 $p_3 = 3$。

2114B 不完全回文字符串

来源：Codeforces Round 1027 (Div. 3)-B. Not Quite a Palindromic String

Tags: 贪心 数学

Vlad 找到了一个长度为偶数 $n$ 的二进制字符串$^{\text{∗}}$ $s$。他认为一对索引 ($i, n - i + 1$)(其中 $1 \le i < n - i + 1$)是好的,当且仅当 $s_i = s_{n - i + 1}$ 成立。

例如,在字符串 '010001' 中只有 $1$ 对好的索引对,因为 $s_1 \ne s_6$,$s_2 \ne s_5$,而 $s_3 = s_4$。在字符串 '0101' 中没有好的索引对。

Vlad 喜欢回文串,但又不那么喜欢,所以他想要重新排列字符串中的一些字符,使得恰好有 $k$ 对好的索引对。

判断是否可以通过重新排列给定字符串中的字符,使得恰好有 $k$ 对好的索引 ($i, n - i + 1$)。

$^{\text{∗}}$如果一个字符串 $s$ 仅由字符 '0' 和 '1' 组成,则称其为二进制字符串。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 2 \cdot 10^5$, $0 \le k \le \frac{n}{2}$ , $n$ 为偶数) —— 分别是字符串的长度和所需的好索引对的数量。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例,如果存在一种重新排列字符串字符的方法使得恰好有 $k$ 对好的索引对,则输出 "YES",否则输出 "NO"。

你可以以任何大小写形式输出每个字母(小写或大写)。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被接受为肯定答案。

测试用例

输入

6
6 2
000000
2 1
01
4 1
1011
10 2
1101011001
10 1
1101011001
2 1
11

输出

NO
NO
YES
NO
YES
YES

2106B 上色圣徒(St. Chroma)

来源：Codeforces Round 1020 (Div. 3)-B. St. Chroma

Tags: 构造算法 贪心 数学

给定一个包含从 $0$ 到 $n-1$ 所有整数的排列$^{\text{∗}}$ $p$ 和一条有 $n$ 个单元格的带子,St. Chroma 会将带子的第 $i$ 个单元格涂上颜色 $\operatorname{MEX}(p_1, p_2, ..., p_i)$ $^{\text{†}}$。

例如,假设 $p = [1, 0, 3, 2]$。那么,St. Chroma 将按以下方式为带子的单元格上色:$[0, 2, 2, 4]$。

你被给定两个整数 $n$ 和 $x$。因为 St. Chroma 喜欢颜色 $x$,请构造一个排列 $p$,使得带子中被涂上颜色 $x$ 的单元格数量最大化。

$^{\text{∗}}$ 长度为 $n$ 的排列是一个包含 $0$ 到 $n-1$ 所有整数恰好一次的序列。例如,$[0, 3, 1, 2]$ 是一个排列,但 $[1, 2, 0, 1]$ 不是,因为 $1$ 出现了两次,且 $[1, 3, 2]$ 也不是,因为 $0$ 根本没有出现。

$^{\text{†}}$ 序列的 $\operatorname{MEX}$ 定义为该序列中未出现的最小非负整数。例如,$\operatorname{MEX}(1, 3, 0, 2) = 4$,而 $\operatorname{MEX}(3, 1, 2) = 0$。

输入

输入的第一行包含一个整数 $t$ ($1 \le t \le 4000$) —— 测试用例的数量。

每个测试用例的唯一一行包含两个整数 $n$ 和 $x$ ($1 \le n \le 2 \cdot 10^5$, $0 \le x \le n$) —— 分别是单元格的数量和你想要最大化的颜色。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

输出一个长度为 $n$ 的排列 $p$,使得带子中被涂上颜色 $x$ 的单元格数量最大化。如果存在多个这样的排列,输出其中任意一个。

测试用例

输入

7
4 2
4 0
5 0
1 1
3 3
1 0
4 3

输出

1 0 3 2
2 3 1 0
3 2 4 1 0
0
0 2 1
0
1 2 0 3

注意

第一个例子在题目描述中已作解释。可以证明 $2$ 是可以被涂上颜色 $2$ 的单元格的最大数量。注意,另一个正确答案可能是排列 $[0, 1, 3, 2]$。

在第二个例子中,该排列给出的着色为 $[0, 0, 0, 4]$,因此有 $3$ 个单元格被涂上颜色 $0$,可以证明这是最大值。

2102A 晚餐时间

来源：Codeforces Round 1024 (Div. 2)-A. Dinner Time

Tags: 构造算法 数学

给定四个整数 $n$, $m$, $p$ 和 $q$,判断是否存在一个整数数组 $a_1, a_2, \ldots, a_n$(元素可以为负数)满足以下条件:

• 数组中所有元素的和等于 $m$:

  $$a_1 + a_2 + \ldots + a_n = m$$

• 每个连续的 $p$ 个元素的和等于 $q$:

  $$a_i + a_{i + 1} + \ldots + a_{i + p - 1} = q,\qquad\text{ 对所有 }1\le i\le n-p+1$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行也是唯一一行包含四个整数 $n$, $m$, $p$ 和 $q$ ($1 \le p \le n \le 100$, $1 \le q, m \le 100$) —— 分别是数组的长度、元素总和、段的长度和段的总和。

输出

对于每个测试用例,如果存在满足上述条件的数组,则输出 "YES"(不带引号),否则输出 "NO"(不带引号)。

你可以以任意大小写形式输出 "YES" 和 "NO"(例如,字符串 "yES"、"yes" 和 "Yes" 都将被视为有效响应)。

注意

在第一个测试用例中,满足条件的数组示例是 $[1, 0, 1]$。这是因为:

• $a_1+a_2+a_3 = 1+0+1 = 2 = m$
• $a_1+a_2=1+0=1=q$
• $a_2+a_3=0+1=1=q$

在第二个测试用例中,唯一满足条件的数组是 $[1]$。

在第三个测试用例中,满足条件的数组示例是 $[-2, 5, -2, 5, -2]$。

在第四个测试用例中,可以证明不存在满足条件的数组。

Rating 1000

2144B 最大成本排列

来源：Educational Codeforces Round 182 (Rated for Div. 2)-B. Maximum Cost Permutation

Tags: 构造算法 贪心

回忆一下,长度为 $n$ 的排列是指一个长度为 $n$ 的序列,其中从 $1$ 到 $n$ 的每个整数恰好出现一次。

我们定义一个排列的成本为:需要排序的连续子段(可能为空)的最小长度,使得整个排列按升序排序。

给定一个由 $0$ 到 $n$ 的整数组成的数组 $p$,其中没有正数(严格大于零的整数)出现超过一次。你需要用整数替换零,使得数组 $p$ 成为一个排列。

你的任务是计算最终排列可能的最大成本。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le n$)。该序列中没有正数出现超过一次。

输入附加约束:所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例,输出一个整数 —— 最终排列可能的最大成本。

测试用例

输入

4
5
1 0 4 0 5
3
0 0 0
4
1 2 3 0
3
0 3 2

输出

3
3
0
2

注意

在第一个例子中,你可以构造排列 $[1, 3, 4, 2, 5]$,其成本为 $3$,因为你需要排序子段 $[2, 4]$。

在第二个例子中,你可以构造排列 $[2, 3, 1]$,其成本为 $3$,因为你需要排序子段 $[1, 3]$。

在第三个例子中,只有一种可能的排列 $[1, 2, 3, 4]$,其成本为 $0$,因为该排列已经是有序的。

在第四个例子中,只有一种可能的排列 $[1, 3, 2]$,其成本为 $2$,因为你需要排序子段 $[2, 3]$。

2143B 折扣优惠

来源：Codeforces Round 1051 (Div. 2)-B. Discounts

Tags: 贪心 排序 双指针

你想要购买 $n$ 件价格分别为 $a_1, a_2, \ldots, a_n$ 的商品。你可以选择以下两种方式之一:

• 单独购买商品 $i$,支付 $a_i$ 枚硬币,或者
• 使用折扣券将其作为团购的一部分购买。

你拥有 $k$ 张折扣券,面值分别为 $b_1, b_2, \ldots, b_k$。一张面值为 $x$ 的折扣券允许你选择恰好 $x$ 件商品,并且只需支付其中 $x - 1$ 件最贵的商品,也就是说,该组中最便宜的商品是免费的。每件商品最多只能包含在一个折扣组中,即使它不是免费的那件。此外,任何单张折扣券最多只能使用一次。

购买所有 $n$ 件商品所需的最低总成本是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

第一行包含两个整数 $n$ 和 $k$ ($1 \le n, k \le 2 \cdot 10^5$) —— 分别是商品的数量和可用的折扣券数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) —— 商品的价格。

第三行包含 $k$ 个整数 $b_1, b_2, \ldots, b_k$ ($1 \le b_i \le n$) —— 折扣券的面值。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$,且所有测试用例的 $k$ 的总和不超过 $2 \cdot 10^5$。

输出

输出 $t$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案 —— 即该测试用例中购买所有商品所需的最低总成本。

测试用例

输入

5
5 3
18 3 7 2 9
3 1 1
6 1
1 2 6 3 3 4
5
2 3
1 1
2 2 2
1 1
10
1
5 3
99 99 999 999 123
2 1 4

输出

10
17
1
0
1197

注意

在第一个测试用例中,你可以将第一张折扣券应用于商品 2、3 和 4。你将支付其中最贵的两件(3 和 7 枚硬币)并获得最便宜的一件免费,成本为 $3 + 7 = 10$ 枚硬币。然后,将第二张和第三张折扣券应用于商品 1 和 5,两者都免费获得。总成本为 $10$ 枚硬币。

在第二个测试用例中,你可以将单张折扣券用于商品 2、3、4、5 和 6。其中,最便宜的是商品 2(价格为 2 枚硬币),你可以免费获得。你支付剩余的商品:$1 + 6 + 3 + 3 + 4 = 17$ 枚硬币,总计。

在第三个测试用例中,只有一张折扣券可用。你可以将其用于两件商品,免费获得较便宜的那件,并为另一件支付 $1$ 枚硬币。

2132C1 狡猾的卖家(简单版)

来源：Codeforces Round 1043 (Div. 3)-C1. The Cunning Seller (easy version)

Tags: 贪心 数学

这是问题的简单版本。简单版本与困难版本的不同之处在于,它要求在最少交易次数下确定最低成本,而困难版本要求在有限交易次数下确定最低成本。

狡猾的卖家在一次卖出三个西瓜而不是一个之后,决定增加他的利润——也就是说,他购入了更多的西瓜。现在他可以以 $3^{x+1} + x \cdot 3^{x-1}$ 枚硬币的价格卖出 $3^x$ 个西瓜,其中 $x$ 是一个非负整数。这样的一次销售被称为一笔交易。

一位精打细算的买家来到他这里,但他的时间非常紧迫。因此,他想恰好购买 $n$ 个西瓜,并达成最少可能的交易次数。

买家很匆忙,因此求助于你,以确定他必须支付给卖家购买 $n$ 个西瓜所需的最少硬币数,前提是他将达成最少可能的交易次数。

输入

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的一行中,有一个整数 $n$ $(1 \le n \le 10^9)$ —— 需要购买的西瓜数量。

输出

对于每个测试用例,输出一个整数 —— 购买西瓜的最低成本。

测试用例

输入

7
1
3
8
2
10
20
260010000

输出

3
10
26
6
36
72
2250964728

注意

注意,购买超过所需的西瓜是没有意义的,所以我们不会考虑那些提供多于所需西瓜的交易。

让我们考虑前两种交易选项的成本:

交易 A: $1$ 个西瓜 —— $3$ 枚硬币。

交易 B: $3$ 个西瓜 —— $10$ 枚硬币。

在第一个样例中,购买 $1$ 个西瓜的唯一方法是使用交易 A,所以答案是 $3$。

在第二个样例中,你可以通过单次交易 B 购买 $3$ 个西瓜,花费 $10$ 枚硬币。

在第三个样例中,你可以进行 $2$ 次交易 A 和 $2$ 次交易 B,总成本为 $26$ 枚硬币。如果我们进行 $3$ 次交易,我们可以得到 $3$、$5$、$7$ 或 $9$ 个西瓜。如果我们进行的交易少于 $3$ 次,我们得到的西瓜不会超过 $6$ 个,这意味着不可能用少于 $4$ 次交易来购买 $8$ 个西瓜。

2092B 瓢虫女士

来源：Codeforces Round 1014 (Div. 2)-B. Lady Bug

Tags: 暴力破解 构造算法 实现 数学

就在Dasha Purova越过法国边境时,反派Markaron绑架了她,并将她关押在他巨大城堡下的一个监狱里。幸运的是,了不起的瓢虫女士一听到关于Dasha的消息,立刻跑向Markaron的城堡去营救她。然而,要到达那里,她需要破解一个复杂的密码。

密码由两个比特字符串 $a$ 和 $b$ 组成,每个字符串的长度为 $n$。在一次操作中,瓢虫女士可以选择任意索引 $2 \le i \le n$ 并执行以下操作之一:

1. 交换($a_i$, $b_{i-1}$)(交换 $a_i$ 和 $b_{i-1}$ 的值),或者
2. 交换($b_i$, $a_{i-1}$)(交换 $b_i$ 和 $a_{i-1}$ 的值)。

瓢虫女士可以执行任意次数的操作。如果她能够确保第一个字符串 $a$ 只包含零,则认为密码被破解。请帮助她判断是否能够拯救不幸的Dasha。

输入

每个测试包含多个测试用例。输入数据的第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2 \cdot 10^5$) —— 密码比特字符串的长度。

接下来两行包含长度为 $n$ 的比特字符串 $a$ 和 $b$,它们代表密码。每个字符串仅包含字符 '0' 和 '1'。

保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例,如果瓢虫女士在任意次数的操作后能够破解密码,则输出 "YES";否则,输出 "NO"。

你可以以任意大小写形式输出每个字母(小写或大写)。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被接受为肯定答案。

测试用例

输入

4
3
000
000
6
010001
010111
5
10000
01010
2
11
00

输出

YES
YES
NO
YES

注意

在第一个测试用例中,字符串 $a$ 本身就只包含零。

在第二个测试用例中,一个可能的操作序列是:

1. 交换$(a_2, \ b_{1})$

   $\mathtt{0{\color{red}{1}}0001}$

   $\mathtt{{\color{red}{0}}10111}$

2. 交换$(b_5, \ a_{4})$

   $\mathtt{000{\color{red}{0}}01}$

   $\mathtt{1101{\color{red}{1}}1}$

3. 交换$(a_4, \ b_{3})$

   $\mathtt{000{\color{red}{1}}01}$

   $\mathtt{11{\color{red}{0}}101}$

4. 交换$(a_5, \ b_{4})$

   $\mathtt{00000{\color{red}{1}}}$

   $\mathtt{1111{\color{red}{0}}1}$

2060B 农夫约翰的卡牌游戏

来源：Codeforces Round 998 (Div. 3)-B. Farmer John's Card Game

Tags: 贪心 排序

农夫约翰的 $n$ 头奶牛正在玩一个卡牌游戏！农夫约翰有一副包含 $n \cdot m$ 张卡牌的牌堆，卡牌编号从 $0$ 到 $n \cdot m-1$。他给他的 $n$ 头奶牛每头分发 $m$ 张牌。

农夫约翰希望游戏是公平的，所以每头奶牛在每一轮中只能打出 $1$ 张牌。他决定确定一个出牌顺序，该顺序由一个长度为 $n$ 的排列$^{\text{∗}}$ $p$ 决定，使得第 $p_i$ 头奶牛将成为第 $i$ 个将一张牌放置到中央牌堆顶部的奶牛。

换句话说，每一轮中以下事件按顺序发生：

• 第 $p_1$ 头奶牛从其手牌中任选一张牌放置到中央牌堆顶部。
• 第 $p_2$ 头奶牛从其手牌中任选一张牌放置到中央牌堆顶部。
• ...
• 第 $p_n$ 头奶牛从其手牌中任选一张牌放置到中央牌堆顶部。

但有一个限制。最初，中央牌堆包含一张编号为 $-1$ 的卡牌。为了放置一张卡牌，该卡牌的编号必须大于中央牌堆顶部卡牌的编号。然后，新放置的卡牌成为中央牌堆的顶部卡牌。如果一头奶牛无法从其手牌中打出任何卡牌，则游戏被视为失败。

农夫约翰想知道：是否存在一个排列 $p$，使得在玩完所有 $m$ 轮游戏后，他的所有奶牛都有可能清空她们的手牌？如果存在，输出任意一个有效的 $p$。否则，输出 $-1$。

$^{\text{∗}}$ 一个长度为 $n$ 的排列包含从 $1$ 到 $n$ 的每个整数恰好一次。

输入

第一行包含一个整数 $t$ ($1 \leq t \leq 400$) —— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n \cdot m \leq 2\,000$) —— 奶牛的数量和每头奶牛收到的卡牌数量。

接下来的 $n$ 行，每行包含 $m$ 个整数 —— 每头奶牛收到的卡牌。保证所有给出的数字（跨越所有 $n$ 行）都是不同的，并且在 $0$ 到 $n \cdot m - 1$ 的范围内（包括端点）。

保证所有测试用例的 $n \cdot m$ 的总和不超过 $2\,000$。

输出

对于每个测试用例，在新的一行输出：

• 如果 $p$ 存在，输出 $n$ 个以空格分隔的整数 $p_1, p_2, \ldots, p_n$。
• 否则，输出 $-1$。

测试用例

输入

4
2 3
0 4 2
1 5 3
1 1
0
2 2
1 2
0 3
4 1
1
2
0
3

输出

1 2
1
-1
3 1 2 4

注意

在第一个测试用例中，一种允许打出所有卡牌的出牌顺序是让第一头奶牛在第二头奶牛之前出牌。打出的卡牌顺序将是 $0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$。

在第二个测试用例中，只有一头奶牛，因此让该奶牛按递增顺序打出她所有的卡牌将会清空手牌。

在第三个测试用例中，可以证明不存在允许打出所有卡牌的有效出牌顺序。