Lời khai chẵn lẻ

Có một xâu nhị phân bí mật $s_1{s}_2\dots s_n$ (mỗi $s_i$ là $0$ hoặc $1$). Bạn nhận được lần lượt $m$ lời khai về xâu này; lời khai thứ $j$ gồm ba số $l_j,r_j,t_j$, nghĩa là "trong đoạn $s_{l_j},s_{l_j+1},\dots ,s_{r_j}$ có một số chẵn chữ số $1$" nếu $t_j=0$, hoặc "có một số lẻ chữ số $1$" nếu $t_j=1$.

Không phải lời khai nào cũng đúng. Hãy tìm số $k$ lớn nhất sao cho $k$ lời khai đầu tiên có thể cùng đúng, tức là tồn tại một xâu nhị phân độ dài $n$ thỏa mãn đồng thời cả $k$ lời khai đó.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$, $m$.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa ba số nguyên $l_j,r_j,t_j$.

Dữ liệu ra

In ra một số nguyên là $k$ lớn nhất tìm được.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2·{10}^5$
• $1\le l_j\le r_j\le n$
• $t_j\in \{0,1\}$

Ví dụ