Binary Search

Interview

Time limit1sMemory limit128 MB

Summary

Find every array length N for which this binary search on a sorted array reports finding x at index i after exactly L comparisons.

Level: Medium6 of 10
Topics: Binary search, Math, Implementation
Solved: No attempts yet

Problem

The program fragment below performs a binary search for an integer x in an array A that is sorted in nondecreasing order:

#define MAXN 10000

int A[MAXN];
int N;

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

  p = 0;      /* left boundary of the search */
  q = N - 1;  /* right boundary of the search */
  L = 0;      /* comparison counter */
  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;
  }
}

Before BinarySearch is called, N is set to some integer with $1 \le N \le 10000$ , and the array A is filled with a nondecreasing integer sequence.

It is known that the procedure terminated by printing the message Found item i = XXX in L = XXX comparisons for some specific values of i and L.

Write a program that finds every value of N that could have produced this message. Because there can be many such values, group all consecutive values of N into intervals and report only the first and last value of each interval.

Input

A single line containing two integers i and L ( $0 \le i < 10000$ and $1 \le L \le 14$ ), separated by a space.

Output

On the first line, print a single integer K: the number of intervals of possible values of N.

Then print K lines, one interval per line in ascending order. Each line contains two integers A_i and B_i ( $A_i \le B_i$ ), separated by a space, giving the first and last value of that interval.

If no value of N is possible, print a single line containing 0.

Examples2

Example 1
Input
```
9000 2
```
Expected output
```
0
```
Example 2
Input
```
10 3
```
Expected output
```
4
12 12
17 18
29 30
87 94
```