题目描述

Bangles 正准备去参观当地的博物馆。博物馆由 $N$ 个房间排成一排组成，编号从 1 到 $N$ 从左到右。房间由 $N-1$ 扇锁着的门连接，每扇门连接一对相邻的房间。每扇门都有一个难度级别，表示 Bangles 打开这扇门的难度。没有两扇门的难度级别相同。第 $i$ 个房间与第 $i+1$ 个房间之间的门的难度级别为 ${D_i}$。

Bangles 将选择一个房间作为起点，然后一次参观一个房间，并在参观时拍照。她在起点房间拍下第一张照片，然后重复以下过程，直到她在所有房间都拍过照片：从她当前可用的两扇锁着的门中，她将打开难度较低的那扇门，并在新解锁的房间中拍照。如果她只有一扇锁着的门可用，那么她就打开那扇门。门一旦被打开，就会保持解锁状态。

Bangles 还不确定她要从哪个房间开始，因此她需要你回答 $Q$ 个查询。对于第 $i$ 个查询，她想知道：如果她从第 ${S_i}$ 个房间开始，那么她拍的第 ${K_i}$ 张照片是在哪个房间？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $Q$。第二行包含 $N-1$ 个整数，描述锁着的门。第 $i$ 个整数（从 1 开始）是 ${D_i}$。然后，接下来 $Q$ 行，每行描述一个查询。这些行中的第 $i$ 行包含两个整数 ${S_i}$ 和 ${K_i}$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是按顺序给出的 $Q$ 个查询的答案列表，用空格分隔。

2
5 4
90 30 40 60
3 4
3 1
1 5
4 3
10 2
6 2 4 5 9 30 7 1 8
6 8
6 8

Case #1: 5 3 5 2
Case #2: 8 8

提示

在样例 #1 中，有四个查询：

• 第一个查询：Bangles 拍照的房间顺序为 3、2、4、5、1，因此答案是 5。
• 第二个查询：Bangles 拍照的房间顺序为 3、2、4、5、1，因此答案是 3。
• 第三个查询：Bangles 拍照的房间顺序为 1、2、3、4、5，因此答案是 5。
• 第四个查询：Bangles 拍照的房间顺序为 4、3、2、5、1，因此答案是 2。

在样例 #2 中，有两个查询：

• 第一个查询：Bangles 拍照的房间顺序为 6、5、4、3、2、1、7、8、9、10，因此答案是 8。
• 第二个查询与第一个相同，因此答案也是 8。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$1 \le D_i \le 10^5$。

所有 $D_i$ 互不相同。

对于所有 $i$，$1 \le S_i \le N$。

对于所有 $i$，$1 \le K_i \le N$。

测试集 1

$2 \le N \le 1000$。

$1 \le Q \le 1000$。

测试集 2

最多 20 个测试用例满足 $2 \le N \le 10^5$ 且 $1 \le Q \le 10^5$。

其余测试用例满足 $2 \le N \le 1000$ 且 $1 \le Q \le 1000$。

翻译由 DeepSeek V4 Pro 完成