区间划分

题目描述

对于非负整数 $l$ 和 $r$($l \lt r$),记 $S(l, r)$ 为将 $l$ 到 $r-1$ 的整数按顺序排列得到的序列 $(l, l+1, \ldots, r-2, r-1)$。此外,如果一个序列可以表示为 $S(2^i j, 2^i (j+1))$(其中 $i, j$ 是非负整数),则称这个序列为"好序列"。

给定非负整数 $L$ 和 $R$($L \lt R$)。请将序列 $S(L, R)$ 划分为尽可能少的好序列,并输出划分的个数和划分方式。更形式化地说,求满足以下条件的最小正整数 $M$ 以及对应的非负整数对序列 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$:

• $L = l_1 \lt r_1 = l_2 \lt r_2 = \cdots = l_M \lt 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$
$\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

$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\cdot4)=(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 1024

1
0 1024

3940649673945088 11549545024454656

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

数据范围

• $0 \le L \lt R \le 2^{60}$
• 输入均为整数。