很久以前，存在一个古老的文明，其记录大多已湮没在历史中。已知当时有 $n$ 个交战派系，按从西到东的顺序排列并编号为 $1$ 到 $n$。第 $i$ 个交战派系的财富值由一个正整数 $w_i$ 表示。
这些交战派系之间从未实现真正的和平，但众所周知，为了对抗他们认为对所有人构成最大威胁的对象，他们会勾结并达成休战。当然，这只有在他们的联合力量确实能够击败该最大威胁时才有意义。
如果存在一个派系，其财富值严格大于所有其他派系财富值之和，我们称该文明处于“霸权”状态。
根据记录，历史上发生了 $n-1$ 次以下过程：
- 其中一个派系崩溃。
- 如果该文明不处于霸权状态，则财富值最大的派系崩溃。
- 如果该文明处于霸权状态，则财富值最小的派系崩溃。
- 如果出现平局，则位于最西侧的财富值最大/最小的派系崩溃。
- 此后，其西侧和东侧最近的未崩溃派系（如果存在）的财富值各增加崩溃派系财富值的一半（向下取整）。
- 即使崩溃的派系只与另一个派系相邻，该派系也只能获得崩溃派系财富值的一半。另一半则丢失了，可能是被蛮族抢走了，或者其他什么原因。
经过 $n-1$ 次迭代后，只剩下一个派系。但即便如此，这个文明还是灭亡了，可能是被蒙古人灭的？或者是罗马人。无论如何，记录已随时间流逝而丢失。
但幸运的是，作为一名计算机科学家，你可以模拟这个过程，找出派系崩溃的确切顺序，以及每个派系在崩溃时的财富值。
输入格式
第一行包含一个整数 $n$。
第二行包含 $n$ 个空格分隔的整数 $w_1, w_2, w_3, \dots, w_n$，表示各派系的初始财富值。
数据范围
- $2 \le n \le 2 \cdot 10^5$
- 对于每个 $i$，$1 \le w_i \le 10^9$
输出格式
输出 $n$ 行，描述每个派系崩溃的顺序（先崩溃的先输出）。每一行应包含两个空格分隔的整数：派系的编号及其崩溃时刻的财富值。
样例
样例输入 1
5 3 1 4 9 1
样例输出 1
4 9 3 8 1 3 2 6 5 12
样例输入 2
6 12 4 12 1 1 7
样例输出 2
1 12 3 12 5 1 4 7 6 10 2 24
说明
以下是第二个样例输入中发生的事件：
- 财富值最大的派系财富为 12，其中派系 1 是最西侧的。此时文明不处于霸权状态，因此派系 1 崩溃。其财富的一半流向派系 2。此时派系 2、3、4、5、6 的财富值分别为 $\{10, 12, 1, 1, 7\}$。
- 派系 3 财富为 12，因文明不处于霸权状态而崩溃。派系 2 和 4 各获得其财富值的一半。此时派系 2、4、5、6 的财富值分别为 $\{16, 7, 1, 7\}$。
- 派系 2 是最富有的，财富值为 16，此时文明处于霸权状态。财富值最小的派系 5 崩溃。注意 $1/2$ 向下取整为 0，因此与 5 相邻的派系获得的财富为 0。此时派系 2、4、6 的财富值分别为 $\{16, 7, 7\}$。
- 文明仍处于霸权状态，派系 4 是财富值为最小值 7 的派系中最西侧的一个。它崩溃，派系 2 和 6 的财富值变为 $\{19, 10\}$。
- 文明仍处于霸权状态，派系 6 财富为 10，是当前最弱的，因此崩溃。派系 2 独自拥有 $\{24\}$ 的财富，直到它最终也崩溃。