Mô tả và yêu cầu

Một phú ông giàu có tại một vùng nọ, một hôm cảm thấy chán nản vì ko có gì
để chơi, liền nghĩ ra một trò vô cùng hấp dẫn. Phú ông thuê n chiến binh đánh số họ
từ 1…n. Sau đó phú ông cho các chiến binh chiến đấu với nhau trong m cuộc chiến,
trong mỗi cuộc chiến phú ông sẽ chọn ra các chiến binh có chỉ số từ l đến r và cho
họ chiến đấu với nhau, người thua sẽ bị loại ra. Chiến binh cuối cùng sót lại sau cuộc
chiến sẽ là chiến binh thắng tất cả các chiến binh trong cu ộc chiến đó, đương nhiên
một chiến binh đã b ị loại trong một cuộc chiến thì không thể tham gia các cuộc chiến
sau đó nữa.
Cho n chiến binh và m cuộc chiến, hãy xác định chiến binh thứ i thua chiến binh
nào.

Dữ liệu vào

• Dòng đầu tiên chứa n và m (2≤n≤3×10^5, 1≤m≤3×10^5)
• m dòng tiếp theo mỗi dòng chứa li, ri và xi mô tả cuộc chiến thứ i, các chiến binh
được chọn có chỉ số từ li đến ri và chiến binh xi là chiến binh thắng cuộc trong cuộc
chiến đó.

Dữ liệu ra

 Gồm một dòng duy nhất chứa n số xi với xi là chiến binh thắng chiến
binh i, xi = 0 nếu chiến binh i chưa chết sau m cuộc chiến.

Ví dụ

INPUT                 OUTPUT
                             8 4                    0 8 4 6 4 8 6 1
                             3 5 4
                             3 7 6
                             2 8 8
                             1 8 1