Subtask 1 và 2 của bài này có đôi chút khác biệt về giới hạn của các biến. Các bạn lưu ý đọc kỹ đề. Với subtask 2, không có giới hạn gì thêm.

Nhiệm vụ của bạn là tìm một dãy ~a~ gồm ~n~ phần tử thỏa mãn ~m~ yêu cầu. Trong đó yêu cầu thứ ~i~ có dạng ~l_i~ ~r_i~ ~v_i~, nghĩa là:

• Giá trị của ~a_{l_i}~ ~\&~ ~a_{l_i+1}~ ~\&~ ... ~\&~ ~a_{r_i}~ là chính xác ~v_i~, với ~\&~ là phép toán thao tác bit AND.

Dữ liệu vào

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, m~ ~(1 \le n, m \le 10^5)~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số ~l_i~ ~r_i~ ~v_i~ ~(1 \le l_i \le r_i \le n; 0 \le v_i < 2^{30})~.

Dữ liệu ra

• In ra dãy ~a~ thỏa mãn với ~0 \le a_i < 2^{30}~. Nếu có nhiều kết quả, hãy in ra kết quả bất kỳ.
• Dữ liệu đầu vào đảm bảo luôn tồn tại kết quả.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

5 1 5 3 2 7 6 7

Giải thích

Với dãy ~a = [5, 1, 5, 3, 2, 7, 6, 7]~, ta có:

• Yêu cầu ~l = 1, r = 1~: ~a_1~ ~=~ ~5~.
• Yêu cầu ~l = 2, r = 4~: ~a_2~ ~\&~ ~a_3~ ~\&~ ~a_4~ ~=~ ~1~ ~\&~ ~5~ ~\&~ ~3~ ~=~ ~1~.
• Yêu cầu ~l = 6, r = 8~: ~a_6~ ~\&~ ~a_7~ ~\&~ ~a_8~ ~=~ ~7~ ~\&~ ~6~ ~\&~ ~7~ ~=~ ~6~.
• Yêu cầu ~l = 3, r = 7~: ~a_3~ ~\&~ ~a_4~ ~\&~ ~a_5~ ~\&~ ~a_6~ ~\&~ ~a_7~ ~=~ ~5~ ~\&~ ~3~ ~\&~ ~2~ ~\&~ ~7~ ~\&~ ~6~ ~=~ ~2~.

Qua đó, ta thấy dãy ~a~ trên là dãy ~a~ thỏa mãn tất cả ~m~ yêu cầu.