UNTITLED - Untitled Problem

no tags 

We consider a sequence S1 is equal to a sequence S2, if and only if they satisfy the following conditions:

  • The length of them are equal.
  • Let Len be the length of them. For each i, j (1 <= i, j <= Len, i != j):If S1[i] is smaller than S1[j], S2[i] must be smaller than S2[j]; If S1[i] is greater than S1[j], S2[i] must greater than S2[j].

Now you are given a sequence S and another N sequences T1, T2 …. TN.

We say position i is OK, if and only if S [1..i] contains a suffix which is equal to a sequence from { T1, T2 ... TN }. You need to print the positions which is OK in increasing order.

Input

Multiple test cases, the number of them(no more than 3) is given in the very first line.

For each test case:

  • The first line contains an integer M (M > 1) which denote the number of sequences. i.e. M = N + 1.
  • M * 2 lines follow, each two lines describe one sequence. For each two lines, the first line contains an integer L which denote the length of this sequence. The second line contains L integers (all the integers don't exceed 231-1) that represent this sequence. The first sequence described is S, the next N sequences represent T1 ... TN.
  • You can assume that there are no same integer in any one sequence.
  • The length of S is no more than 400000, and the total length of T is no more than 100000.

Output

For each test case: Print the positions which is OK in increasing order.

Example

Input:
2
2
1
1
1
2
3
3
3 1 2
2
4 5
2
10 1

Output:
1
2
3

hide comments
Siarhei Kulik: 2012-11-28 14:12:08

got best time with nsqrtnlogn lol...


Added by:Qu Jun
Date:2008-05-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Based on a problem from USACO 2005 Dec Gold Division