题目描述

给定 $n$ 个序列，第 $i$ 个序列 $a_i$ 长度为 $l_i$，用 $[a_{i,1},a_{i,2},\cdots ,a_{i,l_i}]$ 来表示，元素均是 $[1,m]$ 中的互不相同的正整数。

每个时刻，所有序列都会向左循环移位一个位置，即，对于第 $i$ 个序列，如果它目前是 $[a_{i,1},a_{i,2},\cdots,a_{i,l_i}]$，其下一个时刻将会变为 $[a_{i,2},a_{i,3},\cdots,a_{i,l_i},a_{i,1}]$。

对于一个元素 $x$，其在时刻 $t$ 的权值 $f(x,t)$ 记为第 $t$ 时刻时，$x$ 在 $[a_{1,1},a_{2,1},\cdots, a_{n,1}]$ 这个序列中的最长连续出现次数。例如，$1$ 在 $[1,1,4,5,1,4]$ 中的最长连续出现次数是 $2$。

你需要对每一个 $1\leq x\leq m$ 求出 $\max_{t=1}^{100^{100^{100}}} f(x,t)$ 的值。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行先是一个整数 $l_i$，然后是 $l_i$ 个整数 $a_{i,1},\cdots,a_{i,l_i}$。

输出格式

对于每组数据：

一行 $m$ 个整数，第 $i$ 个整数表示 $x=i$ 时的答案。

输入样例

3
3 4
3 3 4 1
4 1 3 4 2
3 3 1 4
5 5
2 3 1
4 5 1 3 2
4 2 1 3 5
1 3
2 5 3
4 6
3 4 5 3
2 6 3
2 3 6
3 3 6 5

输出样例

2 1 3 2
3 1 4 0 1
0 0 2 1 1 2

说明提示

输入样例 #2

1
1 1
1 1

输出样例 #2

1 

输入样例 #3

1
2 3
1 1
2 1 2

输出样例 #3

2 1 0 

数据范围

对于 $30\%$ 的数据，$1\leq T,n,m,l_i\leq 5$。

对于另外 $10\%$ 的数据，$n=2$。

对于另外 $20\%$ 的数据，$l_i\leq 2$。

对于另外 $10\%$ 的数据，$l_i\leq 5$。

对于 $100\%$ 的数据，$1\leq T,\sum n,\sum m\leq 10^5$，$1\leq l_i\leq 40$，$\sum l_i\leq 2\times 10^5$，$1\leq a_{i,j}\leq m$。