Description

http://acm.hdu.edu.cn/showproblem.php?pid=5919

题目大意是有 $m$ 次询问，每次询问一段区间[ l , r ] ，从左到右，如果这个数是在这个区间第一次出现，则记录下其下标，

我们会得到一个新的数组，要求这个数组的中位数是什么。(不需要排序，只需要考虑中间位置的数)

Format

Input

第一行数据组数t

然后n,m,($1 \leq n,m \leq 2\times 10^5$)

然后n个$a_i(0 \leq a_i \leq 5\times 10^5 )$

接下来m行，每行$l_i',r_i'$

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

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

下一组数据

Output

输出格式

Case #x: ans1 ans2 ans3...ansm

ansi 指的是答案所在的位置

x是数据组数

Samples

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