Pre - LCA

Một công ty lớn với n nhân viên được tổ chức dưới dạng một hệ thống phân cấp dạng cây, nơi mỗi nhân viên, ngoại trừ Tổng Giám Đốc (nhân viên số 1), đều có một ông chủ trực tiếp. Tổng giám đốc là người duy nhất không có ông chủ.

Nhiệm vụ của bạn là trả lời q truy vấn, mỗi truy vấn hỏi rằng: "Ai là người sếp cao hơn nhân viên \(x\) \(k\) bậc trong hệ thống phân cấp?"

Để làm rõ hơn, truy vấn sẽ yêu cầu bạn xác định người sếp của một nhân viên theo khoảng cách (số bậc) nhất định trong chuỗi mối quan hệ cấp trên cấp dưới. Nếu không tồn tại người sếp cách \(x\) đúng \(k\) bậc, hãy trả lời là \(-1\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) (\(1 \leq n, q \leq 2 \times 10^5\)) --- số lượng nhân viên trong công ty và số lượng truy vấn.
• Dòng thứ hai chứa \(n-1\) số nguyên \(e_2, e_3, \ldots, e_n\) (\(1 \leq e_i \leq i-1\)), trong đó \(e_i\) biểu thị rằng nhân viên \(i\) có ông chủ trực tiếp là \(e_i\).
• Mỗi trong \(q\) dòng tiếp theo chứa hai số nguyên \(x\) và \(k\) (\(1 \leq x \leq n\), \(0 \leq k \leq n\)), biểu thị một truy vấn: "Ai là sếp của nhân viên \(x\) ở \(k\) bậc trên?"

Output

Với mỗi truy vấn, in ra một số nguyên duy nhất trên một dòng:

• Nếu tồn tại người sếp cao hơn nhân viên \(x\) đúng \(k\) bậc, hãy in số hiệu của người đó.
• Nếu không tồn tại người sếp cách \(x\) đúng \(k\) bậc, hãy in \(-1\).

Example

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

3
1
-1

Scoring

Trong tất cả các test :

• \(1 \leq n, q \leq 2 \times 10^5\)
• \(1 \leq e_i \leq i-1\) với \(2 \leq i \leq n\)

• \(1 \leq x \leq n\), \(0 \leq k \leq n\)

• \(50\%\) số test có \(n, q \leq 5000\).

• \(50\%\) số test còn lại không có ràng buộc gì thêm.