题目描述

一个大仓库中有 $n$ 个箱子排成一列，编号为 $1$ 到 $n$。每个箱子有一个标签 $a_i$，表示其中货物的种类。

仓库检查员会进行 $q$ 次检查。每次检查给出一个区间 $[l,r]$。

对于一个标签值 $x$，如果在区间 $[l,r]$ 中，标签为 $x$ 的箱子恰好有 $x$ 个，则称这种箱子在该区间中是“正确摆放”的。

例如，当 $x=3$ 时，在当前区间中必须恰好有 $3$ 个标签为 $3$ 的箱子。

注意：答案统计的是满足条件的不同标签值 $x$ 的个数。

请你对每次检查，求出区间内正确摆放的标签种类数。

输入格式

第一行包含三个整数 $n,q,c$，分别表示箱子数量、检查次数和询问编码参数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个箱子的标签。

接下来 $q$ 行，每行包含两个整数 $l,r$。

如果 $c=0$，则输入中的 $l,r$ 就是询问区间的真实边界。

如果 $c=1$，询问被编码。设第 $i$ 次询问的答案为 $ans_i$，并令 $ans_0=0$。对于第 $i$ 次询问，真实边界为

$$l = l \oplus ans_{i-1},\qquad r = r \oplus ans_{i-1},$$

其中 $\oplus$ 表示按位异或。保证解码后有 $1\le l\le r\le n$。

输出格式

对于每个询问，输出一行一个整数，表示区间 $[l,r]$ 中满足“出现次数恰好等于自身标签值”的不同标签数量。

数据范围

• $1 \le n,q \le 100000$
• $1 \le a_i \le 10^6$
• $c\in\{0,1\}$

子任务

子任务	分值	依赖子任务	$n,q$	$c$	额外限制
1	5	-	$\le 1000$	0	-
2	20	1	$\le 20000$
3	10	-	$\le 100000$		所有询问满足 $l=1$
4	15				所有 $a_i\le 100$
5	20	1-4			-
6	30	1-5		0 或 1

只有通过某个子任务及其所有依赖子任务中的全部测试，才能获得该子任务分数。

样例

样例 1

7 3 0
1 2 2 3 3 3 2
1 7
1 3
4 6

2
2
1

样例 2

5 2 0
1 1 1 1 1
1 5
2 4

0
0

样例说明

对于样例 1 的询问 $[1,7]$：

• 标签 $1$ 出现 $1$ 次，满足条件；
• 标签 $2$ 出现 $3$ 次，不满足条件；
• 标签 $3$ 出现 $3$ 次，满足条件。

所以答案为 $2$。