本题没有可用的提交语言。

题目描述

下面的程序片段在一个非降序排列的整数数组中进行二分查找：

Pascal版本 (文件 "sproc.pas")

const MAXN = 10000; 
var A: array[0..MAXN-1] of integer; 
    N: integer;

procedure BinarySearch(x: integer); 
var p, q, i, L: integer; 
begin 
    p := 0;      { 搜索的左边界 } 
    q := N-1;    { 搜索的右边界 } 
    L := 0;      { 比较计数器 } 
    while p <= q do 
    begin 
        i := (p + q) div 2; 
        inc(L); 
        if A[i] = x then 
        begin 
            writeln('Found item i = ', i, ' in L = ', L, ' comparisons'); 
            exit 
        end; 
        if x < A[i] then 
            q := i - 1 
        else 
            p := i + 1 
    end 
end;

C版本 (文件 "sproc.c")

#define MAXN 10000

int A[MAXN]; 
int N;

void BinarySearch(int x) { 
    int p, q, i, L;

    p = 0;      /* 搜索的左边界 */ 
    q = N-1;    /* 搜索的右边界 */ 
    L = 0;      /* 比较计数器 */ 
    while (p <= q) { 
        i = (p + q) / 2; 
        ++L; 
        if (A[i] == x) { 
            printf("Found item i = %d" 
                   " in L = %d comparisons\n", i, L); 
            return; 
        } 
        if (x < A[i]) 
            q = i - 1; 
        else 
            p = i + 1; 
    } 
}

在调用 BinarySearch 之前，N 被设置为一个从 1 到 10000 的整数，数组 A 被填充为一个非降序的整数序列。

已知该过程以消息 "Found item i = XXX in L = XXX comparisons" 终止，其中 i 和 L 是已知的值。

你的任务是编写一个程序，找出所有可能导致该消息的 N 的可能值。然而，可能的 N 的数量可能非常大。因此，你需要将所有连续的 N 分组为区间，并只写出每个区间的第一个和最后一个值。

输入

输入文件由一行组成，包含两个整数 i 和 L（0 <= i < 10000 且 1 <= L <= 14），用空格分隔。

输出

输出的第一行是一个整数 K，表示可能的 N 的区间总数。接下来的 K 行按升序列出这些区间。每行包含两个整数 Ai 和 Bi（Ai <= Bi），用空格分隔，表示区间的第一个和最后一个值。

如果不存在可能的 N 值，则输出文件应只包含一个 0。

示例输入 1

10 3

示例输出 1

4
12 12
17 18
29 30
87 94

来源

Northeastern Europe 2000