题目描述

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$ 个整数组成的排列是指一个包含 $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}$。

说明/提示

翻译由 DeepSeek V3 完成

样例

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