After completing his high school physics studies, Cindy intends to apply his knowledge. He dug out a printed circuit board with 2 rows of contacts, each row having $n+1$ contacts. He plans to connect these contacts with thin copper wires as shown in the figure below (blue represents contacts, red represents wires, and the power source is not connected), and then calculate the resistance and current. Connecting two adjacent nodes in the figure below requires 1 unit length of copper wire. To achieve this, Cindy borrowed some copper wires from Bob with a total length of $3n$. Cindy can bend each copper wire several times, but cannot break any wire. Please find any valid solution for Cindy, or report that it is impossible!

Implementation Details

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

int[][] wiring(int n, int[] w)

• $n$: The length of each row, as described in the problem.
• $w$: The $i$-th element ($0\le i\le |w|-1$) represents a copper wire of length $w[i]>0$. It is guaranteed that the sum of the elements in $w$ is $3n$.
• The procedure you implement will be called exactly once.
• If there is no solution, you should return an empty array.
• Otherwise, you should return an array consisting of three arrays of length $n$, representing which copper wire (numbered $0$ to $|w|-1$) is used for each unit segment of the horizontal wires in the first row, the vertical wires, and the horizontal wires in the second row, respectively, from left to right.

Examples

Input 1

3 [3, 2, 2, 2]

Output 1

[[0, 0, 2], [0, 1, 2], [1, 3, 3]]

Note

The output corresponds to the figure below.

Constraints

$1\le n, |w|\le 10^5$

$\sum_{t\in w} t=3n$

Subtasks

1. (10 points) $n\le 3$, $|w|\le 9$
2. (20 points) All copper wire lengths are at most 2
3. (30 points) All copper wire lengths are at least 2
4. (20 points) $n, |w|\le 5000$
5. (20 points) No special restrictions.

Sample Grader

The sample grader reads the input in the following format:

• First line: $n~|w|$
• Second line: The elements of $w$ in order

The sample grader prints your output in the following format:

• First line: Output Yes if a solution exists, otherwise output No
• If a solution exists, the next three lines print the returned solution in order