作诗(Poetize)

SHY 是 T 国的公主，平时的一大爱好是作诗。由于时间紧迫，她找来一篇长度为 $n$ 的文章，并进行 $m$ 次阅读。每次她只阅读其中连续的一段 $[L,R]$ ，并从中选出一些汉字构成诗。

因为 SHY 喜欢对偶，所以她要求选出的每种汉字都在区间 $[L,R]$ 中出现了正偶数次。她希望选出的汉字种类数尽可能多。

文章中的汉字用整数表示。对于每次询问，请求出给定区间内出现次数为正偶数的汉字种类数。

输入格式

第一行包含三个整数 $n,c,m$ ，分别表示文章的字数、汉字的种类数和询问次数。

第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$ ，其中 $A_i\in[1,c]$ ，表示文章中第 $i$ 个汉字的编码。

接下来 $m$ 行，每行包含两个整数 $l,r$ 。设上一次询问的答案为 $\mathit{ans}$ ，第一次询问时 $\mathit{ans}=0$ ，令

L=(l+\mathit{ans})\bmod n+1,\qquad R=(r+\mathit{ans})\bmod n+1。

若 $L>R$ ，则交换 $L$ 和 $R$ 。本次询问的区间为 $[L,R]$ 。

输出共 $m$ 行，每行一个整数。第 $i$ 行表示第 $i$ 次询问中，区间内出现次数为正偶数的汉字种类数。

本题题面与测试数据整理自 BZOJ 2821。