Hooray!  Agent Bauer has shot the terrorists, blown upthe bad guy base, saved the hostages, exposed the moles in the government,prevented an environmental catastrophe, and found homes for three orphanedkittens, all in the span of 19 consecutive hours.  But now, he only has 5 hours remaining todeal with his final challenge: an activated nuclear bomb protected by asecurity code.  Can you help him figureout the code and deactivate it?  Eventsoccur in real time.

The governmenthackers at CTU (Counter-Terrorist Unit) have learned some things about thecode, but they still haven't quite solved it.They know it's a single, strictly positive, integer.  They also know several clues of the form "whendivided by X, the remainder is one of {Y1, Y2, Y3, …,Yk}".There are multiple solutions to these clues, but the code is likely tobe one of the smallest ones.  So they'dlike you to print out the first few solutions, in increasing order.

The world iscounting on you!

Input

Input consistsof several test cases.  Each test casestarts with a line containing C, the number of clues (1 <= C <= 9), andS, the number of desired solutions (1 <= S <= 10).  The next C lines each start with two integersX (2 <= X) and k (1 <= k <= 100), followed by the k distinct integersY1, Y2, …, Yk (0 <= Y1,Y2, …, Yk < X).

You may assumethat the Xs in each test case are pairwise relativelyprime (ie, they have no common factor except 1).  Also, the product of the Xs will fit into a32-bit integer.

The last testcase is followed by a line containing two zeros.

Output

For each testcase, output S lines containing the S smallest positive solutions to the clues,in increasing order.

Print a blankline after the output for each test case.

Sample Input

Sample Output

 

3 2

2 1 1

5 2 0 3

3 2 1 2

0 0

5

13

 

思路：中国剩余定理+暴力；

首先我们肯定会想到dfs暴力枚举，这种情况只有当所有k的乘积很小的情况下才行，这个时候我们采取dfs+中国剩余定理；当k的乘积很大的情况下，

考虑选择一个Ｋ/Ｘ最小的条件，然后枚举所有符合这个条件的数ｎ，即　tX+Yi　，t=0,1,2….　然后依次判断这个ｎ是否符合其它所有条件，因为这个时候x的增量很大。

1 #include
2 #include
3 #include
4 #include
5 #include