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 nên hãy đọc kỹ đề. Với subtask 1, ~n, m \le 1000~ và ~0 \le v_i \le 1~.

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 1000)~.
• ~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 \le 1)~.

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 3
2 3 1
5 8 0
7 7 1

Dữ liệu ra

2 1 3 7 1 4 1 2

Giải thích

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

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

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.