Problem Background

『博』和『奕』喜欢 playing games of strategy, especially wqs weighted games of strategy.

Problem Description

The wqs weighted game of strategy is played on a sequence $\{a_i\}$ with a corresponding binary string $\{b_i\}$.

1. If $b_i=0$, then the number $a_i$ belongs to『博』;
2. If $b_i=1$, then the number $a_i$ belongs to『奕』.

The rules of the game are as follows: Each time an interval $[l,r]$ is given, from $a_l$ to $a_r$, the person who owns the number decides whether to take it or not in turn, and both will use the optimal strategy.

Since『博』is very powerful, she will let『奕』, so the rule of the game is that if the bitwise XOR sum of the numbers chosen by both is not zero, then『奕』wins, otherwise『博』wins.

Note that each person can see the other's selection, can choose multiple numbers (as long as the number is their own), and finally calculate the total XOR sum of the numbers chosen by both.

For any interval $[l,r]$, if『奕』wins, then $w(l,r)=1$, otherwise $w(l,r)=0$.

Each query asks for the value of $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ modulo $2^{32}$.

Due to the large amount of input and output, for test points where $tp\ne 0$, the player needs to generate the sequence $a_i$ and the query intervals $[L,R]$ themselves and output the answer in a special way.

Note that the correct solution does not depend on the special input and output method.

Input Format

The first line contains three positive integers $n, q, tp$, representing the length of the sequence, the number of days, and the number of games per day, as well as the input method.

The second line is a string of length $n$, representing the binary string $\{b_i\}$;

If $tp=0$, the third line contains $n$ positive integers, representing the sequence $\{a_i\}$, followed by $q$ lines, each containing two positive integers $L, R$, representing the query for $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ modulo $2^{32}$.

Otherwise, let Sd initially be $tp$ and Cnt initially be $0$. First, use the function GetA to generate $a_i$ sequentially, then use the function GetLR to generate $L, R$ sequentially, with the specific method appended in code form.

Output Format

If $tp=0$, output $q$ lines, each containing a positive integer, representing the answer to that query.

Otherwise, let $ans_i$ be the answer to the $i$-th query. You need to output the bitwise XOR sum of $(ans_i \times i) \bmod 2^{32}$.

Sample Input and Output

Sample Input #1

3 2 0
100
3 1 2
1 3
2 3

Sample Output #1

2
0

Sample Input #2

5 2 0
10100
2 7 6 3 5
1 5
2 4

Sample Output #2

8
4

Sample Input #3

20 100 8551679995685981130
11001000000000000000

Sample Output #3

1673

Notes/Hints

Sample Explanation #1

Only $w(1,1)=w(1,2)=1$.

For the interval $[1,3]$, if『奕』takes the first number, then『博』takes the last two numbers, otherwise『博』does not take any, so『博』wins.

Note that the selection is made from left to right, and『博』knows whether『奕』has taken the first number before taking the last two.

Sample Explanation #2

Only $w(1,1)=w(1,2)=w(1,3)=w(1,4)=w(2,3)=w(2,4)=w(3,3)=w(3,4)=1$.

Sample Explanation #3

Since $tp\ne 0$ for this sample, you need to use the special input and output method.

Data Range

For all data, $1 \le n \le 5 \times 10^5, 1 \le q \le 1.5 \times 10^6, 0 < a_i < 2^{60}, 1 \le L \le R \le n, 0 \le tp < 2^{64}$.

Special Property: The sequence $b_i$ contains at most 10 zeros.

Remarks

Data generation method:

using ul=unsigned long long;
using ui=unsigned int;
ui Ans,ans;
ul Sd,Cnt;
ul Rd(){Sd^=Sd<<19,Sd^=Sd>>12,Sd^=Sd<<29;return Sd^=++Cnt;}
void GetA(ul &a){a=Rd()%((1ull<<60)-2)+1;}
void GetLR(int &l,int &r){
    l=Rd()%n+1,r=Rd()%n+1;
    if(l>r)swap(l,r);
}
int main(){
    //read n,q,tp,b[i]
    if(tp){
        Sd=tp,Cnt=0;
        for(int i=1;i<=n;++i)GetA(a[i]);
        for(int qi=1;qi<=q;++qi){
            GetLR(l,r);
            //sol
            Ans^=ans*qi;
        }
        printf("%u\n",Ans);
    }
}

见题面 Input 部分

见题面 Output 部分