Background

"Bo" and "Yi" like playing games, and they especially like the wqs weighted game.

Problem Description

The wqs weighted game is played on a sequence $\{a_i\}$, with a corresponding $01$ string $\{b_i\}$.

1. If $b_i=0$, then the number $a_i$ belongs to "Bo".
2. If $b_i=1$, then the number $a_i$ belongs to "Yi".

The rules are: each time, an interval $[l,r]$ is given. From $a_l$ to $a_r$, the owner of each number decides in order whether to pick it or not. Both players use an optimal strategy.

Because "Bo" is very strong, she yields to "Yi". Therefore, the rule is: if the bitwise XOR sum of the numbers finally chosen by the two players is non-zero, then "Yi" wins; otherwise, "Bo" wins.

Note that each player can see what the other has chosen. A player may choose multiple numbers (as long as the number belongs to them). In the end, compute the total XOR sum of all numbers chosen by both players.

For any interval $[l,r]$, if "Yi" 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)$, taken modulo $2^{32}$.

Because the input/output is too large, for test points with $tp\ne 0$, contestants need to generate the sequence $a_i$ and query intervals $[L,R]$ by themselves, and output the answers in a special way.

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

Input Format

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

The second line contains a string of length $n$, representing the $01$ string $\{b_i\}$.

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

Otherwise, let the initial value of Sd be $tp$, and the initial value of Cnt be $0$. First generate $a_i$ in order using the function GetA, then generate $L,R$ in order using the function GetLR. The specific method is given in the code below.

Output Format

If $tp=0$, output $q$ lines, each containing one 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}$.

3 2 0
100
3 1 2
1 3
2 3

2
0

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

8
4

20 100 8551679995685981130
11001000000000000000

1673

Hint

Sample Explanation #1

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

For the interval $[1,3]$, if "Yi" chooses the first number, then "Bo" chooses the last two numbers; otherwise, "Bo" chooses nothing, so "Bo" wins.

Note that choices are made from left to right. Before choosing the last two numbers, "Bo" can know whether "Yi" has chosen the first number.

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$ in this sample, you need to use the special input/output method.

Constraints

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

Special Property: in the sequence $b_i$, there are at most $10$ zeros.

Notes

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);
	}
}

Translated by ChatGPT 5