Một công ty có \(n\) nhân viên, tạo thành một hệ thống phân cấp dạng cây trong đó mỗi nhân viên, ngoại trừ tổng giám đốc đều có một ông chủ.

Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: ai là người sếp chung thấp nhất của nhân viên \(a\) và \(b\) trong hệ thống phân cấp?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q:\) số lượng nhân viên và truy vấn. Các nhân viên được đánh số \(1,2,... ,n\) và người số \(1\) là tổng giám đốc.
• Dòng tiếp theo có \(n−1\) số nguyên \(e_2,e_3,\dots,e_n:\) người chủ mỗi nhân viên \(2,3,...,n\).
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(a\) và \(b\) ứng với câu hỏi: "Ai là chủ chung thấp nhất của nhân viên \(a\) và \(b\)?"

Output

• In câu trả lời cho mỗi truy vấn.

Constraints

• \(1 ≤ n,q ≤ 2⋅10^5\)
• \(1 ≤ e_{i} ≤ i − 1\)
• \(1 ≤ a,b ≤ n\)

Example

Sample Input

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

Sample Output

3
1
1