← 返回题目列表

Codeforces · 2094/C

C. Brr Brrr 帕塔皮姆

中文机器翻译题面 查看原题

Brr Brrr Patapim 正在尝试了解提拉米苏的秘密密码,该密码是 $$$2\cdot n$$$ 元素的排列$$$^{\text{*}}$$$。为了帮助 Patapim 猜测,Tiramisù 给了他一个 $$$n\times n$$$ 网格 $$$G$$$,其中 $$$G_{i,j}$$$(或网格的第 $$$i$$$ 行和 $$$j$$$ 列中的元素)包含 $$$p_{i+j}$$$,或排列中的第 $$$(i+j)$$$ 个元素。

给定这个网格,请帮助Patapim破解被遗忘的代码。保证排列存在,并且可以证明排列可以唯一确定。

$$$^{\text{*}}$$$$$$m$$$ 整数的排列是 $$$m$$$ 整数的序列,其中每个 $$$1,2,\ldots,m$$$ 恰好包含一次。例如,$$$[1, 3, 2]$$$ 和 $$$[2, 1]$$$ 是排列,而 $$$[1, 2, 4]$$$ 和 $$$[1, 3, 2, 3]$$$ 不是排列。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 800$$$)。

以下 $$$n$$$ 行均包含 $$$n$$$ 整数,给出网格 $$$G$$$。第一行包含 $$$G_{1,1}, G_{1,2},\ldots,G_{1,n}$$$;其中第二行包含 $$$G_{2,1}、G_{2,2},\ldots,G_{2,n}$$$ 等。 ($$$1 \leq G_{i,j} \leq 2\cdot n$$$).

保证网格编码有效的排列,并且所有测试用例的 $$$n$$$ 总和不超过 $$$800$$$。

输出

对于每个测试用例,请在新行中输出 $$$2n$$$ 数字:$$$p_1,p_2,\ldots,p_{2n}$$$。

示例

输入
复制

3
3
1 6 2
6 2 4
2 4 3
1
1
2
2 3
3 4

输出
复制

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