26483번 - Fiboxor 서브태스크다국어언어 제한함수 구현

문제

Little Square and Little Triangle are having a fight on Valentine’s day again! The reason of this year’s fight? Little Square has said that the Fibonacci sequence is way prettier than the sequence of powers of two (Little Triangle’s favorite). Recall that the Fibonacci sequence is the sequence that begins with 0 and 1, and where subsequent elements are the sum of the two previous elements:

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

Little Triangle likes this sequence particularly because you can easily calculate the bitwise exclusive or (XOR) of any subarray. Thus they told Little Square that if they can successfully answer $Q$ such XOR subarray queries, then they will accept the fact that Fibonacci is better. Little Triangle isn’t cruel though, so they agreed to let Little Square tell them only the value of the subarray XOR modulo 2ドル^k$ each query, due to the fact that the Fibonacci sequence grows exponentially.

In the end, Little Square has to answer $Q$ queries, each of which contains three integers $k,ドル $l,ドル $r$. This query asks us to calculate the XOR of the Fibonacci numbers with indexes in the interval $[l, r]$ inclusive, indexed from 0ドル,ドル modulo 2ドル^k$.

Little Square asks for your help in order to win this argument, so they can go back at having a good time on Valentine’s day.

인터랙션 프로토콜

The contestant must implement two functions, init and query, with the following signature.

void init(int q);
int query(int k, long long l, long long r);

The first function will be called by the committee exactly once, before any calls to query, and will be supplied the value of $Q$. The second function must answer the query determined by integers $k,ドル $l,ドル $r,ドル and return the answer. It will be called at most $Q$ times by the grader.

입력

출력

제한

• 1ドル ≤ Q ≤ 10^6$
• 0ドル ≤ l ≤ r ≤ 10^{18}$
• 1ドル ≤ k ≤ 20$

서브태스크

노트

Let $a ⊕ b$ denote the XOR of $a$ and $b$.

In the first query, 0ドル ⊕ 1 ⊕ 1 ⊕ 2 \mod 2^2 = 2 \mod 4 = 2$.

In the second query, 3ドル ⊕ 5 ⊕ 8 \mod 2^4 = 14 \mod 16 = 14$.