题目背景

道具会自己活动，本来温顺的妖怪突然大闹起来原来都是因为万宝槌的影响。
唆使小人的天邪鬼虽然最后逃走了，但因为真正使用万宝槌的是小人，所以灵梦决定对其进行监视。但是总感觉也没再有什么不良企图的样子。

但就在那时，天空再次出现了诡异的云团。
是与逆城出现之时一样的，魔力风暴。

“那不是我干的”，少名针妙丸这样解释着
到底，又是谁再次掀起了这样的风暴？
灵梦她们，为了调查清楚原因，再次冲进了风暴之中。

小人的末裔、逆转的城、为反抗而反抗的天邪鬼。
这背后又隐藏着什么呢。

题目描述

简要题意

$n$ 块磁铁排列成了一个环。每块磁铁都有磁力，用 $4^{a_i}$ 表示。相邻两块磁铁磁力大小不同。磁铁大小一致，长度均为 $1$ 单位长度。摆放时分为北极朝左和北极朝右。当两块磁铁互相吸引时，它们会紧紧靠拢，互相排斥时，记这两块磁铁的磁力为 $u$ 和 $v$，那么它们会相距 $u+v$ 单位长度。

目前已知整个环的长度（包括每个磁铁的长度，以及相邻磁铁之间的距离），记这个长度为 $d_0$ 个单位长度。对于第 $i$ 块磁铁，也已知若拿去这块磁铁，剩余磁铁组成的环的长度，记这个长度为 $d_i$ 个单位长度。

找到找到任意一种可能的磁铁排列方法满足这些已知的数据，（也要满足相邻两块磁铁磁力大小不同），并且可以决定所用磁铁的磁力。保证有解。

原始题意

在堀川雷鼓引发的雷暴中，一架架周围附带着电磁场的鼓正随着节奏摇摆着。在强大的电磁干扰下，巫女和魔法使与地面失去了联系。

这些尺寸完全相同（可以视作为单位长度 $1$）的带有磁力的鼓一共有 $n$ 架，它们排列成了一个环。为了让弹幕美观，第 $i$ 架鼓上带有的磁力是 $4^{a_i}$，而且相邻两架鼓带有的磁力大小不同。

每一架鼓都有磁性上的南北两极，而且在摆放的时候有北极朝左和北极朝右的两种情况。若两架鼓相互吸引它们会紧紧靠拢；而若它们相互排斥，这两架鼓之间的距离就是它们的磁力之和的单位长度。

灵梦记录下了整个环的长度 $d_0$，这包括了每架鼓的长度和相邻的鼓之间的距离，而魔理沙正在使用自己的火力击碎这些鼓。然而这些鼓的质量非常皮实，魔理沙一次只能击碎一个鼓，随后堀川雷鼓会用一个尺寸和磁力完全一致的鼓替代这个被击碎的鼓。但是在击碎第 $i$ 架鼓的时候，受到磁力的作用环的长度会发生变化，魔理沙会记录此时剩余的鼓组成的环的长度 $d_i$（假设磁力的作用是瞬间完成的）。

在战斗的间隙，灵梦和魔理沙希望通过她们记录下的数据，找到任意一种鼓的排布情况满足这些数据。为了降低难度，她们可以自由决定每架鼓上的磁力多少。数据保证有解。

尽快解出鼓的分布，从而结束这场异变吧！

输入格式

• 第一行有一个整数 $n$，表示磁铁的总个数。
• 接下来 $1$ 行一个整数，表示 $d_0$。
• 接下来 $n$ 行每行一个整数，其中第 $i$ 行的整数表示 $d_i$。

输出格式

• 输出共 $n$ 行。第 $i$ 行有两个整数 $f_i,a_i$，分别表示磁铁的方向与磁力。若 $f_i=0$ 则表示北极向左，否则若 $f_i=1$ 则表示北极向右。

4
14
13
16
3
16

1 1
1 0
0 1
1 0

提示

样例 1 解释

一种合法的方案中，$c=\{1,1,0,1\}$，$a=\{1,0,1,0\}$。以下是这种方案的图解。

初始时磁铁的状态如下图所示，磁铁上方的数字是它的磁力大小（即 $4^{a_i}$ 的值），磁铁上标记的 $\textsf{N/S}$ 是它的磁极。由于笔者能力有限，无法还原出环形，只能用这种传送门的方式扭曲时空了。

容易发现，总长度为 $14$。

拿掉第一块磁铁后的情形如图所示。容易发现，总长度为 $13$。

拿掉第二块磁铁后的情形如图所示。由于缺少了第二块磁铁的阻挡，第一块和第三块磁铁直接相邻，产生了更大的间距。可以发现，总长度为 $16$。

拿掉第三块磁铁后的情形如图所示。值得注意的是，所有磁铁北极方向相同，于是直接互相接触，总长度为 $3$。

拿掉第四块磁铁后的情形如图所示。由于第三块和第一块磁铁直接相邻（因为是形成了环。在图上则是扭曲后的空间里相邻），因此形成了这种模样。总长度为 $16$。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{特殊性质} & \textbf{分值} \\\hline 1 & 10 & - & 10 \\\hline 2 & 10^5 & - & 30 \\\hline 3 & 10^6 & \text{A} & 5 \\\hline 4 & 10^6 & - & 55 \\\hline \end{array}$$

特殊性质 $\textbf{A}$：保证存在一种方案，所有磁铁的方向一致。

对于所有数据，保证 $1\leq n\leq 1\times10^6$，存在至少一种合法方案。此外，保证 $d_i< 2^{63}$，你构造的 $a_i$ 大小应该在 $[0,10^9]$。