잠긴 문

Bangles는 지역 박물관을 둘러볼 준비를 하고 있다. 박물관은 일렬로 늘어선 N개의 방으로 이루어져 있으며, 방에는 왼쪽에서 오른쪽으로 1부터 N까지 번호가 매겨져 있다. 방들은 N-1개의 잠긴 문으로 연결되어 있으며, 각 문은 서로 인접한 방 한 쌍을 연결한다. 각 문에는 Bangles가 그 문을 여는 것이 얼마나 어려운지를 나타내는 난이도가 있다. 어떤 두 문도 같은 난이도를 갖지 않는다. i번째 방과 (i+1)번째 방 사이의 문의 난이도는 $D_{i}$이다.

Bangles는 시작할 방 하나를 선택하고, 이동하면서 사진을 찍어 박물관의 각 방을 한 번에 하나씩 방문한다. 시작한 방에서 사진을 찍은 다음, 모든 방에서 사진을 찍을 때까지 다음 절차를 반복한다. 자신이 열 수 있는 잠긴 문 두 개 중 난이도가 더 낮은 문을 열고, 새로 들어갈 수 있게 된 방에서 사진을 찍는다. 자신이 열 수 있는 잠긴 문이 하나뿐이라면 그 문을 연다. 한 번 열린 문은 계속 열린 상태로 남는다.

Bangles는 어느 방에서 시작하고 싶은지 아직 정하지 못했으므로, Q개의 질의에 답해야 한다. i번째 질의에서 Bangles가 알고 싶은 것은 다음과 같다. $S_{i}$번째 방에서 시작한다면, 사진을 찍게 되는 $K_{i}$번째 방은 어느 방인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $D_{i}$ ≤ $10^{5}$. 모든 $D_{i}$은 서로 다르다. 모든 i에 대해 1 ≤ $S_{i}$ ≤ N. 모든 i에 대해 1 ≤ $K_{i}$ ≤ N.

테스트 세트 1

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

테스트 세트 2

최대 20개의 테스트 케이스에서 2 ≤ N ≤ $10^{5}$이고 1 ≤ Q ≤ $10^{5}$이다. 나머지 케이스에서는 2 ≤ N ≤ 1000이고 1 ≤ Q ≤ 1000이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N과 Q가 주어진다. 두 번째 줄에는 잠긴 문을 설명하는 N-1개의 정수가 주어진다. (1부터 시작하는) i번째 정수는 $D_{i}$이다. 이어서 질의를 설명하는 Q개의 줄이 주어진다. 이 줄들 중 i번째 줄에는 두 정수 $S_{i}$와 $K_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며 (1부터 시작), y은 Q개 질의의 답을 순서대로 공백으로 구분한 목록이다.

예제 케이스 #1에는 네 개의 질의가 있다:

• 첫 번째 질의에서 Bangle은 3, 2, 4, 5, 1 순서로 방에서 사진을 찍으므로, 답은 5이다.

• 두 번째 질의에서 Bangle은 3, 2, 4, 5, 1 순서로 방에서 사진을 찍으므로, 답은 3이다.

• 세 번째 질의에서 Bangle은 1, 2, 3, 4, 5 순서로 방에서 사진을 찍으므로, 답은 5이다.

• 네 번째 질의에서 Bangle은 4, 3, 2, 5, 1 순서로 방에서 사진을 찍으므로, 답은 2이다.

예제 케이스 #2에는 두 개의 질의가 있다:

• 첫 번째 질의에서 Bangle은 6, 5, 4, 3, 2, 1, 7, 8, 9, 10 순서로 방에서 사진을 찍으므로, 답은 8이다.

• 두 번째 질의는 첫 번째 질의와 같으므로, 답 역시 8이다.