Strange Permutation

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Alice 有一个排列 $p_1, p_2, \ldots, p_n$。不幸的是，这个排列看起来非常无聊，于是她决定对其进行一些改变。她可以选择若干个不重叠的子区间，并将它们分别翻转。翻转单个子区间 $[l, r]$（即将第 $l$ 个到第 $r$ 个元素翻转）的代价为 $r - l$，一次操作的总代价为所有被翻转子区间的代价之和。Alice 心中有一个整数 $c$，因此她只考虑总代价不超过 $c$ 的操作。

然后她觉得更无聊了，于是把所有通过恰好一次操作可以得到的排列都写了下来。当然，Alice 很聪明，每个能得到的排列只写一次（无论通过多少种方式得到），并且将这些排列按字典序排序。

现在 Bob 想向 Alice 提出一些问题。每个问题如下：Alice 写下的第 $j$ 个排列中的第 $i$ 个数字是多少？由于 Alice 太无聊不想回答这些问题，于是她请你帮忙。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 30$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$c$、$q$（$1 \leq n \leq 3 \times 10^4$，$1 \leq c \leq 4$，$1 \leq q \leq 3 \times 10^5$），分别表示排列的长度、操作的最大总代价和询问的数量。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$，$p_i \neq p_j$ 当 $i \neq j$），表示初始排列。

接下来 $q$ 行，每行包含两个整数 $i$ 和 $j$（$1 \leq i \leq n$，$1 \leq j \leq 10^{18}$），表示一次询问的参数。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$，所有测试用例中 $q$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个询问，输出该询问的答案。如果 Alice 写下的第 $j$ 个排列不存在，则输出 $-1$。

样例输入 1

2
3 1 9
1 2 3
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3
6 4 4
6 5 4 3 1 2
1 1
3 14
1 59
2 6

样例输出 1

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

样例输入 2

1
12 4 2
1 2 3 4 5 6 7 8 9 10 11 12
2 20
2 21

样例输出 2

2
2

提示

在第一个测试用例中，Alice 写下了如下排列：$[1, 2, 3]$、$[1, 3, 2]$、$[2, 1, 3]$。

注意，对于排列 $[3, 2, 1]$，Alice 需要翻转整个数组，代价为 $2$，大于指定的 $c=1$。其他两个排列无法通过题目描述的恰好一次操作得到。

数据范围

• $1\le t\le30$，$1\le n\le3\times10^4$，$1\le c\le4$，$1\le q\le3\times10^5$；
• 每个测试用例中的 $p$ 是 $1\ldots n$ 的排列；
• 每次询问满足 $1\le i\le n$，$1\le j\le10^{18}$；
• 单个输入文件内所有测试用例的 $\sum n\le3\times10^5$ 且 $\sum q\le3\times10^5$。

每个测试点独立计分。