Pearl Pairing

Bessie received $N$ pearls for her birthday ($2 \le N \le 100{,}000$, with $N$ always even). Each pearl is painted one of $C$ different colors ($1 \le C \le N$); the colors are numbered $1$ through $C$, and color $i$ is used on exactly $C_i$ pearls, so $C_1 + C_2 + \cdots + C_C = N$.

Because $N$ is even, Bessie wants to arrange all of the pearls into $N/2$ pairs so that the two pearls in each pair have different colors. It is guaranteed that at least one such pairing exists for the given input.

Because many valid pairings may exist, you must output one specific canonical pairing, defined precisely in the output section below.

• Line $1$: two space-separated integers $N$ and $C$.
• Lines $2 \dots C+1$: line $i+1$ contains a single integer $C_i$, the number of pearls of color $i$.

List the pearls in non-decreasing order of color: first all $C_1$ pearls of color $1$, then all $C_2$ pearls of color $2$, and so on through color $C$. Number the pearls in this order from $1$ to $N$.

Form $N/2$ pairs by matching the pearl in position $i$ with the pearl in position $i + N/2$, for $i = 1, 2, \dots, N/2$. Because a valid pairing is guaranteed to exist, the two pearls of every such pair always have different colors.

Print $N/2$ lines. On line $i$, print the two colors of the $i$-th pair, the smaller color first, separated by a single space.

In the sample, color $3$ is used on $4$ pearls, and colors $1$ and $2$ are each used on $2$ pearls. Under the canonical construction, each of the four color-$3$ pearls is paired with a pearl of color $1$ or color $2$.