Walsh Matrix

Time limit1sMemory limit128 MB

Summary

Sum entries in one row of a Walsh matrix over columns S through E, where the matrix size 2^N can reach 2^60.

Level: Medium7 of 10
Topics: Divide and conquer, Recursion, Math, Bit manipulation
Solved: No attempts yet

Problem

A Walsh matrix is a square matrix whose size is a power of two and whose every entry is either $+1$ or $-1$ .

Its defining property is that the scalar (dot) product of any two distinct rows (or of any two distinct columns) — the sum of the products of entries at matching positions — is always $0$ .

The Walsh matrix of size $1$ has a single entry equal to $+1$ . The Walsh matrix of size $2^{N+1}$ is built from four copies of the Walsh matrix $H_N$ of size $2^N$ :

$H_{N+1} = \begin{pmatrix} H_N & H_N \\ H_N & -H_N \end{pmatrix}$

That is, the top-left, top-right, and bottom-left blocks each hold $H_N$ unchanged, while the bottom-right block holds $-H_N$ , the same matrix with every entry's sign flipped.

Rows are numbered $0, 1, 2, \dots$ from top to bottom, and columns $0, 1, 2, \dots$ from left to right. Given integers $N, R, S, E$ , write a program that computes the sum of the entries in row $R$ , from column $S$ through column $E$ , of the Walsh matrix of size $2^N$ .

Input

The input consists of several test cases. Each test case is a single line with four integers $N, R, S, E$ . ( $0 \le N \le 60$ , $0 \le R < 2^N$ , $0 \le S \le E < 2^N$ , $E - S \le 10{,}000$ )

The last line contains four $-1$ values and must not be processed.

Output

For each test case, print the computed sum on its own line.

Examples1

Example 1
Input
```
2 1 0 1
48 0 0 47
-1 -1 -1 -1
```
Expected output
```
0
48
```