A. Мөрийтэй тоглоом Ним

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Таны мэдэж байгаачлан "Ним" нэртэй тоглоомыг $n$ ширхэг чулуун овоогоор тоглодог ба тодруулбал $i$-дахь овоо нь анхандаа $a_{i}$ ширхэг чулуутай байдаг билээ. 2 тоглогч ээлжлэн нүүдэл хийх замаар уг тоглоомыг тоглоно. Нүүдэл хийх тоглогч өөрийн ээлж дээрээ хоосон биш нэгэн чулуун овоог сонгох ба уг овооноос дурын эерэг тооны чулуунуудыг авч хаях юм. Ингэж тоглоом үргэлжилсээр нүүдэл хийх боломжгүй болсон тоглогч ялагдана.

Петя болон Вася "Ним" тоглоомыг тоглосоор уйджээ. Тиймээс тэд уг тоглоомын шинэ хувилбар болох "Мөрийтэй тоглоом Ним"-ыг зохиожээ. Тэдэнд $n$ ширхэг 2 талтай хөзөр байх бөгөөд $i$-дахь хөзрийн нэг тал дээр нь $a_{i}$ нөгөө тал дээр нь $b_{i}$ гэсэн тоо бичигдсэн байна. Тоглоом эхлэхэд тоглогчид бүх хөзрүүдээ ширээн дээр тавина. Хөзөр болгон нь зөвхөн нэг талаараа дээшээ харсан байх бөгөөд уг дээш харсан талыг дурын байдлаар сонгосон байна. Тэд эдгээр дээш харсан талууд дээр бичигдсэн тоонуудыг нэгтгэн $c_{1}, c_{2}, ..., c_{n}$ гэсэн дараалалтай болох бөгөөд тодруулбал $c_{i}$ нь $a_{i}$ эсвэл $b_{i}$-тэй тэнцүү байна гэсэн үг юм. Дараа нь тэд $i$-дахь овоо нь яг $c_{i}$ ширхэг чулуу агуулсан байх $n$ ширхэг чулуун овоогоор "Ним" тоглоомыг тоглох ба Петя эхний үйлдлийг хийнэ.

2 тоглогч 2-уулаа ухаалаг тоглоно гэж үзээд Петя уг тоглоомд хожих магадлалыг олно уу. Хариултаа үл хураагдах бутархай хэлбэрээр хэвлэнэ үү.

Оролт

Эхний мөрөнд ширээн дээрх хөзрүүдийн тоо $n$ ($1 ≤ n ≤ 500 000$) бүхэл тоо өгөгдөнө.

Дараагийн $n$ мөрний мөр болгонд нэг хөзрийн талууд дээрх 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($0 ≤ a_{i}, b_{i} ≤ 10^{18}$) өгөгдөнө.

Гаралт

Хариултаа үл хураагдах бутархай $p / q$ хэлбэрээр хэвлэнэ. Хэрэв Петя-ын хожих магадлал $0$ байвал $0/1$ гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
1 1
1 1
Гаралт
0/1
Оролт
2
1 2
1 2
Гаралт
1/2
Оролт
3
0 4
1 5
2 3
Гаралт
1/1
Сэтгэгдлүүдийг ачааллаж байна...