题目描述

Brr Brrr Patapim 想猜出 Tiramisù 的秘密口令。这个口令是一个长度为 $2n$ 的排列 $p$。

Tiramisù 给了他一个 $n\times n$ 的网格 $G$，其中 $G_{i,j}=p_{i+j}$。保证存在这样的排列，并且可以唯一确定。

请还原整个排列 $p_1,p_2,\ldots,p_{2n}$。

排列指由 $1$ 到 $m$ 的整数各出现一次组成的序列。

输入格式

第一行包含整数 $t$，表示测试组数。

每组测试数据第一行包含整数 $n$。接下来 $n$ 行，每行包含 $n$ 个整数，表示网格 $G$。

输出格式

对于每组测试数据，输出 $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

数据范围

• $1 \le t \le 200$
• $1 \le n \le 800$
• $1 \le G_{i,j} \le 2n$
• 所有测试组的 $n$ 之和不超过 $800$

来源

Codeforces Round 1017 (Div. 4), Problem C - Brr Brrr Patapim