← 返回题目列表

Codeforces · 1470/E

E. 奇怪的排列

中文机器翻译题面 查看原题

Alice 有一个排列 $$$p_1, p_2, \ldots, p_n$$$。不幸的是,这个排列看起来很无聊,所以她决定改变它并选择这个排列的一些不重叠的子范围并将它们反转。反转单个子范围 $$$[l, r]$$$(从位置 $$$l$$$ 到位置 $$$r$$$(含)的元素)的成本等于 $$$r - l$$$,并且操作的成本是反转各个子范围的成本之和。 Alice 心里有一个整数 $$$c$$$,所以她只考虑成本不超过 $$$c$$$ 的操作。

然后她真的很无聊,决定写下通过对初始排列执行一次操作可能获得的所有排列。当然,Alice很聪明,所以她把每个可获得的排列都写了一次(无论可以有多少种方式获得),当然这个列表是按字典顺序排序的。

现在鲍勃想问爱丽丝一些有关她的列表的问题。每个问题都采用以下形式:Alice 写下的第 $$$j$$$ 排列中的第 $$$i$$$ 个数字是什么?由于爱丽丝太无聊了,无法回答这些问题,所以她请你帮她解答。

输入

第一行包含一个整数 $$$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$$$, $$$p_i \neq p_j$$$ if $$$i \neq 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$$$。

输出

对于每个查询,输出该查询的答案,或者如果 $$$j$$$-th 排列不存在于她的列表中,则输出 $$$-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$$$。其他两种排列不能通过仅执行问题陈述中描述的一个操作来获得。