P9580 "Cfz Round 1" Wqs Game

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

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.

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.

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

#### 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