Description

为了获取T病毒解药的存放地点，Alice等人截获了保护伞公司的加密通讯，其可以看做一段长度为\(N\)的字符串，每个字符只会是\(0\)或\(1\)。
在截获通讯后，Alice对电报进行了\(K\)次观测：在每次观测中，Alice截取其中的\([L,R]\)一段子串，并记录下来这段子串中\(1\)的数量的奇偶性（即该通讯左起第\(L\)个字符到第\(R\)个字符中\(1\)的数量是否是奇数）。
不幸的是，原通讯在一次保护伞公司针对抵抗组织的突袭中被销毁，只留下来了所有的观测记录。你需要尝试将字符串的内容复原。

Format

Input

每个测试点仅包含一组测试数据。
第一行两个整数，分别为\(N\)(\(1≤N≤3000\))和\(K\)(\(1≤K≤3000\))。

之后的\(K\)行代表每一次观测记录：每行三个整数\(L_i\),\(R_i\),\(s_i\)(\(1 \leq L_i≤R_i \leq n,0 \leq s_i \leq 1\))，代表第\(i\)次观测了\([L_i,R_i]\)这段子串，\(s_i\)为\(1\)代表\(1\)的个数是奇数，否则是偶数。

Output

输出一行\(N\)个用空格隔开的整数，代表原字符串，行末不要输出多余空格。
保证至少存在一个解。如果有多个字符串满足要求，请输出字典序最小的字符串。

Sample 1

Input

3 3
2 2 1
3 3 0
2 3 1

Output

0 1 0

Sample 2

Input

20 2
7 8 1
1 18 0

Output

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0

Limitation

3s, 1GB for each test case.

Source

Vijos Original