Comet OJ

C1099 [Contest #8]菜菜种菜

内存限制：256 MB 时间限制：2000 ms

题目描述

菜菜太菜，但他不想种菜。

有 $n$ 块土地，每块土地有一个菜值。它们之间有 $m$ 条小路，每条连接两块土地，小路只能单向通行，不存在一条小路两端连接同一块土地，但可能存在两条小路两端连接的土地分别相同。如果存在一条从土地 $u$ 到土地 $v$ 的小路，则称 $u$ 能直接到达 $v$。

菜菜可以购买一些土地，他必须在其中选择一块建造自己的家，所购买的剩下的土地都被作为菜地。因为菜菜不想种菜，所以他希望从他家能直接到达的土地中，一块菜地也没有（如果菜菜家不能直接到达任何一块土地，这也能满足他的愿望）。

菜菜提出了 $q$ 个问题，每个问题给出 $L,R$ ，询问如果他购买了第 $L$ 到第 $R$ 块之间的所有土地，那么所有满足他愿望的建造家的选址的菜值之和是多少？

注意，本题空间限制为128MB

P.S. 本题标算有使用读入优化，相关资讯可参考oi-wiki --- 读入、输出优化

输入格式

第 $1$ 行 $3$ 个由空格隔开的整数 $n,m,q$ ，分别表示土地的块数、小路的条数和问题的个数。

第 $2$ 行 $n$ 个由空格隔开的整数，第 $i$ 个数 $a_i$ 表示第 $i$ 块土地的菜值。

接下来 $m$ 行，每行 $2$ 个由空格隔开整数 $u_i,v_i$，表示第 $i$ 条小路从第 $u_i$ 块土地通向第 $v_i$ 块土地。

接下来 $q$ 行，每行 $2$ 个由空格隔开整数 $l_i,r_i$，表示菜菜第 $i$ 个问题中购买了 $[l_i,r_i]$ 中的所有土地。

  • $1\le n,m,q \le 10^6$
  • $1\le a_i\le 300$
  • $1\le u_i,v_i\le n,u_i\neq v_i$
  • $1\le l_i\le r_i\le n$。

输出

为了避免输出量过大，设 $ans_i$ 表示第 $i$ 个询问的答案。你只需要输出 $1$ 行 $1$ 个整数 ${\rm xor}_{i=1}^qi\times ans_i$，即所有询问的编号与答案的乘积依次按位异或 （c++中的64位整数^）的结果。

样例

样例输入 1

4 2 2
3 5 10 6
1 4
2 3
2 3
1 3

样例输出 1

16

样例输入 2

5 6 3
114 29 219 231 165
5 4
1 2
1 3
5 3
3 2
3 4
2 2
1 2
4 5

样例输出 2

658

提示

对于样例1：第 $1$ 次询问，$3$ 号土地不能直接到达任何土地，是满足要求的，而 $2$ 号土地能到达 $3$ 号土地，$3$ 在 $[2,3]$ 之内是菜地，不能满足要求，所以这次询问的答案为 $10$；第 $2$ 次询问，$1$ 号土地只能到达 $4$ 号土地，不在 $[1,3]$ 内，是满足要求的，$3$ 号土地仍然满足要求，所以这次询问的答案为 $13$。输出 $(1\times10){\rm xor} (2\times13)=16$ 。