Consider an equilateral triangle with side length $n$, which is divided into $n^2$ small equilateral triangles of side length $1$. Among these, there are $\frac{n(n+1)}{2}$ upward-pointing triangles and $\frac{n(n-1)}{2}$ downward-pointing triangles. Now, $n$ of the upward-pointing triangles have been removed, leaving $\frac{n(n-1)}{2}$ upward-pointing triangles and $\frac{n(n-1)}{2}$ downward-pointing triangles. Determine whether it is possible to cover all remaining small triangles using $\frac{n(n-1)}{2}$ rhombi, each with side length $1$ and angles of $60^\circ$ and $120^\circ$. If a solution exists, output one.

An equilateral triangle of side length $4$ and three types of rhombi, labeled $1, 2, 3$ from left to right.

An example for $n=4$.

Input

The first line contains a positive integer $n$, representing the side length of the large equilateral triangle.

The next $n$ lines describe the removed upward-pointing triangles. For each $i$ where $1 \leq i \leq n$, the $(i+1)$-th line of the input contains a binary string of length $i$. The $j$-th character being '0' indicates that the $j$-th upward-pointing small triangle in the $(i+1)$-th row of the large triangle has been removed.

Output

If there is no valid way to cover the triangles with rhombi, output Impossible!.

Otherwise, output any valid solution. A valid solution consists of $n$ lines, where the $i$-th line is a string of length $i$. The $j$-th character in the $i$-th line represents the state of the $j$-th upward-pointing small triangle in that row, formatted as follows:

• If the $j$-th character in the $i$-th line is '-', it means this small triangle was removed.
• If the $j$-th character in the $i$-th line is '1', it means this small triangle is covered by the first type of rhombus.
• If the $j$-th character in the $i$-th line is '2', it means this small triangle is covered by the second type of rhombus.
• If the $j$-th character in the $i$-th line is '3', it means this small triangle is covered by the third type of rhombus.

Examples

Input 1

4
0
11
010
1101

Output 1

-
21
-3-
33-1

Constraints

It is guaranteed that $n \leq 5000$.

Subtask 1 (5 pts): $n \leq 5$.

Subtask 2 (10 pts): $n \leq 10$.

Subtask 3 (35 pts): $n \leq 500$.

Subtask 4 (5 pts): It is guaranteed that exactly one upward-pointing small triangle is removed in each row.

Subtask 5 (15 pts): It is guaranteed that a solution exists.

Subtask 6 (30 pts): No special constraints.