Walsh Matrix

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$.

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.

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