Тэмцээний хоёр хагас шигшээ явагдаж байна. Хагас шигшээ бүрд $n$ оролцогч байгаа. Эцсийн шалгаруултанд $n$ хүн үлдэх ба дараах байдлаар сонгогдоно. Хагас шигшээ бүрээс хамгийн өндөр үзүүлэлттэй $k (0 ≤ 2k ≤ n)$ хүнийг сонгож үлдсэн хүмүүсээс хамгийн өндөр үзүүлэлттэй $n - 2k$ хүнийг сонгоно.

Тэмцээний зохион байгуулагчид одоогоор $k$-ийн утгыг шийдээгүй байгаа. Тиймээс оролцогчид хэнд нь эцсийн шатанд оролцох боломж байгааг мэдэхийг хүсчээ.

Оролт

Эхний мөрөнд хагас шигшээ бүрд оролцож байгаа оролцогчийн тоо $n (1 ≤ n ≤ 10^5)$. Дараагийн $n$ мөрөнд $a_i,\ b_i (1 ≤ a_i, b_i ≤ 10^9)$ (хагас шигшээг дуусгасан миллсекунт) бүхэл тоонууд байна. Энэ нь шигшээ бүрийн $i$-р оролцогчийн эхний ба 2-р хагас шигшээний дүн өгөгдөнө. Бүх дүн ялгаатай байна. $a_1$, $a_2$,..., $a_n$ ба $b_1$, $b_2$,..., $b_n$ дараалал өсөх эрэмбээр өгөгдөнө.

Гаралт

$0,\ 1$-ээс бүрдсэн $n$ урттай 2 тэмдэгт мөр хэвдэнэ. Эхний мөрөнд эхний хагас шигшээний оролцогчдыг, дараагийн мөрөнд 2-р хагас шигшээний оролцогчдыг илтгэнэ. $i$-р мөрийн $j$-дэх тэмдэгт нь $1$ бол $i$-р хагас шигшээн $j$-дэх оролцогч шалгарах боломжиой гэсэн үг. Үгүй бол $0$ байна.

Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090.

• If $k = 0$, the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals.
• If $k = 1$, the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds).
• If $k = 2$, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.