E. Бэрстэй холбоотой өөр нэгэн бодлого

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

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

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

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

Бэрс бол шатрын нэгэн хүчирхэг хэсэг билээ. Орчин үеийн шатарт бэрс нь хэвтээ, босоо эсвэл диагоналийн дагуу чиглэлд хэдэн ч тооны нүдээр нүүж болдог (бэрсний замд нь өөр ямар нэгэн зүйл байрлаагүй байна гэж үзнэ). Өөрөөр хэлбэл бэрсний нүүдэл нь тэрэг болон тэмээний нүүдлүүдийг нэгтгэсэн байх юм.

$n × n$ хэмжээ бүхий шатрын хөлөг дээр $m$ ширхэг бэрс байрлаж байв. Та эдгээр бэрс болгоны байрлалыг мэдэж байгаа бөгөөд $i$-р бэрс нь $(r_{i}, c_{i})$ нүдэн дээр байрлаж байгаа байв, энд $r_{i}$ нь хөлгийн мөрийн дугаарыг (мөрнүүд нь дээрээсээ доош хүртэл 1-ээс $n$ хүртэл дугаарлагдсан байна), $c_{i}$ нь хөлгийн баганын дугаарыг (баганууд нь зүүнээсээ баруун хүртэл 1-ээс $n$ хүртэл дугаарлагдсан байна) илэрхийлнэ. Аль ч 2 бэрс нь ижил нүдэн дээр байрлаагүй байна.

Бэрс бүрийн хувьд та уг бэрс нь хэдэн ширхэг бусад бэрсний хөл дээр байрлаж байгааг илэрхийлэх $w$ тоог мэдэж болох юм. Ямар нэгэн бэрсний хөл дээр хэрэв олон бэрс байрлаж байвал уг бэрс нь эдгээр бэрсний зөвхөн хамгийн эхний бэрсийг л идэж чадна. Мэдээж хэрэг ямар ч бэрсний хувьд $w$-ын утга нь 0-ээс 8 хүртэл утга авах юм.

Та $t_{0}, t_{1}, ..., t_{8}$ гэсэн дарааллыг хэвлэх ёстой бөгөөд энд $t_{i}$ нь яг $i$ ширхэг бусад бэрсний хөл дээр оршиж байгаа бэрсний тоог илэрхийлнэ, өөрөөр хэлбэл эдгээр бэрсний $w$ нь $i$-тай тэнцүү байна.

Оролт

Эхний мөрөнд хос бүхэл тоо $n, m$ ($1 ≤ n, m ≤ 10^{5}$) өгөгдөх ба энд $n$ нь хөлгийн хэмжээг илэрхийлэх ба $m$ нь хөлөг дээр байгаа бэрсний тоог илэрхийлнэ. Дараагийн $m$ мөрөнд бэрснүүдийн байрлал өгөгдөх ба тус бүр нь нэг мөрөнд өгөгдөнө. Мөр болгон нь хос бүхэл тоо $r_{i}, c_{i}$ ($1 ≤ r_{i}, c_{i} ≤ n$)-г агуулах ба эдгээр нь бэрсний байрлалыг илэрхийлэх юм. Ямар ч 2 бэрс нь ижил нүдэн дээр байрлаагүй байна.

Гаралт

Шаардагдсан дараалал $t_{0}, t_{1}, ..., t_{8}$-ыг хэвлэнэ үү. Дарааллын тоонуудыг зайгаар тусгаарлан хэвлэнэ.

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

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

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