Problem Description

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.

Input

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 } ]$

Output

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.

Sample Input

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

Sample Output

Case #1: 3 3
Case #2: 3 1

Hint

Source

HDU Online Judge