C. Брр Бррр Патапим
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Брр Бррр Патапим пытается узнать секретный пароль Тирамису, который является перестановкой$$$^{\text{∗}}$$$ из $$$2\cdot n$$$ элементов. Чтобы помочь Патапиму угадать, Тирамису дал ему сетку $$$n\times n$$$ $$$G$$$, в которой $$$G_{i,j}$$$ (или элемент в $$$i$$$-й строке и $$$j$$$-м столбце сетки) содержит $$$p_{i+j}$$$, или $$$(i+j)$$$-й элемент перестановки.

Учитывая эту сетку, пожалуйста, помогите Патапиму разгадать забытый код. Гарантируется, что перестановка существует, и можно показать, что перестановка может быть определена однозначно.

$$$^{\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