E - ブレスレット Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

アイドルグループである Bit♡Beat のライブでは、 N 人のメンバーそれぞれのブレスレットが周期的に光りますが、メンバーごとに少しずつスタートがずれた状態から始まります。具体的には、 i 人目のメンバーのブレスレットはライブ開始から A_i 秒後に光り、そこから B_i 秒ごとに光ります。

N 人全員のブレスレットが同時に光ることがあるか判定してください。

より厳密には、ライブ開始から x 秒後に全員のブレスレットが光るような非負整数 x が存在するか判定してください。

制約

  • 2\le N\le 2\times 10^5
  • 0\le A_i < B_i \le 10^6
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

N 人全員のブレスレットが同時に光ることがあるならば Yes を、ないならば No を出力せよ。

入力例 1

3
1 3
1 12
3 5

出力例 1

Yes

ライブ開始から 13 秒後に全員のブレスレットが同時に光ります。したがって、 Yes を出力してください。

入力例 2

2
0 6
5 6

出力例 2

No

全員のブレスレットが同時に光ることはありません。したがって、No を出力してください。

入力例 3

10
23192 199879
152914 434323
486127 642530
867889 926999
362331 897721
75620 913403
100107 117031
22740 516557
260622 642909
419828 739597

出力例 3

Yes

ライブ開始から 382791477 秒後に全員のブレスレットが同時に光ります。