ANARC08I  I Speak Whales
According to Wikipedia, a Walsh matrix is a specific square matrix, with dimensions equal to a power of 2, the entries of which are +1 or 1, and the property that the dot product of any two distinct rows (or columns) is zero. Below are the first three Walsh Matrices. (The gray lines are imaginary lines for illustration purpose only.)
A Walsh Matrix of size 2^(N+1) can be constructed as the "union" of 4 Walsh Matrices of size 2^N arranged such that the lower right matrix is inverted whereas the other 3 matrices are not, i.e.:
Let's number the rows of a given Walsh Matrix from the top starting with row 0. Similarly, let's number the columns of the matrix from the left starting with column 0. Given the four integers N , R , S , and E , write a program that will construct a Walsh Matrix of size 2^N and will print the sum of all the numbers in row #R between columns #S and #E (inclusive.)
Input
Your program will be tested on one or more test cases. Each test case is specified using a single line listing four integers in the following order: N , R , S , and E , where 0 <= N <= 60 , 0 <= R < 2^N , 0 <= S <= E < 2N , and E  S <= 10,000 . The last line of the input file has four 1's and is not part of the test cases.
Output
For each test case, print the output on a single line.
Example
Input: 2 1 0 1 48 0 0 47 1 1 1 1 Output: 0 48
hide comments
Seckin Can Sahin:
20090709 13:14:52
limits are correct. and also it is true that 0 <= S <= E < 2^N.


Dominik Kempa:
20090708 17:49:53
I suppose the limits aren't correct, shouldn't there be 0 <= S <= E < 2^N ? 

Robert Gerbicz:
20090705 07:22:41
My O(ES+N) algorithm pass the problem. Last edit: 20090705 07:23:01 

[Trichromatic] XilinX:
20090705 02:57:49
Time limit too strict!

Added by:  Ahmed Aly 
Date:  20090704 
Time limit:  0.461s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ANARC 2008 