Приведенный ниже фрагмент программы выполняет бинарный поиск целого числа в массиве, отсортированном в порядке неубывания.

Pascal

procedure BinarySearch(x: integer; N: integer; A: array of integer);
var
    p, q, i, L: integer;
begin
    p := 0;     { Left border of the search  }
    q := N - 1; { Right border of the search }
    L := 0;     { Comparison counter         }
    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++

void BinarySearch(int x, int N, int* A)
{
    int p = 0;     // Left border of the search
    int q = N - 1; // Right border of the search
    int L = 0;     // Comparison counter
    while (p <= q) {
        int 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;
    }
}

Python

def BinarySearch(x: int, N: int, A: list):
    p = 0      # Left border of the search
    q = N - 1  # Right border of the search
    L = 0      # Comparison counter
    while p <= q:
        i = (p + q) // 2
        L += 1
        if A[i] == x:
            print('Found item i =', i, 'in L =', L, 'comparisons')
            return

        if x < A[i]:
            q = i - 1
        else:
            p = i + 1

Перед вызовом BinarySearch в N было записано некоторое целое число от 1 до 10000 включительно, а массив A был заполнен неубывающей последовательностью целых чисел длиной N.

Процедура завершилась сообщением «Found item i = XXX in L = XXX comparisons» с некоторыми известными значениями i и L.

Напишите программу, находящую все возможные значения N, которые могли привести к такому сообщению. Количество таких значений N может быть достаточно большим, поэтому сгруппируйте все последовательные значения N в интервалы и выведите только первое и последнее значение из каждого интервала.

В единственной строке записаны целые числа i и L (0 ≤ i ≤ 9999; 1 ≤ L ≤ 14).

В первой строке выведите целое число K – общее количество интервалов из возможных значений N. Далее в K строках перечислите эти интервалы в порядке возрастания.

Каждая строка должна содержать целые числа A_i и B_i (A_i ≤ B_i), представляющие собой первое и последнее значение в интервале.

Если возможные значения N отсутствуют, выведите 0.