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 \}$
• For each $1 \leq i \leq m$, $\sum_{j=1}^n A_{i,j} \cdot x_j \equiv A_{i,n+1} \pmod 2$

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 5 \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

3 3
0 0 1 1
1 0 1 0
1 1 1 1

Output 1

1 1 1