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}$$$。
示例
输入复制
331 6 26 2 42 4 31122 33 4
输出复制
5 1 6 2 4 3 2 1 1 2 3 4