Where Am I After K Jumps

Difficulty: 1800 5000 ms 128 MB

graphs binary-lifting

Each node points to exactly one successor. Answer Q queries: starting at node v and following the pointer K times, which node do you reach?

Input: the first line has N and Q; the second line has the successors; each of the next Q lines has v and K.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• 0 ≤ K ≤ 10¹⁸

Sample Tests

4 2
2 3 4 1
1 5
2 2

2
4

1 1
1
1 1000000000000000000

1

Read the Editorial