B. Далбааны өдөр

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

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

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

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

Берланд улсын үндэсний баяр болох төрийн далбааны өдөр болох гэж байна. Энэ баярыг тохиолдуулан ерөнхийлөгч бүжгийн цэнгүүн зохиох гэж байгаа бөгөөд танай байгууллагыг зохион байгуулах ажлыг хийхийг хүсчээ. Тэр дараах нөхцлүүдийг тавьсан. Үүнд:

  • Яг $m$ бүжиг явагдах ёстой.
  • Бүжиг болгонд яг $3$ хүн оролцоно.
  • Бүжиг бүрт нэг цагаан, нэг улаан, нэг цэнхэр хувцастай хүн оролцох хэрэгтэй (Энэ нь Берландын тугны өнгө болно).

Танд нийт $n$ бүжигчин байгаа бөгөөд тэдгээрийн тоо нь $3m$-с бага байж болно. Иймд зарим нэг бүжигчин нэгээс олон удаа бүжиглэх хэрэгтэй юм. Мөн таны бүх бүжигчин цэнгүүнд оролцох ёстой гэнэ. Хэрвээ өмнөх бүжигт оролцсон $2$, эсвэл $3$ бүжигчин дараагийн бүжигт бүжиглэвэл хүмүүс уйддаг гэнэ. Та мэдээж ийм зүйл болохыг хүсэхгүй байгаа тул хамгийн өмнөх бүжигт орсон нэг бүжигчин дараагийнхад байхаар бүжигчдийн бүжиглэх дарааллыг гаргасан.

Та ингээд дээрх нөхцөлийг хангах $m$ бүжгийн гурвалыг сонгожээ. Одоо таны ажил бол ерөнхийлөгчийн хүслийг хангахаар буюу бүх бүжигт нэг цагаан, нэг улаан, нэг цэнхэр хувцастай бүжигчин байхаар тэдгээрийн хувцасыг сонгох юм. Бүжигчид бүжгийн дундуур хувцасаа сольж болохгүй.

Оролт

Эхинй мөрөнд бүжигчдийн тоо $n$ ($3 ≤ n ≤ 10^5$) ба бүжгийн тоо $m$ ($1 ≤ m ≤ 10^5$) өгөгдөнө. Дараагийн $m$ мөрөнд бүжиг бүрт оролцох бүжигчдийн дугаар байна. $i$-р мөрөнд $i$-р бүжгэнд гарах хоорондоо ялгаатай $3$ бүжигчний дугаар байрлах юм. Бүжигчид $1$-с $n$ хүртэл дугаарлагдсан болно. Бүх бүжигчид ядаж нэг удаа бүжиглэхээр өгөгдөнө.

Гаралт

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

Орчуулсан: zoloogg

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

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