Зарим шоргоолжнуудыг төмөр сараалжийн зангилаан дээр тавиад ажиглахад нэг дор $4$-өөс олон шоргоолж байвал $4$-өөрөө нэг бүлэг болж байгаад бүлэг бүр зангилаа болох ($x,y$) цэгээс тарж хөрш ($x+1,y$), ($x-1,y$), ($x,y+1$), ($x,y-1$) зангилаа руу $1$ $1$-ээрээ явдаг байв. Мөн шоргоолжнууд хэзээ ч нэг нэгнийхээ хөдөлгөөнд саад болдоггүй байлаа.

Эрдэмтэд яг ийм төрлийн $n$ ширхэг шоргоолжийг ($0,0$) зангилаа дээр тавиад хэрхэн тарахыг нь ажиглав. Тодорхой хугацааны дараа цэг бүр дээр $4$-өөс цөөхөн шоргоолж үлдэх үед бүх шоргоолж хөдөлгөөнгүй болж байв.

Тийм бол ингэж хөдөлгөөнгүй болсон үед цэг бүр дээр хэдэн шоргоолж байгааг мэдээлнэ үү.

Оролт

Эхний мөрөнд шоргоолжны тоо $n$ ба ($0 ≤ n ≤ 30000$) асуултын тоо $t$ ($1 ≤ t ≤ 50000$) тоонууд өгөгдөнө.

Дараагийн $t$ мөрөнд мөр бүрд нүдний байрлалыг илэрхийлэх $x_i$, $y_i$ ($-10^9 ≤ xi, yi ≤ 10^9$) тоо өгөгдөнө.

Асуултууд давхцаж болох ба шоргоолжнууд хөдөлгөөнгүй болох мөч заавал олдоно.

Гаралт

$t$ ширхэг мөрөнд мөр бүрт $1$ бүхэл тоо.

In the first sample the colony consists of the one ant, so nothing happens at all.

In the second sample the colony consists of 6 ants. At the first minute 4 ants scatter from (0, 0) to the neighbouring junctions. After that the process stops.