题目描述

对于非负整数 $l$ 和 $r$ $(l < r)$，令 $S(l, r)$ 表示由 $l$ 到 $r-1$ 的整数按顺序排列形成的序列。此外，当且仅当一个序列可以表示为 $S(2^i j, 2^i (j+1))$ 时，其中 $i$ 和 $j$ 为非负整数，我们称这个序列为好序列。

给定非负整数 $L$ 和 $R$ $(L < R)$。将序列 $S(L, R)$ 划分为最少数量的好序列，并输出划分数量和划分方案。更具体地说，找到最小的正整数 $M$，使得存在一个非负整数对序列 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ 满足以下条件，并输出这样的 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$。

• $L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R$
• $S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M)$ 都是好序列。

可以证明，使 $M$ 最小化的划分方案是唯一的。

输入格式

输入$L$和$R$，按以下格式输出答案：

$M$

$l_1$ $r_1$

$l_2$ $r_2$

$\vdots$

$l_M$ $r_M$

输出格式

注意，对 $(l_1, r_1), \ldots, (l_M, r_M)$ 应按升序输出。

样例

3 19

5
3 4
4 8
8 16
16 18
18 19

0 1024

1
0 1024

3940649673945088 11549545024454656

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

样例1解释

$S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)$ 可以被划分为以下五个好序列，这是最小可能的数量：

• $S(3,4)=S(2^0\cdot 3,2^0\cdot 4)=(3)$
• $S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)$
• $S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)$
• $S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)$
• $S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)$

数据范围

$0 \leq L < R \leq 2^{60}$，所有输入值都是整数。

来源

• AtCoder ABC349D