Egor 了解到了一个名为“简短陈述联盟”（Brief Statements Union，简称 BSU）的秘密组织，其最终目标是使所有竞赛编程问题的陈述清晰简洁，并消除陈述中那些冗长、枯燥且不必要的背景故事。

Egor 决定加入该组织。为此，他编写了以下题目，并配以简短的陈述：

给定一个整数 $n$ 和 $k$ 个条件。第 $i$ 个条件指出，所有整数 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 的按位与（bitwise AND）等于 $x_i$。

对于每个条件 $i$，判断是否存在一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$，使得该数组满足除条件 $i$ 之外的所有条件。注意，如果该数组同时也满足条件 $i$，也是可以的。

该组织的委员会很喜欢 Egor 的题目陈述。这就是他被该组织录取的原因。现在，Egor 决定将这道题提供给本次比赛，因此你需要解决它。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示数组所需的长度和条件的数量（$1 \le n, k \le 10^6$）。

接下来 $k$ 行，第 $i$ 行包含三个整数 $l_i, r_i, x_i$，描述第 $i$ 个条件（$1 \le l_i \le r_i \le n, 0 \le x_i \le 10^{18}$）。

输出格式

输出一个长度为 $k$ 的二进制字符串。如果存在一个长度为 $n$ 的数组，在移除第 $i$ 个条件后满足其余所有条件，则第 $i$ 个字符应为 '1'。否则，第 $i$ 个字符应为 '0'。

样例

样例输入 1

4 3
1 2 1
2 4 3
2 2 1

样例输出 1

011

样例输入 2

4 3
1 2 1
3 4 3
2 3 1

样例输出 2

111