C. Brr Brrr Patapim

时间限制： 2 秒
空间限制： 256 MB
输入： 标准输入
输出： 标准输出

Brr Brrr Patapim 试图得知 Tiramisù 的秘密密码，这是一个由 $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