내 유전자는 어디에?

과학자들은 한 종이 다른 종으로 어떻게 진화했는지를, 조상의 유전체(게놈)가 후손의 유전체로 어떻게 변했는지 추적하여 연구한다. 가까운 종들은 여러 유전자를 공유하며, 이들을 비교하는 좋은 방법 중 하나는 공유하는 유전자들의 위치가 어떻게 바뀌었는지를 살펴보는 것이다.

유전체의 유전자 순서를 바꾸는 가장 흔한 돌연변이 중 하나가 뒤집기(reversal) 이다. 유전체를 $N$개의 유전자로 이루어진 수열로 보고, 각 유전자를 $1$부터 $N$까지의 정수라고 하자. 뒤집기는 연속한 유전자 구간의 순서를 뒤집는 연산으로, 두 인덱스 $(i, j)$ ($1 \le i \le j \le N$)로 표현되며 $i$번째부터 $j$번째까지의 유전자 순서를 뒤집는다. 유전체 $[g_1, \dots, g_{i-1}, g_i, g_{i+1}, \dots, g_{j-1}, g_j, g_{j+1}, \dots, g_N]$에 적용하면 $[g_1, \dots, g_{i-1}, g_j, g_{j-1}, \dots, g_{i+1}, g_i, g_{j+1}, \dots, g_N]$가 된다.

예를 들어 [1, 2, 3, 4, 5, 6, 7]에 뒤집기 $(3, 6)$을 적용하면 [1, 2, 6, 5, 4, 3, 7]이 되고, 이어서 뒤집기 $(1, 3)$을 적용하면 [6, 2, 1, 5, 4, 3, 7]이 된다.

한 과학자가 유전체에 여러 번의 뒤집기를 차례로 적용한 뒤, 몇몇 유전자의 최종 위치를 알고 싶어 한다. 이 질의들에 답하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

• 각 테스트 케이스의 첫 줄에는 유전체의 유전자 개수 $N$ ($1 \le N \le 50000$)이 주어진다. 유전체는 처음에 $1$부터 $N$까지의 정수가 증가하는 순서로 놓여 있다.
• 둘째 줄에는 적용할 뒤집기의 횟수 $R$ ($0 \le R \le 1000$)이 주어진다.
• 이어지는 $R$개의 줄에는 각각 뒤집기를 나타내는 두 정수 $i$, $j$ ($1 \le i \le j \le N$)가 공백 하나로 구분되어 주어진다.
• 다음 줄에는 질의의 개수 $Q$ ($0 \le Q \le 100$)가 주어진다.
• 이어지는 $Q$개의 줄에는 각각 최종 위치를 알고 싶은 유전자 하나가 정수로 주어진다.

뒤집기는 주어진 순서대로 적용된다. 입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 $Q + 1$개의 줄을 출력한다. 첫 줄에는 Genome 다음에 공백 하나와 테스트 케이스 번호를 출력한다(테스트 케이스 번호는 $1$부터 시작한다). 그 다음 $Q$개의 줄에는 각각 질의한 유전자의 최종 위치를 정수 하나로 출력한다.