Bob has an $n \times n$ matrix. Each position contains an integer between $1$ and $n^2$. Bob remembers that the $i$-th row ($0 \le i \le n-1$) contains $a_i$ distinct numbers, and the $i$-th column ($0 \le i \le n-1$) contains $b_i$ distinct numbers. Since Bob does not like repeating the same number in an entire row or column, $a_i, b_i \ge 2$.

Somehow, Bob lost the matrix and now only has $a$ and $b$. Please help Bob recover the matrix! Any matrix that satisfies the given constraints for $a$ and $b$, and where all elements are between $1$ and $n^2$, is considered correct.

Implementation Details

You should include matrix.h and implement the following procedure:

int[][] cons(int n, int[] a, int[] b)

• $n$: The side length of the matrix.
• $a$: The number of distinct values in each row.
• $b$: The number of distinct values in each column.
• Your implemented procedure will be called exactly once.
• You should return an $n \times n$ matrix $m$ that you constructed. The element at the $i$-th row and $j$-th column should be $m[i][j]$.
• It is guaranteed that a solution exists.

Examples

Input 1

3
2 2 3
2 3 3

Output 1

1 2 1
2 3 2
1 9 4

Constraints

$1 \le n \le 2000$.

For each $1 \le i \le n$, $2 \le a_i, b_i \le n$.

It is guaranteed that a solution exists.

Subtasks

1. (10 points) $n \le 5$
2. (20 points) $n \le 10$
3. (20 points) $n \le 50$
4. (20 points) For each $i$, $b_i = 2$.
5. (30 points) No special constraints.

Sample Grader

The sample grader reads the input in the following format:

• First line: $n$
• Second line: $a[0]~a[1]~\cdots~a[n-1]$
• Third line: $b[0]~b[1]~\cdots~b[n-1]$

The sample grader prints your output in the following format:

• The matrix you constructed, with each row separated by a newline and elements within each row separated by spaces.