Бяцхан Максим сонирхолтой бодлогуудад дуртай. Тэрээр тантай нэгэн ийм бодлогыг хуваалцахаар шийджээ.

Анхандаа $a$ цуваа байх ба цуваа нь $n$ ширхэг 0-ээс тогтоно. Цувааны элементүүд нь индекслэгдсэн ба 1-ээс эхэлсэн байна. Дараа нь асуултуудыг даган $a$ цувааг өөрчлөх юм. Асуулт бүр нь 2 бүхэл тоо $v_{i}, t_{i}$-аар дүрслэгдэнэ. Асуултын хариултад бид цувааны $v_{i}$-дахь элементийг $t_{i}$-тэй тэнцүү болгоно $(a_{v_{i}} = t_{i}; 1 ≤ v_{i} ≤ n)$.

Максим бүхэл тоонуудын хэсэг хос $(x, y)$ нь сайн бөгөөд зарим хэсэг нь тийм биш гэж боддог. Максим $n$ ширхэг бүхэл тоонуудаас тогтох $a$ цувааг хэрэв бүх бүхэл тоо $i$, $(1 ≤ i ≤ n - 1)$-ын хувьд бүхэл тоонуудын хос $(a_{i}, a_{i + 1})$ нь сайн байвал азтай гэж боддог. Хосууд доторх тоонуудын дараалал чухал болохыг анхаарна уу, өөрөөр хэлбэл ялангуяа $(1, 2) ≠ (2, 1)$ байх юм.

$a$ цувааг өөрчлөх асуулт бүрийн дараа Максим үр дүнгийн цуваа нь (0-үүд байхгүй) азтай байхаар $a$ цувааны бүх 0-ийг 1-ээс 3 хүртэлх бүхэл тоонуудаар солих хэчнээн арга байгааг мэдэхийг хүсжээ. Мэдээж хэрэг, ялгаатай 0-үүд нь ялгаатай бүхэл тоонуудаар солигдож болно.

Максим танд асуултуудын дараалал болон өөрийнхөө сайн гэж бодож байгаа бүх бүхэл тоон хосуудаа хэлнэ. Максим-д тусалж, уг бодлогыг түүнд бодож өгнө үү.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$ болон $m$ $(1 ≤ n, m ≤ 77777)$ өгөгдөнө -- эдгээр нь цувааны элементийн тоо болон үйлдлийн тоог илэрхийлнэ.

Дараагийн 3-н мөрөнд $w$ матриц өгөгдөнө, энэ нь зөвхөн 0-үүд болон 1-үүдээс тогтоно; эдгээрийн $i$-дэх мөрийн $j$-дахь тоо нь $w_{i, j}$ байна. Хэрэв $w_{i, j} = 1$ $(1 ≤ i, j ≤ 3)$ байвал, $(i, j)$ хос нь сайн байна, бусад тохиолдолд энэ нь сайн биш байх юм. Матриц нь үндсэн диагональтайгаа харьцангуй тэгш хэмтэй байх албагүй.

Дараагийн $m$ мөрөнд бүхэл тоонуудын хосууд $v_{i}, t_{i}$ $(1 ≤ v_{i} ≤ n, 0 ≤ t_{i} ≤ 3)$ өгөгдөнө -- эдгээр нь цувааг өөрчлөх асуултуудыг илэрхийлнэ.

Гаралт

$m$ ширхэг бүхэл тоо хэвлэнэ -- эдгээрийн $i$-дахь тоо нь үр дүнгийн цуваа нь (0-үүд байхгүй) азтай байхаар $a$ ($i$-дахь асуултаар солигдсоны дараах) цувааны бүх 0-ийг 1-ээс 3 хүртэлх бүхэл тоонуудаар солих аргын тоотой тэнцүү байна. Тоонуудыг цагаан зайгаар тусгаарлана уу. Хариултууд нь маш том байж болох учраас, тэдгээрийг $777777777$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.