[문제 요약] 1 에서 N 순으로 나열된 유전자에서 연속적인 부분을 뒤집는 경우를 생각하자.

뒤집음 (i,j) (1 <= i <= j <= N) 는 i 번째 j 번째를 통으로 뒤집는 경우를 일컫는다.

예를 들어 , [1,2,3,4,5,6,7] 이 주어질 때

• (3,6) 을 뒤집는 경우 3 번째에서 6 번째를 뒤집고 [1,2,6,5,4,3,7] 로 바뀌고 ,
• (1,3) 을 뒤집는 경우 [6, 2, 1, 5, 4, 3, 7] 이다.

문제는 어떤 유전자가 역 변이가 일어난 후 처음의 유전자 번호가 몇 번째 위치에 있는가를 알아내는 것이 문제이다.

입력

• 첫 번째 라인은 N ( 1 <= N <= 50000 ) 이다. 즉 1,2,3, ...,N 유전자의 수열이 주어진다.
• 두 번째 라인은 뒤집음 (i,j) 의 횟수 R ( 0 <= R <= 1000 ) 이 주어진다.
• 다음 R 라인 은 i , j 가 ( 1 <= i <= j <= N ) 주어진다.
• 다음으로 질의 수 Q ( 0 <= Q <= 100 ) 가 주어지고
• 다음 Q 라인은 처음의 유전자 번호가 주어진다.

출력

입출력 예

입력

9
1
3 6
4
1
3
5
1

출력

1
6
4
1

입력

5
2
1 2
1 5
2
5
2

출력

1
5

출처:South America 2005