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

Заданы $$$n$$$ перестановок $$$a_1, a_2, \dots, a_n$$$, каждая длины $$$m$$$. Напомним, что перестановка длины $$$m$$$ — это последовательность из $$$m$$$ различных целых чисел от $$$1$$$ до $$$m$$$.

Назовем красотой перестановки $$$p_1, p_2, \dots, p_m$$$ наибольшее такое $$$k$$$, что $$$p_1 = 1, p_2 = 2, \dots, p_k = k$$$. Если $$$p_1 \neq 1$$$, то красота равна $$$0$$$.

Произведение двух перестановок $$$p \cdot q$$$ — это такая перестановка $$$r$$$, что $$$r_j = q_{p_j}$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ выведите наибольшую красоту перестановки $$$a_i \cdot a_j$$$ по всем $$$j$$$ от $$$1$$$ до $$$n$$$ (возможно, $$$i = j$$$).

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5 \cdot 10^4$$$; $$$1 \le m \le 10$$$) — количество перестановок и длина каждой перестановки.

В $$$i$$$-й из следующих $$$n$$$ строк записана перестановка $$$a_i$$$ — $$$m$$$ различных чисел от $$$1$$$ до $$$m$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^4$$$.

Выходные данные

На каждый набор входных данных выведите $$$n$$$ целых чисел. $$$i$$$-е значение должно быть равно наибольшей красоте перестановки $$$a_i \cdot a_j$$$ по всем $$$j$$$ ($$$1 \le j \le n$$$).

Пример
Входные данные
3
3 4
2 4 1 3
1 2 4 3
2 1 3 4
2 2
1 2
2 1
8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2
Выходные данные
1 4 4 
2 2 
10 8 1 6 8 10 1 7