题目描述

达达是 T 国的公主，平时的一大爱好是作诗。

由于时间紧迫，达达作完诗之后还要虐 OI，于是达达找来一篇长度为$N$的文章，阅读 $M$ 次，每次只阅读其中连续的一段 $[l,r]$，从这一段中选出一些汉字构成诗。

因为达达喜欢对偶，所以达达规定最后选出的每个汉字都必须在$[l,r]$里出现了正偶数次。

而且达达认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。

于是达达请你安排选法。

问题简述：$N$个数，$M$组询问，每次询问需要你求出 $[l,r]$ 中有多少个数出现正偶数次。

输入格式

输入第一行包含三个整数 $n、c$以及$m$，表示文章字数、汉字的种类数、要选择$m$ 次。

第二行有$n$个整数，每个数 $A[i]$在$[1,c]$ 间，代表一个编码为$A[i]$的汉字。

接下来$m$行每行两个整数$l$和 $r$，设上一个询问的答案为 $ans$(第一个询问时$ans$=0)，令 $L=(l+ans)\bmod n+1,R=(r+ans)\bmod n+1$，若 $L>R$，交换$L$ 和 $R$，则本次询问为 $[L,R]$。

输出格式

输出共 $m$行，每行一个整数，第 $i$ 个数表示达达第$i$ 次能选出的汉字的最多种类数。

样例

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

2
0
0
0
1

数据范围

$1≤n,c,m≤10^5$

来源

• BZOJ2821
• 算法竞赛进阶指南