23912번 - 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 i-th room and (i+1)-th room has difficulty level D_i.

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 Q queries. For the i-th query, she would like to know: What is the K_i-th room that she will take a picture in if she starts in the S_i-th room?

입력

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

출력

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 Q queries in order, separated by spaces.

제한

• 1 ≤ T ≤ 100.
• 1 ≤ D_i ≤ 10⁵, for all i.
• All D_i are distinct.
• 1 ≤ S_i ≤ N, for all i.
• 1 ≤ K_i ≤ N, for all i.

Test Set 1 (12점)

• 2 ≤ N ≤ 1000.
• 1 ≤ Q ≤ 1000.

Test Set 2 (26점)

• 2 ≤ N ≤ 10⁵ and 1 ≤ Q ≤ 10⁵ for at most 20 test cases.
• For the remaining cases, 2 ≤ N ≤ 1000 and 1 ≤ Q ≤ 1000.

힌트

In sample case #1, there are four queries:

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

In sample case #2, there are two queries:

• In the first query, Bangle takes pictures in the rooms in the order 6, 5, 4, 3, 2, 1, 7, 8, 9 and 10, so the answer is 8.
• The second query is the same as the first, so the answer is also 8.