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 0Output 1
2 1 0 1Input 2
3 2
1 1 2 0
1 1 1 1Output 2
2 0 2Input 3
5 0Output 3
0 1 2 0 1