D. Шоргоолжнууд

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

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

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

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

Зарим шоргоолжнуудыг төмөр сараалжийн зангилаан дээр тавиад ажиглахад нэг дор $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$ бүхэл тоо.

Орчуулсан: gmunkhbaatarmn

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

Оролт
1 3
0 1
0 0
0 -1
Гаралт
0
1
0
Оролт
6 5
0 -2
0 -1
0 0
0 1
0 2
Гаралт
0
1
2
1
0

Тэмдэглэл

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.

Сэтгэгдлүүдийг ачааллаж байна...