cho.sh

XOR보나치 수열

앞 K개 항으로 정의된 XOR 점화식에서 구간 [l, r]의 XOR을 묻는 질의를 대량으로 처리합니다.

보통6수학누적 합비트 연산아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

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

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

  • x1=a1x_1 = a_1
  • x2=a2x_2 = a_2
  • …\dots
  • xk=akx_k = a_k
  • n>kn > k이면 xn=xn−1⊕xn−2⊕⋯⊕xn−kx_n = x_{n-1} \oplus x_{n-2} \oplus \dots \oplus x_{n-k}

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

xl⊕xl+1⊕⋯⊕xr−1⊕xrx_l \oplus x_{l+1} \oplus \dots \oplus x_{r-1} \oplus x_r

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

입력

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

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

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

이어지는 QQ개의 줄 중 ii번째 줄에는 ii번째 질문을 나타내는 두 정수 lil_i와 rir_i가 주어진다 (1≤li≤ri≤10181 \le l_i \le r_i \le 10^{18}).

출력

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