2507 - untitled

    考虑一个序列S1与另一个序列S2,如果满足下列条件,则两个序列等价:

1、 两个序列长度相等。 2、 设序列长度为len,对于任意的i,j(1<=i,j<=Len,i!=j),若s1[i]<s1[j],则s2[i]<s2[j];若s1[i]>s1[j],则s2[i]>s2[j]。 现给出序列S和另外n个序列T1,T2,…Tn。 位置i可行,当且仅当S[1..i]的某个后缀等价于T1…Tn中的某个序列。你需要输出所有可行i的值,按照升序输出。

Input

     数据有若干组,第一行一个数Test,表示数据组数。
     以下有Test组数据。
     对于每组数据,第一行一个整数m,表示序列的个数,其中,第一个序列表示序列S,以下m-1个序列表示T1,T2,…,Tn(m=n+1)。对于每个序列,第一行一个数表示其长度Len,第二行Len个数,表示这个序列。
     每组数据用一个空行隔开。

Output

     对于每组数据,按升序输出可行的i值,一行一个数。
 每组数据之间不要加入多余空行。

Examples

Input

2
2
1
1
1
2

3
3
3 1 2
2
4 5
2
10 1

Output

1
2
3

Hint

数据范围:

     S的长度小于400000,m>1,T的总长度小于100000。
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题