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

Added by:Ahmed Aly
Date:2009-07-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2008

hide comments
2009-07-09 13:14:52 Seckin Can Sahin
limits are correct. and also it is true that 0 <= S <= E < 2^N.

there are ~1000 test cases in one file(in official I/O), this is why O(n*(E-S)) can't pass. It should have been said in constraints.
2009-07-08 17:49:53 Dominik Kempa
I suppose the limits aren't correct, shouldn't there be 0 <= S <= E < 2^N ?
2009-07-05 07:22:41 Robert Gerbicz
My O(E-S+N) algorithm pass the problem.

Last edit: 2009-07-05 07:23:01
2009-07-05 02:57:49 [Trichromatic] XilinX
Time limit too strict!

Edit: I do think an algorithm with complexity O(n*(E-S)) per test should pass, even though my algorithm has comlexity O(n) per test.

Edit: If you want to reject programs with complexity O(n*(E-S)), you should cancel the condition E-S<=10000.

Last edit: 2009-07-05 03:26:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.