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.

Input

• 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 đó.

Output

• 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.

Sample Input

8 4 
3 5 4 
3 7 6 
2 8 8 
1 8 1

Sample Output

0 8 4 6 4 8 6 1