You are given a matrix Am×(n+1). You need to find n integers x1,x2,⋯,xn that satisfy the following conditions.
- For each 1≤i≤n, xi∈{0,1}
- For each 1≤i≤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