Петя болон Жена ширээний теннис тоглох дуртай. Нэг тоглолт нь дараах дүрмийн дагуу явагдана: нэг тоглолт хэд хэдэн сэтээс бүрдэх ба сэт бүр хэд хэдэн давуулалтаас бүрдэнэ. Нэг давуулалтад тоглогчдын аль нэг нь хожих ба тэр тоглогч нэг оноо авна. Тоглогчдын аль нэг нь $t$ оноотой болмогц тэр тоглогч сэт-д хожих ба дараагийн сэт эхэлж хоёр тоглогчийн оноо 0 болно. Аль нэг тоглогч нийт $s$ сэтд хожвол тэр тоглогч тоглолтонд хожиж тоглолт дуусна. Энд $s$ ба $t$ нь эерэг бүхэл тоонууд.

Илүү сонирхолтой болгохын тулд тоглолт бүрийн өмнө Петя Жена хоёр шинэ $s$ ба $t$ тоонууд сонгоно. Үүнээс гадна түүхийн төлөө тэд тоглолт бүрийн бичлэгийг хадгалах буюу давуулалт бүрд ялагчийг бичиж авна. Давуулалтын ялагчид цаг хугацааны дараалалтайгаар тэмдэглэгдэнэ. Тэмдэглэлд аль нэг тоглогч нь $t$ оноотой болмогц сэт дуусах ба аль нэг тоглогч $s$ сэтд хожмогц тоглолт дуусна.

Петя Жена хоёр хуучин тоглолтын тэмдэглэл олсон. Харамсалтай нь тэмдэглэлд байгаа давуулалтын дараалал нь сэтүүдэд хуваагдаагүй ба уг тоглолтонд зориулсан $s$ ба $t$ тоонууд байхгүй байсан. Тоглогчид одоо $s$ ба $t$ тоонуудын утга хэд байх ёстой юм бол гэж гайхаж байна. Та боломжит бүх боломжуудыг тодорхойлж чадах уу?

Оролт

Эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ байх ба давуулалтуудын дарааллын урт ($1 ≤ n ≤ 10^{5}$).

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $a_{i}$ байна. Хэрвээ $a_{i} = 1$ байвал $i$-р давуулалтанд Петя хожсон гэсэн үг ба хэрвээ $a_{i} = 2$ байвал $i$-р давуулалтанд Жена хожсон гэсэн үг.

Өгөгдсөн тэмдэглэлд харгалзах $s$ ба $t$ тоонуудын боломж хамгийн багадаа нэг байх албагүй.

Гаралт

$s$ ба $t$ тоонуудын хувьд боломжуудын тоог илэрхийлэх нэг тоо $k$-г эхний мөрөнд хэвлэ.

Дараагийн $k$ мөр бүрт хоёр бүхэл тоон утга $s_{i}$ ба $t_{i}$ байх ба $s$ ба $t$ тоонуудын боломж. Боломжуудыг $s_{i}$-н өсөх дарааллаар хэвлэх ба тэнцүү $s_{i}$-тэй байвал $t_{i}$-н өсөх дарааллаар хэвлэ.