您将获得 $$$n$$$ 排列 $$$a_1, a_2, \dots, a_n$$$,每个排列的长度为 $$$m$$$。回想一下,长度 $$$m$$$ 的排列是从 $$$1$$$ 到 $$$m$$$ 的 $$$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}$$$。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,打印从 $$$1$$$ 到 $$$n$$$ 的所有 $$$j$$$ 的排列 $$$a_i \cdot a_j$$$ 的最大美度(可能 $$$i = j$$$)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5 \cdot 10^4$$$; $$$1 \le m \le 10$$$) - 排列的数量和每个排列的长度。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含排列 $$$a_i$$$ — $$$m$$$ 从 $$$1$$$ 到 $$$m$$$ 的不同整数。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^4$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数。第 $$$i$$$ 值应等于所有 $$$j$$$ 上的排列 $$$a_i \cdot a_j$$$ 的最大美度 ($$$1 \le j \le n$$$)。
示例
输入 #1
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
1 4 4 2 2 10 8 1 6 8 10 1 7