CF1470E.Strange Permutation

Alice had a permutation $p_1, p_2, \ldots, p_n$. Unfortunately, the permutation looked very boring, so she decided to change it and choose some non-overlapping subranges of this permutation and reverse them. The cost of reversing a single subrange $[l, r]$ (elements from position $l$ to position $r$, inclusive) is equal to $r - l$, and the cost of the operation is the sum of costs of reversing individual subranges. Alice had an integer $c$ in mind, so she only considered operations that cost no more than $c$.

Then she got really bored, and decided to write down all the permutations that she could possibly obtain by performing exactly one operation on the initial permutation. Of course, Alice is very smart, so she wrote down each obtainable permutation exactly once (no matter in how many ways it can be obtained), and of course the list was sorted lexicographically.

Now Bob would like to ask Alice some questions about her list. Each question is in the following form: what is the $i$-th number in the $j$-th permutation that Alice wrote down? Since Alice is too bored to answer these questions, she asked you to help her out.

爱丽丝原本有一个排列 $p_1, p_2, \ldots, p_n$。不幸的是，这个排列看起来非常单调乏味，因此她决定对其进行修改：选择该排列中若干个互不重叠的子区间，并将每个子区间内的元素反转。反转单个子区间 $[l, r]$（即从位置 $l$ 到位置 $r$（含端点）的所有元素）的代价为 $r - l$，而一次操作的总代价等于所有被反转子区间的代价之和。爱丽丝心中设定了一个整数 $c$，因此她只考虑总代价不超过 $c$ 的操作。

随后，她变得极其无聊，于是决定将通过在初始排列上恰好执行一次操作所能得到的所有不同排列全部写下来。当然，爱丽丝非常聪明，因此她对每个可得到的排列仅记录一次（无论其可通过多少种方式获得），并且这些排列按字典序升序排列。

现在鲍勃想向爱丽丝询问一些关于该列表的问题。每个问题的形式如下：爱丽丝所写的第 $j$ 个排列中，第 $i$ 个位置上的数是多少？由于爱丽丝实在太无聊而不愿回答这些问题，她请你来帮她解答。

The first line contains a single integer $t$ ($1 \leq t \leq 30$) — the number of test cases.

The first line of each test case contains three integers $n$, $c$, $q$ ($1 \leq n \leq 3 \cdot 10^4$, $1 \leq c \leq 4$, $1 \leq q \leq 3 \cdot 10^5$) — the length of the permutation, the maximum cost of the operation, and the number of queries.

The next line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$, $p_i \neq p_j$ if $i \neq j$), describing the initial permutation.

The following $q$ lines describe the queries. Each of them contains two integers $i$ and $j$ ($1 \leq i \leq n$, $1 \leq j \leq 10^{18}$), denoting parameters of this query.

It is guaranteed that the sum of values $n$ over all test cases does not exceed $3 \cdot 10^5$, and the sum of values $q$ over all test cases does not exceed $3 \cdot 10^5$.

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

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

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

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

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

For each query output the answer for this query, or $-1$ if $j$-th permutation does not exist in her list.

对于每个查询，输出该查询的答案；如果她的列表中不存在第 $j$ 个排列，则输出 $-1$。

In the first test case, Alice wrote down the following permutations: $[1, 2, 3]$, $[1, 3, 2]$, $[2, 1, 3]$.

Note that, for a permutation $[3, 2, 1]$ Alice would have to reverse the whole array, and it would cost her $2$, which is greater than the specified value $c=1$. The other two permutations can not be obtained by performing exactly one operation described in the problem statement.

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

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