Traveling Through the City Cluster

Charine is a traveler with an ambitious plan to visit all the cities in a vast city cluster. The cluster contains n cities, with the exciting property that any two cities are directly connected by a road of length 1 zm.

Despite this modern convenience, Charine is bound by a personal constraint – for each city i, he has preselected a route (denoted by a_i) that he will always take when leaving city i. In other words, after visiting city i, he will automatically move to city a_i without taking any detours or incurring any hesitation.

Traveling at a constant pace of 1 zm per unit time, Charine has exactly t units of time to travel. Note that although road distances no longer vary in length due to accelerated transport, the predetermined routes (or "通路") define his journey, which is completely independent of the road network connectivity (the "道路").

Given his travel plan and starting city, determine where Charine will be after t units of time (i.e. after t moves). When t = 0, he is at his starting city.

The problem can be formally stated as follows:

• You are given an integer n representing the number of cities.
• An array a of length n is provided, where each element a_i (in 1-indexed format) represents the city that Charine will travel to from city i.
• You will also receive m queries. Each query consists of two integers, the starting city S and the time t.
• For each query, determine the city in which Charine will be located after t moves following his predetermined route.

The movement process can be visualized by the recurrence:

$$ \text{city}_{0} = S, \quad \text{city}_{k+1} = a_{\text{city}_{k}} \quad (k \ge 0) $$

inputFormat

The first line contains two space‐separated integers n and m (the number of cities and the number of queries).

The second line contains n space-separated integers: a₁ a₂ ... a_n, where each a_i (1-indexed) is the predetermined next city from city i.

Then, m lines follow, each containing two space-separated integers S and t representing a query: starting city and the number of moves (time units).

outputFormat

For each query, output the final city in which Charine is located after performing exactly t moves. Each answer should be printed on its own line.

sample

5 3
2 3 4 5 1
1 0
1 1
2 3

1
2
5

</p>