Mạng Dịch Chuyển

Bạn đang quản lý một hệ thống gồm $n$ máy chủ. Mỗi máy chủ đều tích hợp một đường chuyển tiếp cố định dẫn đến một máy chủ khác (hoặc dẫn đến chính nó).

Nhiệm vụ của bạn là xử lý $q$ truy vấn có dạng: khi bắt đầu tại máy chủ $x$ và di chuyển qua $k$ đường chuyển tiếp liên tiếp, bạn sẽ dừng lại ở máy chủ nào?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 ≤ n, q ≤ 2 · 10^5$): số lượng máy chủ và số lượng truy vấn. Các máy chủ được đánh số từ $1$ đến $n$.

Dòng thứ hai chứa $n$ số nguyên $t_1, t_2, ..., t_n$ ($1 ≤ t_i ≤ n$): máy chủ đích của đường chuyển tiếp xuất phát từ mỗi máy chủ. Có thể xảy ra trường hợp $t_i = i$.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ ($1 ≤ x ≤ n$) và $k$ ($0 ≤ k ≤ 10^9$): bắt đầu tại máy chủ $x$ và di chuyển qua $k$ đường chuyển tiếp.

Kết quả

In ra kết quả cho mỗi truy vấn, mỗi kết quả trên một dòng.

Chấm điểm

Subtask 1 (30 points). $k ≤ 1000$

Subtask 2 (70 points). $1 ≤ n, q ≤ 2 · 10^5$

Ví dụ

Input

5 2
3 3 4 5 2
1 3
2 4

Output

5
2

Ghi chú

Giải thích cho ví dụ mẫu:

Hệ thống gồm $5$ máy chủ và $2$ truy vấn.

Đường chuyển tiếp từ các máy chủ lần lượt là $t = [3, 3, 4, 5, 2]$.

Truy vấn $1$: Xuất phát từ máy chủ $1$, qua $3$ đường chuyển tiếp: $1 \to 3 \to 4 \to 5$. Kết quả là $5$.

Truy vấn $2$: Xuất phát từ máy chủ $2$, qua $4$ đường chuyển tiếp: $2 \to 3 \to 4 \to 5 \to 2$. Kết quả là $2$.