问题描述

青蛙先生有一个长度为 $n$ 的整数序列，可以表示为 $a_1, a_2, \cdots, a_n$。现在有 $m$ 次查询。
在第 $i$ 次查询中，会给出两个整数 $l_i$ 和 $r_i$。考虑子序列 $ a_{l_i}, a_{l_{i+1}}, a_{l_{i+2}}, \cdots, a_{r_i} $。
我们可以将这个子序列中首次出现的整数的位置（根据原始序列的位置）表示为 $p_{1}^{(i)}, p_{2}^{(i)}, \cdots, p_{k_i}^{(i)}$（按升序排列，即 $ p_{1}^{(i)} < p_{2}^{(i)} < \cdots < p_{k_i}^{(i)} $）。
注意，$k_i$ 是这个子序列中不同整数的数量。你需要输出第 $i$ 次查询的 $ p_{\left \lceil \frac{k_i}{2} \right \rceil}^{(i)} $。

输入

输入的第一行是一个整数 $T$ ($T \leq 2$)，表示测试用例的数量。
每个测试用例以两个整数 $n$ ($n \leq 2 \times 10^5$) 和 $m$ ($m \leq 2 \times 10^5$) 开始。接下来的一行包含 $n$ 个整数，表示序列中的整数（即 $a_1, a_2, \cdots, a_n$，$0 \leq a_i \leq 2 \times 10^5$）。
接下来的 $m$ 行每行包含两个整数 $l_i$ 和 $r_i$。
然而，青蛙先生觉得这个问题太简单了，于是他生气地修改了每个查询，将其改为 $l_i', r_i'$ ($1 \leq l_i' \leq n$，$1 \leq r_i' \leq n$)。结果，问题变得更加有趣。
我们可以将答案表示为 $ans_1, ans_2, \cdots, ans_m$。注意，对于每个测试用例，$ans_0 = 0$。
你可以通过以下公式从读取的值（我们将其表示为 $l_i', r_i'$）中得到正确的输入 $l_i, r_i$： $[ 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 } ]$

输出

每个测试用例输出一行。
对于每个测试用例，输出一行 “Case #x: $p_1, p_2, \cdots, p_m$”，其中 $x$ 是测试用例编号（从 1 开始），$p_1, p_2, \cdots, p_m$ 是答案。

样例输入

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

样例输出

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

提示

题目来源

HDU Online Judge