Description
你有一张 n 个点,m 条边的有向图,且每个点拥有一个权值 vali 。不存在一条边两端连向
同一个点,可能存在两条边两端连接的点分别相同。我们定义 u 能直接到达 v , 当且仅当有 u 直接连向 v 的边。
现在有 q 个询问,每次询问给出一个区间 [L,R],你可以选择该区间内的一个点作为中
心点。一个点能作为中心点的条件是:这个点能直接到达的点不在区间 [L,R] 之间。
现在,对于每个询问,你需要输出询问区间内所有可以作为中心点的点的权值之和。
第 1 行 3 个由空格隔开的正整数 n,m,q, 分别表示点的个数、有向边的个数和询问的个数。
第 2 行 n 个由空格隔开的正整数,第 i 个数 vali表示第 i 个点的权值。
接下来 m 行,每行两个由空格隔开的正整数 ui,vi, 表示一条从 ui 到 vi 的有向边。
接下来 q 行,每行两个由空格隔开的正整数 Li,Ri, 表示一个询问 [Li,Ri]。
Output
为了减少输出量,设 ansi 为第 i 个询问的答案。你只需要输出一行一个整数 xori=1qi×ansi,即所有询问的编号与答案的乘积异或起来的值。
Samples
4 2 2
3 5 10 6
1 4
2 3
2 3
1 3
16
Limitation
对于 10 的数据,n,q⩽300 。
对于 30 的数据,n,q⩽10000 。
对于 60 的数据,n,q⩽100000。
对于另外 20 的数据,m=n−1, 图是一条链。
对于 100 的数据, n,q⩽500000,m⩽min(n×(n−1)/2,500000),1⩽vali⩽300,1⩽ui,vi⩽n,ui=vi,1⩽Li⩽Ri⩽n 。
Tips
建议使用快读