A. Хүлэг баатруудын тэмцээн

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

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

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

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

Берландын хаан II Берл хүлэг баатруудынхаа дунд тэмцээн зохиохоор болжээ. Хаан бүх ноёддоо мэдэгдсэн бөгөөд ноёд ч хариуд нь зөвшөөрч буйгаа илэрхийлжээ.

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

-$n$ ширхэг баатар тэмцээнд оролцож байгаа ба баатар бүр $1-n$ тоонуудаар ялгаатайгаар дугаарлагдсан. -Тэмцээн $m$ ширхэг тулаанаас бүрдэнэ: $i$ дэх тулаанд $l_i$-с багагүй $r_i$-с ихгүй дугаартай бөгөөд тэмцээнээс хасагдаагүй байгаа бүх баатрууд оролцож $x_i$ дугаартай баатар л ялж энэ тулалдаанд орсон баатруудаас ганцаар тэмцээнээс хасагдалгүй үлдэнэ. -Хамгийн сүүлийн буюу $m$ дэх тулааны ялагч нь тэмцээний ялагч болно.

Найз тань танд тэмцээний талаарх мэдээллүүдийг дуулгасан бөгөөд та баатар бүр ямар баатарт ялагдсаныг мэдэхийг хүсч байгаа. $a,b$ баатрууд нэгэн тулаанд зэрэг ороод $a$ баатар энэ тулааны ялагч болсон бол бид $a$ нь $b$-г ялсан гэж үзнэ.

Баатар бүр ямар баатарт ялагдсаныг тооцоолох код бич.

Оролт

Эхний мөрөнд $n, m (2\le n\le 3·10^5; 1\le m\le 3·10^5)$ тоонууд өгөгдөх ба эдгээр нь харгалзан тэмцээнд оролцсон баатруудын тоо ба нийт баатруудын тоо юм. Дараагийн $m$ мөр бүрт тухайн тулааныг тодорхойлох $l_i,r_i,x_i (1\le l_i

Оролт нь зөв ба бодлогын өгүүлбэртэй зайлшгүй нийцнэ. Мөн тулаан бүрт багадаа 2 баатар оролцсон.

Гаралт

Дараах байдлаар нэг мөрөнд $n$ ширхэг бүхэл тоог хэвлэ: $i$ дэх тоо нь $i$ дэх баатрыг ялсан баатрын дугаар байх ба $i$ баатар тэмцээний ялагч бол $i$ дэх тоо $0$ байна.

Орчуулсан: Төрбат

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

Оролт
4 3
1 2 1
1 3 3
1 4 4
Гаралт
3 1 4 0 
Оролт
8 4
3 5 4
3 7 6
2 8 8
1 8 1
Гаралт
0 8 4 6 4 8 6 1 

Тэмдэглэл

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.

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