P17630 安达与岛村
题目背景
她显得有些慌张。
「太，太好了」
「彼此都成了老婆婆，也许会偷偷觉得对方年轻的时候真好呢」
「我，不管你变成什么样子…… 我都，喜欢你」
「真的吗？那我现在变成老婆婆也可以吗？」
一阵深深的沉默。怎么看都是在认真的思考。她的正直和认真让我的眼梢舒缓了下来。
经过了花瓣积在脚下这么长的时间，一个羞涩的声音飘然传来。
「还是年轻的样子就好……」
「果然是这样啊」
「我也这样想」
我笑道。对方也像被吸引似的抬起头，安心地笑了。
两人相视而笑，突然，喉咙和眼睛在颤抖。
「又见到你了」
无法判断这句话是谁说的。
无论对于谁都是真心话。
不论是声音、语言，还是交谈过的一切，都让人觉得痒痒的。
不在记忆中的场所也没关系。
因为可以再次一起去任何地方。
「安达」 与 「岛村」
去大海吧。
海？
因为有了船，所以哪里都能去哦。
嗯，走吧。
无论去哪里，都是两人一起。
题目描述
岛村给了你一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$。
这个序列上经过了 $m$ 个时刻。在其中第 $i$ 个时刻，给定两个整数 $l_i,r_i$，然后 $a_{l_i},a_{l_i+1}\cdots , a_{r_i}$ 全部分别变为了其在模 $200003$ 意义下的乘法逆元。
记 $f_t(R)$ 为在第 $t$ 个时刻结束时 $a_1,a_2,\cdots ,a_{R}$ 中不同数的个数。
岛村现在有 $q$ 次询问，其中第 $j$ 次询问给定 $x_j,y_j$。请你求出 $\sum _{r=1}^{x_j}\limits\sum _{i=1}^{y_j}\limits f_{i}(r)$。
输入格式
由于读入量过大，本题采用下发数据生成器的方式输入。
```cpp
using namespace std;
const int N=2e5+3,Q=5e6+3;
int n,m,q,Amax,a[N];
int l[N],r[N],x[Q],y[Q];
unsigned sd,z1,z2,z3,z4;
unsigned rnd(){
sd=((z113,z1=((z1&4294967294U)sd>>Amax;
z1=sd,z2=(~sd)^0x233333333U;
z3=sd^0x1234598766U,z4=(~sd)+51;
for(int i=1;i
输出格式
由于输出量过大。你只需输出一个数，表示所有询问答案的按位异或和。
我们保证正解与此输出方式无关。
说明/提示
#### 样例解释：
对于样例一：
每个时刻变换为逆元的区间依次为 $[3,4],[1,5],[1,5],[4,5],[2,2]$。
各个时刻下的序列 $a$ 依次如下：
初始时：$[3,2,3,3,4]$。
第一次变化后：$[3,2,66668,66668,4]$。
第二次变化后：$[66668,100002,3,3,50001]$。
第三次变化后：$[3,2,66668,66668,4]$。
第四次变化后：$[3,2,66668,3,50001]$。
第五次变化后：$[3,100002,66668,3,50001]$。
各个 $f_t(R)$ 的值如下：
$f_1(1)=1,f_1(2)=2,f_1(3)=3,f_1(4)=3,f_1(5)=4,$
$f_2(1)=1,f_2(2)=2,f_2(3)=3,f_2(4)=3,f_2(5)=4,$
$f_3(1)=1,f_3(2)=2,f_3(3)=3,f_3(4)=3,f_3(5)=4,$
$f_4(1)=1,f_4(2)=2,f_4(3)=3,f_4(4)=3,f_4(5)=4,$
$f_5(1)=1,f_5(2)=2,f_5(3)=3,f_5(4)=3,f_5(5)=4$。
各询问参数与答案如下：
第一次询问：$x_1=1,y_1=3$，答案为 $3$。
第二次询问：$x_2=4,y_2=2$，答案为 $18$。
第三次询问：$x_3=4,y_3=4$，答案为 $36$。
第四次询问：$x_4=5,y_4=1$，答案为 $13$。
第五次询问：$x_5=3,y_5=2$，答案为 $12$。
所以输出 $3 \oplus 18 \oplus 36 \oplus 13 \oplus 12=52$。
---
#### 数据范围：
**本题目采用子任务捆绑测试。**
对于所有数据：$1 \le n \le 2 \times 10^5$，$1 \le m \le 2 \times 10^4$，$1 \le q \le 5 \times 10^6$。
- $\forall 1 \le i \le n$，有 $1 \le a_i < 200003$。
- $\forall 1 \le j \le m$，有 $1 \le l_j \le r_j \le n$。
- $\forall 1 \le k \le q$，有 $1 \le x_k \le n$，$1 \le y_k \le m$。
::cute-table{tuack}
| 子任务编号 | $n=$ | $m=$ | $q=$ | 分值 | 时间限制 |
|:-:|:-:|:-:|:-:|:-:| :-:|
| $0$ | $10$ | $10$ | $10$ | $5$ | $1$ 秒 |
| $1$ | $5000$ | $5000$ | $5000$ | ^ | ^ |
| $2$ | $10^4$ | $10^4$ | $10^4$ | ^ | ^ |
| $3$ | ^ | ^ | $10^6$ | ^ | ^ |
| $4$ | $2 \times 10^5$ | ^ | $2 \times 10^5$ | $15$ | $3.5$ 秒 |
| $5$ | ^ | $2 \times 10^4$ | ^ | ^ |^ |
| $6$ | ^ | $10^4$ | $2 \times 10^6$ | ^ |^ |
| $7$ | ^ | $2 \times 10^4$ | ^ | ^ | ^ |
| $8$ | ^ | ^ | $5 \times 10^6$ | $20$ | ^ |