XOR보나치 수열

마린은 파리를 잡겠다고 라켓을 너무 세게 휘두르다 팔꿈치를 다쳤다. 할머니는 약초를 바르라고 했고 의사는 진통제를 처방했지만, 마린은 둘 다 무시하고 정수 수열에서 답을 찾기로 했다.

마린은 새 수열을 하나 만들고 XOR보나치 수열이라고 이름 붙였다. 이 수열의 $n$번째 항을 $x_n$이라 하고, 다음과 같이 정의한다.

• $x_1 = a_1$
• $x_2 = a_2$
• $\dots$
• $x_k = a_k$
• $n > k$이면 $x_n = x_{n-1} \oplus x_{n-2} \oplus \dots \oplus x_{n-k}$

마린은 질문 $Q$개의 답을 받으면 아픔이 사라진다고 한다. 각 질문은 두 수 $l$과 $r$로 주어지고, 답은 다음 값이다.

$x_l \oplus x_{l+1} \oplus \dots \oplus x_{r-1} \oplus x_r$

여기서 $\oplus$는 비트 단위 XOR 연산이다.

첫째 줄에 정수 $K$가 주어진다 ($1 \le K \le 100\,000$).

둘째 줄에 XOR보나치 수열의 처음 $K$개 항이 주어진다. 각 값은 $10^{18}$보다 작은 음이 아닌 정수이다.

셋째 줄에 정수 $Q$가 주어진다 ($1 \le Q \le 10^6$).

이어지는 $Q$개의 줄 중 $i$번째 줄에는 $i$번째 질문을 나타내는 두 정수 $l_i$와 $r_i$가 주어진다 ($1 \le l_i \le r_i \le 10^{18}$).

$Q$개의 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 질문의 답을 출력한다.