잠긴 문

Bangles는 박물관 관람을 준비한다. 박물관은 일렬로 늘어선 N개의 방으로 이루어져 있고, 방은 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있다. 방들은 N-1개의 잠긴 문으로 이어져 있으며, 각 문은 서로 인접한 두 방을 연결한다. 각 문에는 Bangles가 문을 여는 데 드는 어려움을 나타내는 난이도가 있다. 두 문의 난이도가 같을 수는 없다. i번 방과 (i+1)번 방 사이의 문의 난이도는 Di이다.

Bangles는 방 하나를 골라 그 방에서 시작해 박물관의 모든 방을 하나씩 방문하며 사진을 찍는다. 시작한 방에서 사진을 찍은 뒤, 모든 방에서 사진을 찍을 때까지 다음 절차를 반복한다. 열 수 있는 잠긴 문이 두 개라면 난이도가 더 낮은 문을 열고 새로 열린 방에서 사진을 찍는다. 열 수 있는 잠긴 문이 하나뿐이라면 그 문을 연다. 한 번 연 문은 계속 열린 상태로 남는다.

Bangles는 아직 어느 방에서 시작할지 정하지 못했기 때문에, 여러분이 Q개의 질문에 답해야 한다. i번째 질문은 Si번 방에서 시작했을 때 Bangles가 사진을 찍게 되는 Ki번째 방이 어디인지 묻는다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 Q가 주어진다. 둘째 줄에는 잠긴 문을 나타내는 N-1개의 정수가 주어진다. 1부터 시작해 i번째 정수는 Di이다. 그다음 Q개의 줄에 질문이 주어진다. 이 중 i번째 줄에는 두 정수 Si와 Ki가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Q개의 질문에 대한 답을 순서대로 공백으로 구분해 나열한 목록이다.

• 1 ≤ T ≤ 100.
• 1 ≤ Di ≤ 105, 모든 i에 대해.
• 모든 Di는 서로 다르다.
• 1 ≤ Si ≤ N, 모든 i에 대해.
• 1 ≤ Ki ≤ N, 모든 i에 대해.

예제 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이다.