QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB
[0]

# 313. Equation Mod 2

Statistics

You are given a matrix Am×(n+1). You need to find n integers x1,x2,,xn that satisfy the following conditions.

  • For each 1in, xi{0,1}
  • For each 1im, \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