Fiboxor

리틀 스퀘어와 리틀 트라이앵글이 올해도 밸런타인데이에 다투고 있다. 이번 싸움의 원인은 리틀 스퀘어가 리틀 트라이앵글이 좋아하는 2의 거듭제곱 수열보다 피보나치 수열이 훨씬 예쁘다고 주장했기 때문이다.

피보나치 수열은 0과 1로 시작하고, 그 뒤의 각 원소는 바로 앞의 두 원소의 합이다.

$0, 1, 1, 2, 3, 5, 8, 13, \dots$

리틀 트라이앵글은 임의의 부분 배열의 비트별 XOR(XOR)을 쉽게 계산할 수 있어서 이 수열을 좋아한다. 리틀 트라이앵글은 리틀 스퀘어가 XOR 부분 배열 질의 $Q$개에 정확히 답하면 피보나치 수열이 더 낫다는 사실을 인정하겠다고 말했다. 피보나치 수는 지수적으로 커지기 때문에, 리틀 트라이앵글은 각 부분 배열 XOR 값을 $2^k$로 나눈 나머지만 알려 주는 데 동의했다.

$Q$개의 질의는 각각 정수 $k$, $l$, $r$로 주어진다. 각 질의마다 인덱스가 $0$부터 시작하는 구간 $[l, r]$(양 끝 포함)에 있는 피보나치 수들의 XOR을 구하고, 그 값을 $2^k$로 나눈 나머지를 구하라.

• $1 \le Q \le 10^6$
• $0 \le l \le r \le 10^{18}$
• $1 \le k \le 20$

$a \oplus b$는 $a$와 $b$의 XOR을 뜻한다.

첫 번째 질의에서는 $0 \oplus 1 \oplus 1 \oplus 2 \mod 2^2 = 2 \mod 4 = 2$이다.

두 번째 질의에서는 $3 \oplus 5 \oplus 8 \mod 2^4 = 14 \mod 16 = 14$이다.