Sequences of 1 and -1

A sequence of length N consists only of 1 and -1. Define the value of a sequence as the sum of all its elements.

The product of two sequences is defined by multiplying elements in the same positions. For example, multiplying {-1, 1, -1, -1} and {1, 1, -1, 1} gives {-1, 1, 1, -1}, whose sequence value is 0.

You are given M sequences a_1, a_2, ..., a_M. Each a_i has length N and consists only of 1 and -1. For each a_i, choose a sequence b_i of length N so that the product of a_i and b_i has sequence value 0.

In addition, among b_1, b_2, ..., b_M, the number of distinct sequences must be at most N. Write a program that outputs such sequences b_i. Since a sequence value of 0 is impossible when N is odd, the input only contains even N.

The first line contains two integers N and M separated by a space. N is even, 2 <= N <= 100, and 1 <= M <= 10,000.

Each of the next M lines contains one sequence a_1, a_2, ..., a_M. Each line contains N integers, each either 1 or -1, separated by spaces.

Print M lines, one for each of b_1, b_2, ..., b_M. Each line must contain N integers, each either 1 or -1, separated by spaces.

The number of distinct sequences among the printed lines must be at most N. If there are multiple valid answers, print any one of them. Every input is guaranteed to have at least one valid answer.