I Speak Whales#1338
According to Wikipedia, a Walsh matrix is a square matrix with the size equal to a power of , whose elements are or , and such that the dot product of any two different rows (or columns) is zero. Below are the first three Walsh matrices. (The gray lines are imaginary and are shown for illustration only).
A Walsh matrix of size 2^N can be constructed as the combination of Walsh matrices of size 2^{N-1} arranged so that the lower right matrix is inverted, while the other matrices are not. That is:
Let us number the rows of the given Walsh matrix from the top starting with row . Similarly, number the columns from the left starting with column . Given four integers , , , and , write a program to construct a Walsh matrix of size 2^N and print the sum of all numbers in row between columns and inclusive.
Your program will be tested on one or more test cases. Each test case is given in a single line with four integers in the following order: , , , and , where 0 \leq N \leq 60, 0 \leq R < 2^N, 0 \leq S \leq E < 2^N, and E-S \leq 10000. The last line of the input file contains four and is not a test case.
For each test case, print the answer on a single line.
Example 1