Background

"Bo" and "Yi" enjoy games, especially wqs-weighted games.

Description

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

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

The rules of the game are as follows: for a given interval $[l,r]$, from $a_l$ to $a_r$, the person who owns the number decides sequentially whether to select it or not. Both players use optimal strategies.

Because "Bo" is very powerful, she lets "Yi" win; thus, the rule of the game is that if the bitwise XOR sum of the numbers selected by the two players is non-zero, "Yi" wins; otherwise, "Bo" wins.

Note that each person can see the choices made by the other, and they can choose multiple numbers (as long as the number belongs to them). The final result is calculated based on the total XOR sum of the numbers selected by both players.

For any interval $[l,r]$, if "Yi" wins, $w(l,r)=1$; otherwise, $w(l,r)=0$.

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

Due to the large volume of input and output, for test cases where $tp\ne 0$, participants must generate the sequence $a_i$ and the query intervals $[L,R]$ themselves and output the answer using a specific method.

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

Input

The first line contains three positive integers $n, q, tp$, representing the length of the sequence, the number of queries, and the input method indicator.

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

If $tp=0$, the third line contains $n$ positive integers, representing the sequence $\{a_i\}$. The following $q$ lines each contain two positive integers $L, R$, representing the query for the value of $\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, use the function GetA to generate $a_i$ sequentially, then use the function GetLR to generate $L, R$ sequentially. The specific method is provided in the code below.

Output

If $tp=0$, output $q$ lines, each containing a positive integer representing the answer to the corresponding 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}$.

Examples

Input 1

3 2 0
100
3 1 2
1 3
2 3

Output 1

2
0

Note 1

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

For the interval $[1,3]$, if "Yi" selects the first number, "Bo" selects the next two numbers; otherwise, "Bo" selects nothing, and "Bo" wins.

Note that the selection is made sequentially from left to right, and "Bo" knows whether "Yi" has selected the first number before choosing the next two.

Input 2

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

Output 2

8
4

Note 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$.

Input 3

20 100 8551679995685981130
11001000000000000000

Output 3

1673

Note 3

Since $tp\ne 0$ in this example, you must 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: The sequence $b_i$ contains at most $10$ zeros.

Note

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