Description

Due to time pressure, after finishing a poem SHY still needs to crush OI, so she takes an article of length $n$, reads it $m$ times, and each time reads only a contiguous segment $[l, r]$. From this segment, she selects some Chinese characters to form a poem. Because SHY likes parallelism, she requires that every selected character must appear a positive even number of times within $[l, r]$. Also, SHY wants the number of distinct selected characters (two identical characters are considered the same type) to be as large as possible. So SHY asks LYD to arrange the selection.

LYD, being a "sha×", certainly cannot do it, so he asks you for help.

Problem summary: Given $n$ positive integers $a_1 \dots a_n$ not greater than $c$ and $m$ queries, each query asks how many numbers in $[l, r]$ appear a positive even number of times.

Input Format

This problem is strictly online.

The first line contains three integers $n$, $c$, and $m$, representing the article length, the number of character types, and the number of selections.

The second line contains $n$ integers. The $i$-th integer is the code $a_i$ of the $i$-th character.

Each of the next $m$ lines contains two integers $L$ and $R$. Let the previous query’s answer be $ans$ (for the first query, $ans = 0$). Define $l=((L+ans)\bmod n)+1$, $r=((R+ans)\bmod n)+1$, and if $l>r$, swap $l$ and $r$. Then the current query is $[l, r]$.

Output Format

Output $m$ lines. The $i$-th integer is the maximum number of distinct characters SHY can select for the $i$-th query.

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

2
0
0
0
1

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, c, m \le 10^5$, $1 \leq a_i \leq c$, $1 \leq l, r \leq n$.

Translated by ChatGPT 5