Problems
Binary Search
Binary Search
The program fragment below performs binary search of an integer number in an array that is sorted in a nondescending order:
Before BinarySearch was called, \textbf{N} was set to some integer number from \textbf{1} to \textbf{10000} inclusive and array \textbf{A} was filled with a nondescending integer sequence.
It is known that the procedure has terminated with the message "\textbf{Found item i = XXX in L = XXX comparisons}" with some known values of \textbf{i} and \textbf{L}.
Your task is to write a program that finds all possible values of \textbf{N} that could lead to such message. However, the number of possible values of \textbf{N} can be quite big. Thus, you are asked to group all consecutive \textbf{Ns} into intervals and write down only first and last value in each interval.
\InputFile
The input consists of a single line with two integers \textbf{i} and \textbf{L} (\textbf{0} ≤ \textbf{i} < \textbf{10000} and \textbf{1} ≤ \textbf{L} ≤ \textbf{14}), separated by a space.
\OutputFile
On the first line of the output write the single integer number \textbf{K} representing the total number of intervals for possible values of \textbf{N}. Then \textbf{K} lines shall follow listing those intervals in an ascending order. Each line shall contain two integers \textbf{A_i}and \textbf{B_i} (\textbf{A_i} ≤ \textbf{B_i}) separated by a space, representing first and last value of the interval.
If there are no possible values of \textbf{N} exist, then the output shall contain the single \textbf{0}.
Input example #1
9000 2
Output example #1
0