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}$ $\mathrm{\&}$ $a_{l_i+1}$ $\mathrm{\&}$ ... $\mathrm{\&}$ $a_{r_i}$ là chính xác $v_i$, với $\mathrm{\&}$ 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$ $\mathrm{\&}$ $a_3$ $=$ $1$.
• Yêu cầu $l=5,r=8$: $a_5$ $\mathrm{\&}$ $a_6$ $\mathrm{\&}$ $a_7$ $\mathrm{\&}$ $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.