There are n cities in Byteland. The cities are numbered from 1 to n. City number i wants to make d_i trade agreements with other cities. Is it possible to arrange the trade agreements in such way that each of the cities makes exactly d_i trade agreements? A pair of cities can make any number of trade agreements and a city can not make a trade agreement with itself.

Input

The first line contains integer n, the number of cities. Next line contains n integers, d_1, d_2, \ldots, d_n.

Output

Output a n \times n matrix. Cell (i, j) of the matrix should contain the number of trade agreements city i makes with city j. Note that cell (i, j) should be equal to cell (j, i). If there are no valid solutions, output QAQ

Constraints

• 1 \le n \le 100
• 1 \le d_i \le 100

Examples

Input:

3
1 3 4

Output:

0 0 1
0 0 3
1 3 0

Input:

4
2 2 2 2

Output:

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Input:

3
1 3 5

Output:

QAQ