题目背景

『博』和『奕』喜欢博弈，尤其喜欢 wqs 带权博弈。

题目描述

wqs 带权博弈在一个数列 $\{a_i\}$ 上进行，对应有一个 $01$ 串 $\{b_i\}$。

1. 若 $b_i=0$，则 $a_i$ 这个数字是属于『博』的；
2. 若 $b_i=1$，则 $a_i$ 这个数字是属于『奕』的。

游戏规则是，每次给定一个区间 $[l,r]$，从 $a_l$ 到 $a_r$，拥有这个数的人依次决定选该数或者不选，两个人都会采用最优策略。

因为『博』很强大，她会让着『奕』，于是博弈的规则是，如果最后两个人选的数按位异或和不为零，则『奕』获胜，否则『博』获胜。

注意每个人能看到对方的选数情况，可以选多个数（只要这个数是自己的），最后计算两个人选数的总异或和。

对于任意区间 $[l,r]$，若『奕』获胜，则 $w(l,r)=1$，否则 $w(l,r)=0$。

每次查询 $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 的值，对 $2^{32}$ 取模。

由于输入输出量过大，对于 $tp\ne 0$ 的测试点，选手需要自行生成数列 $a_i$ 和询问区间 $[L,R]$，并用特殊方式输出答案。

注意正解不依赖特殊的输入输出方式。

输入格式

第一行三个正整数 $n,q,tp$，表示数列长度，天数以及每天局数，以及读入方式。

第二行一个长度为 $n$ 的字符串，表示 $01$ 串 $\{b_i\}$；

若 $tp=0$，则第三行 $n$ 个正整数，表示数列 $\{a_i\}$，接下来 $q$ 行，每行两个正整数 $L,R$，表示询问 $\sum\limits_{l=L}^R\sum\limits_{r=l}^Rw(l,r)$ 对 $2^{32}$ 取模的值。

否则，令 Sd 初值为 $tp$，Cnt 初值为 $0$，先使用函数 GetA 依次生成 $a_i$，再使用函数 GetLR 依次生成 $L,R$，具体方式以代码形式后附。

输出格式

若 $tp=0$ 则输出 $q$ 行，每行一个正整数，表示该询问的答案。

否则，令 $ans_i$ 为第 $i$ 次询问的答案，你需要输出 $(ans_i\times i)\bmod 2^{32}$ 的按位异或和。

样例 1 输入

3 2 0
100
3 1 2
1 3
2 3

样例 1 输出

2
0

样例 1 解释

只有 $w(1,1)=w(1,2)=1$。

对于区间 $[1,3]$，如果『奕』选第一个数，则『博』选后两个数，否则『博』不选，于是『博』获胜。

注意是从左往右依次选取，『博』在选后两个数之前能够知道『奕』是否选了第一个数。

样例 2 输入

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

样例 2 输出

8
4

样例 2 解释

只有 $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$。

样例 3 输入

20 100 8551679995685981130
11001000000000000000

样例 3 输出

1673

样例 3 解释

由于本样例 $tp\ne 0$，所以你需要使用特殊方式输入输出。

数据范围

对于所有数据，$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}$。

特殊性质：序列 $b_i$ 中最多有 $10$ 个 $0$。

备注

数据生成方式：

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