You are given a matrix $A_{m \times (n+1)}$. You need to find $n$ integers $x_1,x_2,\cdots,x_n$ that satisfy the following conditions.

• For each $1 \leq i \leq n$, $x_i \in \{ 0, 1, 2 \}$
• For each $1 \leq i \leq m$, $\sum_{j=1}^n A_{i,j} \cdot x_j \equiv A_{i,n+1} \pmod 3$

If there are multiple possible solutions, output any of them.

Input

The first line contains two integers $n$ and $m$ ($1 \leq n,m \leq 2 \times 10^3$).

The next $m$ lines describes the matrix $A$:

• The $i$-th line of these lines contains $n+1$ numbers $A_{i,1}, A_{i,2}, \cdots, A_{i,n}, A_{i,n+1}$

Output

Output a single line contains $n$ integers $x_1,x_2,\cdots, x_n$. It is guaranteed that there's at least one valid solution.

Examples

Input 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

Output 1

2 1 0 1

Input 2

3 2
1 1 2 0
1 1 1 1

Output 2

2 0 2

Input 3

5 0

Output 3

0 1 2 0 1