Balanced Sign Assignment

You are given a fixed sequence (a_1, a_2, \ldots, a_n) of positive integers which satisfies the following conditions:

1. Let (n) be an even integer such that (2 \le n \le 40) and let (a_i = 1) for all (1 \le i \le n). Then for every even integer (X) in the interval ([L,R]) with [ L = -n \quad \text{and} \quad R = n, ] there exists a choice of (b_1, b_2, \ldots, b_n) with each (b_i\in {-1,1}) satisfying [ \sum_{i=1}^{n} a_i,b_i = X. ] In other words, every even number between (-n) and (n) can be represented as the sum of the (a_i)'s multiplied by appropriate signs.

2. In addition, for every integer (i), let (cnt_i) be the number of occurrences of (i) in (a_1, a_2, \ldots, a_n). Then either (cnt_i = 0) or (cnt_i \ge 2). This condition is satisfied by our choice since the only value used is (1) and it appears (n) times (with (n\ge2)).

To verify that your fixed sequence (a) indeed has the desired property, the input consists of (Q) queries. In each query you are given an even integer (X \in [L, R]). For each query, output a valid sequence (b_1, b_2, \ldots, b_n) (each (b_i\in{-1,1}) ) such that

[ \sum_{i=1}^{n} a_i,b_i = X. ]

Since (a_i = 1) for all (i), the equation becomes

[ \sum_{i=1}^{n} b_i = X. ]

A simple solution is to choose exactly (\frac{n+X}{2}) of the (b_i)'s to be (+1) and the remaining (\frac{n-X}{2}) to be (-1). You can output any valid solution.

Note: The input guarantees that (n) is even and (X) is an even integer between (-n) and (n) (inclusive).

inputFormat

The first line contains two space-separated integers (n) (an even integer with (2 \le n \le 40)) and (Q) (the number of queries).

Each of the following (Q) lines contains an even integer (X) ((-n \le X \le n)) representing a query.

outputFormat

For each query, output a single line with (n) space-separated integers. Each integer must be either (1) or (-1) such that the sum (\sum_{i=1}^{n} b_i = X) holds. If there are multiple valid answers, print any one of them.

sample

4 3
4
0
-4

1 1 1 1
1 1 -1 -1
-1 -1 -1 -1