Description

你有一张 $n$ 个点,$m$ 条边的有向图，且每个点拥有一个权值 $val_{i}$ 。不存在一条边两端连向 同一个点，可能存在两条边两端连接的点分别相同。我们定义 $u$ 能直接到达 $v$ , 当且仅当有 $u$ 直接连向 $v$ 的边。

现在有 $q$ 个询问，每次询问给出一个区间 $[L , R]$,你可以选择该区间内的一个点作为中 心点。一个点能作为中心点的条件是：这个点能直接到达的点不在区间 $[L , R]$ 之间。 现在，对于每个询问，你需要输出询问区间内所有可以作为中心点的点的权值之和。

Format

Input

第 1 行 3 个由空格隔开的正整数 $n, m, q ,$ 分别表示点的个数、有向边的个数和询问的个数。

第 2 行 $n$ 个由空格隔开的正整数，第 $i$ 个数 $val_{i}$表示第 $i$ 个点的权值。

接下来 $m$ 行，每行两个由空格隔开的正整数 $u_{i}, v_{i},$ 表示一条从 $u_{i}$ 到 $v_{i}$ 的有向边。

接下来 $q$ 行，每行两个由空格隔开的正整数 $L_{i}, R_{i},$ 表示一个询问 $[Li, Ri]$。

Output

为了减少输出量，设 $ans_{i}$ 为第 $i$ 个询问的答案。你只需要输出一行一个整数 $xor^q_{i=1} i×ans_{i}$,即所有询问的编号与答案的乘积异或起来的值。

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 ⩽ val_{i} ⩽ 300, 1 ⩽u_{i}, v_{i} ⩽ n, u_{i} \ne v_{i}, 1 ⩽ L_{i} ⩽ R_{i} ⩽ n$ 。

Tips

建议使用快读