一种新的整数存储格式 IIII-4 正在开发中。每个整数的编码结果由一、二、三、四或五个 4 位组组成。第一个组是强制性的，随后是零到四个可选的附加组。

解码过程如下：

1. 读取第一个 4 位强制组。
2. 在表中查找该组对应的附加组数量 $g$ 和偏移量 $f$。
3. 读取 $g$ 个附加组。将这些组解码为一个从 $0$ 到 $2^{4g} - 1$ 的整数 $y$。
4. 将偏移量加到 $y$ 上，即结果为 $y + f$。

给定两个整数 $x$ 和 $y$ 以及一个整数序列 $a_1, a_2, \dots, a_n$，满足 $x \le a_i \le y$。你的目标是确定一个查找表和偏移量，使得能够编码和解码从 $x$ 到 $y$（包含边界）的所有整数，并使输入序列的编码长度尽可能短。

注意，用于将数字从 $0$ 解码到 $2^{4g} - 1$ 的位顺序对于本题目的目的无关紧要。

使用此表编码从 $x$ 到 $y$ 的每个整数必须有唯一的方式。然而，该范围之外的整数可以用任意方式编码。

输入格式

第一行包含两个整数 $x$ 和 $y$ ($-10^9 \le x \le y \le 10^9$, $y - x \le 1\,000\,000$)，表示需要用该方法编码的范围边界。

第二行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示要编码的序列长度。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($x \le a_i \le y$)。

输出格式

打印最优表，由对应于 16 个前缀的解码信息的 16 行组成。

每一行应包含两个整数：$g_i$ ($0 \le g_i \le 4$) 表示附加组的数量，$f_i$ ($-2 \cdot 10^9 \le f_i \le 2 \cdot 10^9$) 表示偏移量。

给定的数字序列必须通过该表编码为最少的位数。保证至少存在一种有效的编码方式。如果存在多个最优表，你可以打印其中任何一个。

样例

样例输入 1

0 15
16
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

样例输出 1

0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
0 13
0 14
0 15

样例输入 2

-128 127
4
1 0 -1 0

样例输出 2

2 -261
0 -5
0 -4
0 -3
0 -2
0 -1
0 0
0 1
1 2
1 18
1 34
1 50
1 66
1 82
1 98
1 114