#P1064. 裂变

裂变

题目背景

面条老师发现了一张神奇的魔法卡片!这张卡片的正面背面都有数字,并且某些情况下还会分裂成两张卡片!

题目描述

卡片保证正面的数字小于背面的数字。对于一张正面写了 xx 背面写了 yy 的卡片,如果 xyxx\le y-x 就会发生分裂。这张卡片会分裂成两张卡片:

  • 第一张卡片的正面为 xx,背面为 x+y2\lfloor \frac{x+y}{2} \rfloor
  • 第二张卡片的正面为 x+y2+1\lfloor \frac{x+y}{2} \rfloor+1,背面为 yy

x\lfloor x \rfloor表示对xx向下取整。

分裂出来的卡片如果也满足分裂条件就会继续分裂。请问最终会存在哪些卡片?

输入格式

一行为空格隔开的两个整数 x,yx,y

输出格式

第一行为一个整数 cntcnt,表示最终会存在 cntcnt 张卡片。

接下来 cntcnt 行,每行都有空格隔开的两个正整数。第 ii 行为第 ii 张卡片的正面数字和背面数字。(所有卡片按照正面数字从小到大的顺序输出

1 10
5
1 1
2 2
3 3
4 5
6 10

分裂过程:

  • (1,10)
  • (1,5)(6,10)
  • (1,3)(4,5)(6,10)
  • (1,2)(3,3)(4,5)(6,10)
  • (1,1)(2,2)(3,3)(4,5)(6,10)

数据规模与约定

  • 对于 10%10\% 的数据,x=yx = y
  • 对于另外 10%10\% 的数据,x=1x = 1
  • 对于 100%100\% 的数据,1xy1041 \le x\le y \le 10^4