XXL Olympic Football

To make the 2028 Summer Olympics even more exciting, the organizers have planned an XXL football match for both the opening and closing ceremonies. A special $1000\times 400$ meter field is already in construction for these games!

here are $2M$ athletes participating, coming from $N$ countries. Specifically, $A_i$ athletes are representing country $i$ for each $i$ from $0$ to $N - 1$, inclusive. For the two football games we have the following restrictions:

• For the opening ceremony, two teams of $K$ athletes each must be formed.
• For the closing ceremony, two teams of $M-K$ athletes each must be formed.
• Every athlete must participate in exactly one game (either opening or closing), and in only one team.
• No two athletes from the same country may play against each other in a game.

As the chief computer scientist of the Olympics, your task is to divide the athletes into four teams (two per game) satisfying all the above conditions.

You can assume that:

• $K \ge \frac{1}{2}M$, that is, the opening is at least as popular as the closing ceremony.
• $K \le \frac{2}{3}M$, that is, the opening may be just slightly more popular than the closing ceremony.
• No country sends more than $M$ athletes.

We can prove that a valid assignment always exists under the given conditions.

Input data

The first line contains two integers $N$ and $K$ - the numbers of countries, and the number of athletes to play in a team in the opening ceremony, respectively.

The second line contains $N$ positive integers $A_0, A_1, \ldots, A_{N-1}$, the number of athletes from each country.

Output data

Print $N$ lines. Line $i$ should contain the assignment of the athletes from country $i$, represented by four non-negative integers:

• The number of athletes assigned to the home team of the opening ceremony.
• The number of athletes assigned to the away team of the opening ceremony.
• The number of athletes assigned to the home team of the closing ceremony.
• The number of athletes assigned to the away team of the closing ceremony.

If there are multiple valid solutions, you may output any of them.

Constraints and clarifications

• $2 \le N \le 100\,000$.
• $\sum_{i=0}^{N-1} A_i$ is even. Let $M = \frac{1}{2}\sum_{i=0}^{N-1} A_i$.
• $1\leq A_i \leq \min\Bigl(M, 10^9\Bigr)$ for each $i=0 \ldots N-1$.
• $\frac{1}{2}M \le K \le \frac{2}{3}M$.

Example 1

stdin

3 4
5 3 6

stdout

4 0 1 0
0 0 0 3
0 4 2 0

Explanation

In the first sample case one valid assignment is:

• $4$ athletes from country $1$ play against $4$ athletes from country $3$ in the opening ceremony.
• All $3$ athletes from country $2$ play against the remaining athletes from countries $1$ and $3$ in the closing ceremony.
  Note that there exist other valid assignments.

Example 2

stdin

5 6
3 4 3 6 4

stdout

2 0 0 1
0 4 0 0
0 2 0 1
4 0 0 2
0 0 4 0