Sequence II

Mr. Frog has an integer sequence of length n, which can be denoted as $a_1,a_2,\cdots ,a_n$ There are m queries.

In the i-th query, you are given two integers $l_i$ and $r_i$. Consider the subsequence $a_{l_i},a_{l_{i+1}},a_{l_{i+2}},\cdots ,a_{r_i} $.

We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as $p_{1}^{(i)},p_{2}^{(i)},\cdots, p_{k_i}^{(i)}$ (in ascending order, i.e.,$p_{1}^{(i)}<p_{2}^{(i)}<\cdots <p_{k_i}^{(i)}$).

Note that $k_i$ is the number of different integers in this subsequence. You should output $p_{\left \lceil \frac{k_i}{2} \right \rceil}^{(i)}$for the i-th query.

In the first line of input, there is an integer T ($T\leq 2$) denoting the number of test cases.

Each test case starts with two integers n ($n \leq 2 \times 10^5$) and m ($m\leq 2\times 10^5$). There are n integers in the next line, which indicate the integers in the sequence(i.e., $a_1,a_2,\cdots ,a_n, 0\leq a_i \leq 2 \times 10^5$).

There are two integers $l_i$ and $r_i$ in the following m lines.

However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to $l_i^`,r_i^`(1\leq l_i^` \leq n,1\leq r_i^` \leq n )$. As a result, the problem became more exciting.

We can denote the answers as $ans_1, ans_2,\cdots ,ans_m$. Note that for each test case $ans_0 = 0$.

You can get the correct input $l_i,r_i$ from what you read (we denote them as $l_i^`,r_i^`$)by the following formula:
$$ l_i = min\{ (l_i^`+ans_{i-1})\ mod \ n+1, (r_i^`+ans_{i-1})\ mod \ n+1 \} $$
$$ r_i = max\{ (l_i^`+ans_{i-1})\ mod \ n+1, (r_i^`+ans_{i-1})\ mod \ n+1 \} $$

You should output one single line for each test case.

For each test case, output one line “Case #x: $p_1,p_2,\cdots ,p_m$”, where x is the case number (starting from 1) and $p_1,p_2,\cdots ,p_m$ is the answer.