Background

Items can move on their own, and the usually gentle youkai suddenly started causing trouble, all because of the influence of the Miracle Mallet.
Although the amanojaku who incited the little people escaped in the end, since the one who actually used the Miracle Mallet was a little person, Reimu decided to keep them under surveillance. But it feels like there are no bad intentions anymore.

But just at that time, strange clouds appeared in the sky again.
Just like when the Inverted Castle appeared, it was a magical storm.

"That wasn't me," Sukuna Shinmyoumaru explained.
So who, exactly, stirred up such a storm again?
To find out the reason, Reimu and the others rushed into the storm once more.

Descendants of the little people, the inverted castle, and the amanojaku who rebels just to rebel.
What is hidden behind all of this?

Problem Description

Brief statement

$n$ magnets are arranged into a ring. Each magnet has a magnetic force, represented as $4^{a_i}$. Any two adjacent magnets have different magnitudes of magnetic force. All magnets have the same size, with length $1$ unit. When placing them, there are two orientations: north pole facing left, and north pole facing right. When two magnets attract each other, they will be tightly attached; when they repel each other, suppose their magnetic forces are $u$ and $v$, then they will be separated by $u+v$ units.

You are given the length of the entire ring (including the length of each magnet, and the distances between adjacent magnets), denoted as $d_0$ units. For the $i$-th magnet, you are also given the length of the ring formed by the remaining magnets after removing this magnet, denoted as $d_i$ units.

Find any possible arrangement of magnets that satisfies the given data (and also satisfies that adjacent magnets have different magnetic force magnitudes), and you may decide the magnetic force used by each magnet. A solution is guaranteed to exist.

Original statement

In the thunderstorm caused by Horikawa Raiko, drums with electromagnetic fields around them are swaying to the rhythm. Under the strong electromagnetic interference, the shrine maiden and the magician lost contact with the ground.

There are $n$ such drums with magnetic force, all of exactly the same size (can be regarded as unit length $1$), and they are arranged into a ring. To make the danmaku look nice, the magnetic force on the $i$-th drum is $4^{a_i}$, and adjacent drums have different magnitudes of magnetic force.

Each drum has magnetic north and south poles, and when placing them there are two possibilities: north pole facing left, or north pole facing right. If two drums attract each other, they will be tightly attached; if they repel each other, then the distance between them is the sum of their magnetic forces, in units of length.

Reimu recorded the total ring length $d_0$, which includes the length of each drum and the distances between adjacent drums, while Marisa is using her firepower to smash these drums. However, these drums are very sturdy: Marisa can only smash one drum at a time, and then Horikawa Raiko will replace the smashed drum with a drum of exactly the same size and magnetic force. But when smashing the $i$-th drum, under the effect of magnetic force the ring length will change. Marisa will record the length $d_i$ of the ring formed by the remaining drums at that moment (assume the magnetic effect happens instantly).

During breaks in the battle, Reimu and Marisa hope to use the data they recorded to find any drum arrangement that satisfies these data. To reduce the difficulty, they can freely decide the magnetic force on each drum. The data guarantees that a solution exists.

Solve the distribution of the drums as quickly as possible to end this incident!

Input Format

• The first line contains an integer $n$, the total number of magnets.
• The next $1$ line contains an integer $d_0$.
• The next $n$ lines each contain an integer; the integer on line $i$ is $d_i$.

Output Format

• Output $n$ lines in total. On line $i$, output two integers $f_i,a_i$, representing the magnet's orientation and magnetic force, respectively. If $f_i=0$, it means the north pole faces left; otherwise if $f_i=1$, it means the north pole faces right.

4
14
13
16
3
16

1 1
1 0
0 1
1 0

Hint

Explanation for Sample 1

In one valid solution, $c=\{1,1,0,1\}$ and $a=\{1,0,1,0\}$. Below is an illustration of this solution.

Initially, the magnets are in the state shown in the figure below. The number above each magnet is its magnetic force magnitude (i.e., the value of $4^{a_i}$), and the $\textsf{N/S}$ marked on the magnet are its poles. Due to the author's limited ability, the ring shape cannot be restored, so a "portal" method is used to twist space-time.

It is easy to see that the total length is $14$.

The situation after removing the first magnet is shown in the figure. It is easy to see that the total length is $13$.

The situation after removing the second magnet is shown in the figure. Because the second magnet is missing as a barrier, the first and third magnets become adjacent directly, producing a larger gap. You can see that the total length is $16$.

The situation after removing the third magnet is shown in the figure. Note that all magnets have the same north direction, so they directly touch each other, and the total length is $3$.

The situation after removing the fourth magnet is shown in the figure. Since the third and first magnets are directly adjacent (because they form a ring; in the figure they are adjacent in the twisted space), it becomes like this. The total length is $16$.

Constraints and notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Special property} & \textbf{Score} \\\hline 1 & 10 & - & 10 \\\hline 2 & 10^5 & - & 30 \\\hline 3 & 10^6 & \text{A} & 5 \\\hline 4 & 10^6 & - & 55 \\\hline \end{array}$$

Special property $\textbf{A}$: It is guaranteed that there exists a solution in which all magnets have the same orientation.

For all testdata, it is guaranteed that $1\leq n\leq 1\times10^6$ and that there exists at least one valid solution. In addition, it is guaranteed that $d_i< 2^{63}$, and the $a_i$ you construct should be within $[0,10^9]$.

Translated by ChatGPT 5