#216764. [GKS 2020 #D] Locked Doors

Bangles is preparing to go on a tour of her local museum. The museum is made up of N rooms in a row, numbered from 1 to N from left to right. The rooms are connected by N-1 locked doors, each connecting a pair of adjacent rooms. Each door has a difficulty level indicating how difficult it is for Bangles to open the door. No two doors will have the same difficulty level. The door between the -th room and -th room has difficulty level .

Bangles will pick one of the rooms to start in, and visit each of the rooms in the museum one at a time, taking pictures as she goes. She takes a picture in her starting room, then she repeats the following procedure until she has taken a picture in all the rooms: Of the two locked doors available to her, she will open the door with the lower difficulty level and take a picture in the newly unlocked room. If there is only one locked door available to her, then she will unlock that door. Once a door is unlocked, it remains unlocked.

Bangles is not yet sure which room she would like to start in, so she needs you to answer queries. For the -th query, she would like to know: What is the -th room that she will take a picture in if she starts in the -th room?

The first line of the input gives the number of test cases, . test cases follow. The first line of each test case contains the two integers and . The second line contains integers, describing the locked doors. The -th integer (starting from 1) is . Then, lines follow, describing the queries. The -th of these lines contains the two integers and .

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of the answers for the queries in order, separated by spaces.

样例输入 1

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

样例输出 1

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

In sample case #1, there are four queries:

• In the first query, Bangle takes pictures in the rooms in the order , , , and , so the answer is .
• In the second query, Bangle takes pictures in the rooms in the order , , , and , so the answer is .
• In the third query, Bangle takes pictures in the rooms in the order , , , and , so the answer is .
• In the fourth query, Bangle takes pictures in the rooms in the order , , , , and , so the answer is .

In sample case #2, there are two queries:

• In the first query, Bangle takes pictures in the rooms in the order , , , , , , , , and , so the answer is .
• The second query is the same as the first, so the answer is also .

Limits

.

, for all .

All are distinct.

, for all .

, for all .

Test Set 1

.

.

Test Set 2

and for at most 20 test cases.

For the remaining cases, and .