← 返回题目列表

Codeforces · 1792/D

D. 固定前缀排列

中文机器翻译题面 查看原题

您将获得 $$$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