相信你也和 O i e r Oier Oier- K r y Kry Kry 一样，码了几行代码，就轻松搞定其等价电阻的值。 K r y Kry Kry 忽然间意识到不能总是不干正经事，联赛马上就来了， 该整理下 U U U 盘，好好复习总结下，于是插上 U U U 盘，开始翻阅以前学习的资料。 由于前面的更换教室地板，再加上刚才解决电路连接问题， K r y Kry Kry 有点累了，不知道哪里来的困意，在学习压力这么大的情况下，居然不知不觉的睡着了 K r y Kry Kry 在梦里回到了初中时代， 仿佛感觉好像是 Mir.Z 在教室前面讲解联赛的题目，但又感觉不是，这个梦怎么这么不真实。 难道 M i r . Z Mir.Z Mir.Z 讲的题目和今年联赛有关， K r y Kry Kry 努力的回想着。由于 K r y Kry Kry 想让梦境清晰一点，着急的一下子从梦里惊醒了。 隐约只记得 M i r . Z Mir.Z Mir.Z 所讲的题目大概，具体描述如下： 有一个整数序列，暂且将其称为 X O R b o n a c c i XORbonacci XORbonacci 序列。序列中的第 N N N 个元素用 X N X_N XN表示。该序列按照以下方式递归定义： X 1 X_1 X1 = = = X 1 X_1 X1 ， X 2 X_2 X2 = = = X 2 X_2 X2 ， … … …… …… X K X_K XK = = = X K X_K XK ； X N X_N XN = = = X N − 1 X_{N-1} XN−1 ⨁ \bigoplus ⨁ X N − 2 X_{N-2} XN−2 ⨁ \bigoplus ⨁ … … …… …… ⨁ \bigoplus ⨁ X N − K X_{N-K} XN−K ( N ＞ k ) (N＞k) (N＞k) Mir.Z 将会提出 Q 次询问，每次询问给出两个整数 L 和 R。而每次询问的答案即以下式子的值： X L X_L XL ⨁ \bigoplus ⨁ X L + 1 X_{L+1} XL+1 ⨁ \bigoplus ⨁ … … …… …… ⨁ \bigoplus ⨁ X R − 1 ⨁ X R X_{R-1}\bigoplus X_R XR−1⨁XR。注意：题目中的符号" ⨁ \bigoplus ⨁"在 K r y Kry Kry 的梦里应该是 X O R XOR XOR 异或。( P S ： P a s c a l PS：Pascal PS：Pascal 语言异或运算符是 x o r xor xor， C C C 语言或者 C + + C++ C++ 语言异或运算符是 ^) O i e r Oier Oier 们抓紧解决这个小题吧，万一联赛要是真的出呢？那岂不是赚到了。
第 1 行输入包含一个整数 k k k； 接下来的一行包含 k k k 个整数，第 i i i个整数 A i A_i Ai 表示 X O R b o n a c c i XORbonacci XORbonacci 序列中的第 i i i 个元素； 接下来一行包含一个整数 Q Q Q； 接下来的 Q Q Q 行，每行包含两个整数 L i L_i Li和 R i R_i Ri，表示 M i r . Z Mir.Z Mir.Z 第 i i i 次询问的下标区间；
输出共 Q Q Q 行，第 i 行输出 M i r . Z Mir.Z Mir.Z 的第 i i i 次询问的结果。
对于 30%的数据： 1 ≤ k ≤ 5000 , 1 ≤ Q ≤ 5000 , 1 ≤ L i ≤ R i ≤ 5000 , 1 ≤ A i ≤ 5000 1≤k≤5000 ,1≤Q≤5000, 1≤L_i≤R_i≤5000, 1≤A_i≤5000 1≤k≤5000,1≤Q≤5000,1≤Li≤Ri≤5000,1≤Ai≤5000； 对于 50%的数据： 1 ≤ k ≤ 100000 , 1 ≤ Q ≤ 100000 , 1 ≤ L i ≤ R i ≤ 500000 , 1 ≤ A i ≤ 5000 1≤k≤100000 ,1≤Q≤100000, 1≤L_i≤R_i≤500000, 1≤A_i≤5000 1≤k≤100000,1≤Q≤100000,1≤Li≤Ri≤500000,1≤Ai≤5000； 对于 100%的数据： 1 ≤ k ≤ 100000 , 1 ≤ Q ≤ 100000 , 1 ≤ L i ≤ R i ≤ 1 0 18 , 1 ≤ A i ≤ 1 0 18 1≤k≤100000, 1≤Q≤100000, 1≤L_i≤R_i≤10^{18}, 1≤A_i≤10^{18} 1≤k≤100000,1≤Q≤100000,1≤Li≤Ri≤1018,1≤Ai≤1018；
知识导入-前缀和(by 不想悲伤到天明) 根据同理，可以推出一个异或前缀数组：
前缀和异或前缀和根据 ∑ i = 1 n a i \sum\limits_{i=1}^{n}{a_i} i=1∑nai ∑ i = 1 n ⨁ a i \sum\limits_{i=1}^{n}{\bigoplus a_i} i=1∑n⨁ai可推出 ∑ i = 1 n a i = ∑ i = 1 n − 1 a i + a n \sum\limits_{i=1}^{n}{a_i} = \sum\limits_{i=1}^{n-1}{a_i}+a_n i=1∑nai=i=1∑n−1ai+an ∑ i = 1 n ⨁ a i = ∑ i = 1 n − 1 ⨁ a i + a n \sum\limits_{i=1}^{n}{\bigoplus a_i} = \sum\limits_{i=1}^{n-1}{\bigoplus a_i}+a_n i=1∑n⨁ai=i=1∑n−1⨁ai+an求区间 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i \sum\limits_{i=1}^{r}{a_i}-\sum\limits_{i=1}^{l-1}{a_i} i=1∑rai−i=1∑l−1ai ∑ i = 1 r ⨁ a i ⨁ ∑ i = 1 l − 1 ⨁ a i {\sum\limits_{i=1}^{r}{\bigoplus a_i} }\bigoplus {\sum\limits_{i=1}^{l-1}{\bigoplus a_i}} i=1∑r⨁ai⨁i=1∑l−1⨁ai本来可以直接维护一个异或前缀数组的，但是 1 ≤ L i ≤ R i ≤ 1 0 18 1≤L_i≤R_i≤10^{18} 1≤Li≤Ri≤1018 所以我们要看看有没有规律： 因为我们知道 n ⨁ n = 0 n\bigoplus n=0 n⨁n=0且 X N X_N XN = = = X N − 1 X_{N-1} XN−1 ⨁ \bigoplus ⨁ X N − 2 X_{N-2} XN−2 ⨁ \bigoplus ⨁ … … …… …… ⨁ \bigoplus ⨁ X N − K X_{N-K} XN−K ( N ＞ k ) (N＞k) (N＞k) 所以可以推出 ∑ i = 1 k + 1 ⨁ a i = ∑ i = 0 0 ⨁ a i \sum\limits_{i=1}^{k+1}{\bigoplus a_i}=\sum\limits_{i=0}^{0}{\bigoplus a_i} i=1∑k+1⨁ai=i=0∑0⨁ai也就是 0 0 0； 接下来也可以看出
∑ i = 1 k + 1 ⨁ a i = ∑ i = 1 0 ⨁ a i \sum\limits_{i=1}^{k+1}{\bigoplus a_i}=\sum\limits_{i=1}^{0}{\bigoplus a_i} i=1∑k+1⨁ai=i=1∑0⨁ai ∑ i = 1 k + 2 ⨁ a i = ∑ i = 1 1 ⨁ a i \sum\limits_{i=1}^{k+2}{\bigoplus a_i}=\sum\limits_{i=1}^{1}{\bigoplus a_i} i=1∑k+2⨁ai=i=1∑1⨁ai ∑ i = 1 k + 3 ⨁ a i = ∑ i = 1 2 ⨁ a i \sum\limits_{i=1}^{k+3}{\bigoplus a_i}=\sum\limits_{i=1}^{2}{\bigoplus a_i} i=1∑k+3⨁ai=i=1∑2⨁ai…… ∑ i = 1 k + X ⨁ a i = ∑ i = 1 ( k + x ) % ( K + 1 ) ⨁ a i \sum\limits_{i=1}^{k+X}{\bigoplus a_i}=\sum\limits_{i=1}^{(k+x)\%(K+1)}{\bigoplus a_i} i=1∑k+X⨁ai=i=1∑(k+x)%(K+1)⨁ai