[AdditionalFile6499.zip](file://AdditionalFile6499.zip?type=additional_file)

#6499. 「雅礼集训 2018 Day2」颜色

标签: 传统 | 时间限制: 1000 ms | 内存限制: 8 MiB |

题目描述

有 $n$ 个数字，第 $i$ 个数字为 $a_i$。

有 $m$ 次询问，每次给出 $k_i$ 个区间，每个区间表示第 $l_{i, j}$ 到 $r_{i, j}$ 个数字，求这些区间中一共出现了多少种不同的数字。

部分数据强制在线。

输入格式

第一行包含三个整数 $n, m, p$，$p$ 为 $0$ 或 $1$ 表示是否强制在线。

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

接下来依次给出每个询问，每个询问第一行一个正整数，表示 $k_i$，接下来 $k_i$ 行，每行两个正整数，分别表示 $l_{i, j}$ 和 $r_{i, j}$，若 $p = 1$ 且这不是第一个询问，输入的 $l_{i, j}$ 和 $r_{i, j}$ 是经过加密的，你需要将这两个数字分别异或上上一个询问的答案，对 $n$ 取模后再加 $1$，两者较小值为真实的 $l_{i, j}$，较大值为真实的 $r_{i, j}$。

输出格式

对每个询问输出一行一个整数表示答案。

样例

输入

3 2 0
1 2 1
1
1 2
2
1 1
3 3

输出

2
1

数据范围与提示

对于全部数据，$1 \leq n, m, \sum k_i, a_i \leq 10^5, 1 \leq l_{i, j} \leq r_{i, j} \leq n$。

• 子任务 $\rm 1(points:10)$：$n, m, \sum k_i, a_i \leq 5000$
• 子任务 $\rm 2(points:10)$：$n, m, \leq 5000$
• 子任务 $\rm 3(points:20)$：$k_i = 1$
• 子任务 $\rm 4(points:20)$：$p = 0$
• 子任务 $\rm 5(points:20)$：$1 \leq n, m, \sum k_i, a_i \leq 50000$
• 子任务 $\rm 6(points:20)$：无特殊限制