Bạn đang chơi một trò chơi bao gồm \(n\) hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: khi bạn bắt đầu trên hành tinh \(x\) và di chuyển qua \(k\) cổng dịch chuyển, bạn sẽ đến hành tinh nào?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng hành tinh và truy vấn. Các hành tinh được đánh số \(1,2,\ldots,n\)
• Dòng thứ hai có \(n\) số nguyên \(t_1,t_2,\ldots,t_n\): với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là \(t_i=i\)
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(x\) và \(k\): bạn bắt đầu trên hành tinh \(x\) và di chuyển qua \(k\) cổng dịch chuyển

Constraints

• \(1 \leq n, q \leq 2 \cdot 10^5\)
• \(1 \leq t_i \leq n\)
• \(1 \leq x \leq n\)
• \(0 \leq k \leq 10^9\)

Output

• In đáp án cho mỗi truy vấn

Example

4 3
2 1 1 4
1 2
3 4
4 1

1
2
4