Decode All

2 secs 1024 MB
hide's icon hide
Tweet
問題
提出
テストケース
解説

問題文

ミクさんは疑似乱数生成手法の11つである線形合同法に着想をえて,以下のような整数変換暗号を考えた.

00以上の自然数xxは以下により暗号後の整数E(x)E(x)へと変換される.

・暗号化には22つの00以上の整数の固定されたペア=key(a,b)=key(a, b)を用いる.

・E(x)=(a⊕x)−b・E(x) = (a \oplus x) - b

ミクさんは秘密裏に作成した暗号key(a,b)key(a, b)に基づき,NN個の暗号データ(xi,yi)(x_i, y_i)を作成した.

なお,(xi,yi)(x_i, y_i)はそれぞれii個目に用いられた平文xx,暗号化後の文E(x)E(x)を表すものとする.

しかし,後にミクさんは暗号化の途中でデータの記録を誤った可能性があることに気がついた.

さて,NN個の暗号化データを完全に再現するkeykeyが存在するか判定せよ.

制約

・1≤N≤1000001 \le N \le 100000

・全ての(xi,yi)(x_i, y_i)について以下が成り立つ.

・0≤xi,yi≤10180 \le x_i, y_i \le 10 ^ {18}

入力

入力は以下の形式で与えられる.

n
x_1 y_1
...
x_n y_n

出力

与えられた暗号を完全に再現する22つの00以上の整数のペアkey=(a,b)key=(a, b)が存在する場合,YESと11行に出力せよ.

データに誤りがあり,与えられた暗号を完全に再現するkeykeyが存在しない場合,NOと11行に出力せよ.

サンプル

入力1
4
326 204
311 317
253 119
151 157
出力1
YES

暗号化に用いられたと考えうるkeykeyの11例として,(a,b)=(78,60)(a, b) = (78, 60)がある.

入力2
5
467 506
831 982
623 868
712 1251
857 884
出力2
NO

この場合,データに誤りがあり,暗号keykeyは存在しない.

入力3
10
316238659101155907 645229132805311485
614695967254137802 292741814780945796
81465790441210746 988185134638820564
636206482332723754 307251294187930532
686348272422600465 365275074915096751
19562978609682594 923890399887684124
469663112021574638 726000639528742240
28734570745545446 932742000047451224
140972113578833785 964619673208742103
492102380635833317 739607777324559707
出力3
YES

暗号化に用いられたと考えうるkeykeyの11例として,(a,b)=(3213267742554228790,2305843163383389816)(a, b) = (3213267742554228790, 2305843163383389816)がある.

入力4
11
451537263676468998 332954437761876502
525673960312500525 408008265211769853
499685243562174727 307921464855968791
266442455897875302 112750506376971702
384815832914534157 265104976905720349
350377164260985777 159525776026050185
632372260046207332 712599240620446796
331586352355379714 178175875135233818
313323170231724340 196994822537329668
271810186936181928 80890626850130304
163990564903638853 44075541558499797
出力4
NO

提出

Go (1.21)