P1023：Sequence II

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，有 $m$ 次查询。

对于第 $i$ 次查询，考虑子序列 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$。

把该子序列中每个不同整数第一次出现的位置（位置以下标形式、相对于原序列计）按升序记为 $p_1^{(i)}, p_2^{(i)}, \dots, p_{k_i}^{(i)}$，其中 $k_i$ 是这个子序列中不同整数的个数。

你需要输出 $p_{\left\lceil \frac{k_i}{2} \right\rceil}^{(i)}$。

输入输出格式

输入

第一行一个整数 $T$，表示测试组数。

对于每组数据：

• 第一行两个整数 $n, m$。
• 第二行包含 $n$ 个整数，表示序列 $a_1, a_2, \dots, a_n$。
• 接下来 $m$ 行，每行给出两个整数 $l_i', r_i'$。

设该组数据的答案依次为 $ans_1, ans_2, \dots, ans_m$，并规定 $ans_0 = 0$。真正的查询端点由下式恢复：

$$l_i = \min \left\{ ((l_i' + ans_{i-1}) \bmod n) + 1,\ ((r_i' + ans_{i-1}) \bmod n) + 1 \right\}$$$$r_i = \max \left\{ ((l_i' + ans_{i-1}) \bmod n) + 1,\ ((r_i' + ans_{i-1}) \bmod n) + 1 \right\}$$

输出

对于每组数据输出一行：

Case #x: p_1 p_2 ... p_m

其中 $x$ 表示测试组编号（从 $1$ 开始），$p_i$ 为第 $i$ 次查询的答案。

样例

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

数据范围

• $1 \le T \le 2$
• $1 \le n, m \le 2 \times 10^5$
• $0 \le a_i \le 2 \times 10^5$
• $1 \le l_i', r_i' \le n$