問題文

初め整数 XX を持っていたあなたは、上司から 1111 回ずつ、NN 日にわたって NN 回の命令を受けました。

ii 日目の命令では、正整数 aia_ibib_i を与えられ、その時点で持っている整数 xxaix+bia_i x+b_i で置き換えました。

あなたは NN 回の命令に与えられた順に従った後に、持っている整数を 109+710^9+7 で割った余りを結果として記録しました。

しかし、kk 日目がエイプリルフールだったため、上司が aka_kbkb_k の値を入れ替えて命令をしていたことが判明しました。

入力で与えられる aia_ibib_i は入れ替えられた後の値です。

aka_kbkb_k を入れ替えなかった場合の結果は YY になることが分かっています。kk としてあり得る値をすべて出力してください。ただし、NN 日のうちエイプリルフールは 11 日しかありません。

kk としてあり得る値が少なくとも 11 つあることは保証されます。

制約

  • 1N1051\leq N \leq 10^5
  • 0X1090 \leq X\leq 10^9
  • 0Y<109+70 \leq Y < 10^9 + 7
  • 1ai1091\leq a_i\leq 10^9
  • 1bi1091\leq b_i\leq 10^9

入力

入力はすべて整数である。

N X YN\ X\ Y
a1 b1a_1\ b_1
a2 b2a_2\ b_2
\vdots
aN bNa_N\ b_N

出力

何日目がエイプリルフールだったか、あり得る日を昇順で改行区切りで出力してください。

サンプル

入力1
3 10 834
5 5
5 2
3 3
出力2
1
3
入力2
13 864378500 920284871
4 15
10 3
9 16
4 9
10 5
7 14
17 18
13 18
16 1
17 2
17 11
1 1
5 19
出力2
9

Submit


Go (1.21)