월쉬 행렬

월쉬 행렬(Walsh matrix)은 크기가 2의 거듭제곱인 정사각 행렬로, 모든 원소가 $+1$ 또는 $-1$인 행렬이다.

이 행렬의 가장 큰 특징은 서로 다른 두 행(또는 서로 다른 두 열)의 스칼라 곱, 즉 같은 위치의 원소끼리 곱해 모두 더한 값이 항상 $0$이라는 점이다.

크기가 $1$인 월쉬 행렬은 원소가 하나뿐이며 그 값은 $+1$이다. 크기가 $2^{N+1}$인 월쉬 행렬은 크기가 $2^N$인 월쉬 행렬 $H_N$ 네 개를 이어 붙여 만든다.

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

즉 왼쪽 위, 오른쪽 위, 왼쪽 아래 세 블록에는 $H_N$을 그대로 넣고, 오른쪽 아래 블록에는 모든 원소의 부호를 뒤집은 $-H_N$을 넣는다.

행 번호는 위에서부터 $0, 1, 2, \dots$로, 열 번호는 왼쪽에서부터 $0, 1, 2, \dots$로 매긴다. 정수 $N, R, S, E$가 주어질 때, 크기가 $2^N$인 월쉬 행렬에서 $R$행의 $S$열부터 $E$열까지의 원소를 모두 더한 값을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 네 정수 $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$)

마지막 줄에는 $-1$이 네 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 구한 합을 한 줄에 하나씩 출력한다.