statement.md

椅子取りゲーム

Problem Statement

N人の子供たちが椅子取りゲームをしている。ここでは便宜上、子供たちに0からN-1までの番号を振ることにする。 椅子も最初N席あり、これが円環状に並んでいる。これにも(子供の番号とは別に)0からN-1までの番号を振ることにする。

子供たちは最初に自分の番号に対応する椅子の前に立っている。この椅子の中からいくつかを取り除き、音楽を鳴らす。 音楽が鳴っている間、子供たちは1秒毎に番号が1少ない椅子の前へと移動していく。椅子は円環状に並んでいるので、0番の椅子の前にいた子供はN-1番の椅子の前に移動する。 音楽が止まったとき、子供たちは自分の前にある椅子に座ろうとする。もし椅子が取り除かれていれば、その子供は椅子に座ることができない。

T秒後に音楽を止め、椅子取りをしたとき、椅子に座ることができない子供は誰になるか求めよ。

Input

入力は以下の形式で表される。

D
N₁ T₁
M₁
C₁₁ C₁₂ ... C_1M1
N₂ T₂
M₂
C₂₁ C₂₂ ... C_2M2
:
N_D T_D
M_D
C_D1 C_D2 ... C_DMD

ここでDは椅子取りゲームの回数である。また、i回目のゲームにおいて、N_iは参加する子供の人数、T_iは音楽を止める時間、M_iは取り除かれる椅子の数、C_ijはj番目に取り除かれる椅子の番号である。

Constraints

入力は、以下の条件をすべて満たす。

• 1 <= D <= 100
• 1 <= i <= Dを満たすすべての整数iについて、
  • 2 <= N_i <= 100
  • 1 <= T_i <= 1000
  • 1 <= M_i <= N-1
  • さらに 1 <= j <= M_iを満たすすべての整数jについて、
    • 0 <= C_ij <= N-1

Output

出力は、各ゲームごとに椅子に座ることができない子供の番号を 数字の小さい順に 半角スペース区切りで1行に全て出力せよ。

Sample Input

2
3 10
1
0
20 45
2
3 5

Sample Output

1
8 10

• 1回目のゲームでは、椅子取りゲームを開始するときに0番の椅子が取り除かれ、取り除かれた椅子の前にいる子供は1秒ごとに0→1→2→0...と変化していく。10秒後にそこにいる1番の子供が答えとなる。