은하계에는 1번부터 M번까지 M개의 행성이 존재한다. 각 행성에는 다른 행성으로 연결되는 단방향 워프 포털이 정확히 하나씩 설치되어 있다.

i번 행성에 있는 포털을 이용하면 정해진 목적지인 f(i)번 행성으로 즉시 이동하게 된다.

우주 여행가인 당신은 특정 행성 x에서 출발하여 포털을 정확히 n번 이용했을 때 최종적으로 도착하게 되는 행성이 어디인지 알고 싶다.

수많은 여행 계획(Q)이 주어질 때, 각 계획에 대한 최종 목적지 행성을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 M이 주어진다. (1 ≤ M ≤ 200,000)

둘째 줄에 1번 행성부터 M번 행성까지 각 행성의 포털이 연결하는 목적지 행성 번호 f(1), f(2), .., f(M)이 차례대로 주어진다. (1 ≤ f(i) ≤ M)

그다음 줄에 여행 계획의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

다음 Q개의 줄에 각각 포털 이용 횟수 n과 시작 행성 번호 x가 주어진다. (1 ≤ n ≤ 1,000,000,000; 1 ≤ x ≤ M)

출력

각 질문마다 n번의 포털 이동 후 도착하게 되는 최종 행성 번호를 한 줄에 하나씩 출력한다.

제약 조건

1 ≤ M ≤ 200,000

1 ≤ Q ≤ 200,000

1 ≤ n ≤ 1,000,000,000

예제 입력 1

5
3 3 5 4 2
4
1 1
2 1
3 1
10 5

예제 출력 1

3
5
2
2