Zhegalkin 多项式是一个布尔函数 $f(x_1, \dots, x_n)$，其表示形式如下：

$$f(x_1, \dots, x_n) = \bigoplus_{S \subseteq \{1, 2, \dots, n\}} a_S \cdot \bigwedge_{i \in S} x_i$$

其中 $\oplus$ 和 $\wedge$ 分别代表布尔运算 XOR 和 AND，XOR 是对所有变量子集进行的，且对于每个子集 $S \subseteq \{1, 2, \dots, n\}$，都有 $a_S \in \{0, 1\}$。

在本题中，给定 $m$ 组变量值 $(v_{i1}, \dots, v_{in})$ 和 $m$ 个布尔值 $y_i \in \{0, 1\}$。你需要构造一个至多包含 9000 个非零项的 Zhegalkin 多项式，使得对于每个 $i = 1, 2, \dots, m$，满足 $f(v_{i1}, \dots, v_{in}) = y_i$。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 变量的数量和给定变量值的组数 ($1 \le n, m \le 2000$)。

接下来的 $m$ 行，每行包含一个长度为 $n$ 的字符串（由 0 或 1 组成），表示第 $i$ 组变量值，随后是一个整数 $y_i$。

保证所有变量值集合互不相同，且至少有一组满足 $y_i = 1$。

输出格式

你的多项式必须包含至多 9000 个满足 $a_S = 1$ 的项。对于每一项，输出其对应的变量子集 $S$，表示为一个长度为 $n$ 的 01 字符串，其中第 $i$ 个字符为 1 表示 $i \in S$，为 0 表示 $i \notin S$。你可以以任意顺序输出这些项，但不能有重复的子集。

如果存在多种可能的答案，输出其中任意一个即可。如果解不存在，输出 -1。

保证如果解存在，则一定存在一个至多包含 9000 个满足 $a_S = 1$ 的项 $S$ 的解。

样例

样例输入 1

2 3
01 1
10 1
11 1

样例输出 1

00

样例输入 2

3 2
000 0
111 1

样例输出 2

100
010
001

说明

第一个样例的一种可能答案是 $f(x_1, x_2) = 1$。

第二个样例的一种可能答案是 $f(x_1, x_2, x_3) = x_1 \oplus x_2 \oplus x_3$。