P9580 「Cfz Round 1」Wqs Game

『博』和『奕』喜欢博弈，尤其喜欢 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]$，并用特殊方式输出答案。 注意正解**不依赖**特殊的输入输出方式。

无

无

#### 【样例解释 #1】 只有 $w(1,1)=w(1,2)=1$。 对于区间 $[1,3]$，如果『奕』选第一个数，则『博』选后两个数，否则『博』不选，于是『博』获胜。 注意是从左往右依次选取，『博』在选后两个数之前能够知道『奕』是否选了第一个数。 #### 【样例解释 #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】 由于本样例 $tp\ne 0$，所以你需要使用特殊方式输入输出。 #### 【数据范围】 对于所有数据，$1\le n\le5\times10^5,1\le q\le 1.5\times10^6,0