시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 319 156 56 67.470%

문제

함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.

  • f1(x) = f(x)
  • fn+1(x) = f(fn(x))

예를 들어 f4(1) = f(f(f(f(1))))이다.

n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오.

입력

첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)

다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.

다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m)

출력

주어지는 n, x마다 fn(x)를 출력한다.

예제 입력 1

5
3 3 5 4 3
5
1 1
2 1
11 3
1000 4
5 1

예제 출력 1

3
5
5
4
3

출처