给定一个 $m \times (n+1)$ 的矩阵 $A$。你需要找到 $n$ 个整数 $x_1, x_2, \cdots, x_n$，满足以下条件：

• 对于每个 $1 \leq i \leq n$，$x_i \in \{ 0, 1, 2 \}$
• 对于每个 $1 \leq i \leq m$，$\sum_{j=1}^n A_{i,j} \cdot x_j \equiv A_{i,n+1} \pmod 3$

如果存在多个可能的解，输出其中任意一个即可。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n,m \leq 2 \times 10^3$)。

接下来的 $m$ 行描述了矩阵 $A$：

• 其中第 $i$ 行包含 $n+1$ 个数字 $A_{i,1}, A_{i,2}, \cdots, A_{i,n}, A_{i,n+1}$

输出格式

输出一行，包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$。保证至少存在一个有效解。

样例

样例输入 1

4 5
1 0 2 1 0
0 0 0 1 1
0 0 1 2 2
2 1 0 1 0
1 0 2 1 0

样例输出 1

2 1 0 1

样例输入 2

3 2
1 1 2 0
1 1 1 1

样例输出 2

2 0 2

样例输入 3

5 0

样例输出 3

0 1 2 0 1