Tổ tiên của tôi (My Ancestor)

Nguồn: Thailand ICPC National

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một cây gia đình có gốc tại đỉnh $1$. Mỗi đỉnh $v$ có một giá trị nguyên dương $w_v$. Với mọi cạnh từ cha $p$ tới con $v$, luôn có

Vì vậy, trên bất kỳ đường đi nào từ gốc xuống một đỉnh, các giá trị tăng nghiêm ngặt.

Có $q$ truy vấn. Mỗi truy vấn cho một đỉnh $v$ và một ngưỡng $P$. Hãy tìm tổ tiên thực sự của $v$ (không tính chính $v$) gần gốc nhất có giá trị ít nhất $P$.

Nếu không có tổ tiên như vậy, in -1.

Bản PHOJ sử dụng đỉnh $1$ làm gốc và liệt kê cha của các đỉnh $2,3,\ldots,n$.

Input

• Dòng đầu chứa $n,q$.
• Dòng thứ hai chứa $w_1,w_2,\ldots,w_n$.
• Dòng thứ ba chứa $n-1$ số $p_2,p_3,\ldots,p_n$, trong đó $p_i$ là cha của đỉnh $i$ và $1\le p_i<i$.
• $q$ dòng tiếp theo, mỗi dòng chứa $v,P$.

Output

Với mỗi truy vấn, in chỉ số tổ tiên cần tìm hoặc -1 nếu không tồn tại.

Subtask

• Subtask 1 — 20%: $n,q\le200$, $w_i\le10^6$.
• Subtask 2 — 30%: $n\le5000$, $q\le5000$, $w_i\le10^9$.
• Subtask 3 — 50%: $1\le n\le80000$, $1\le q\le20000$, $1\le w_i\le10^9$. Dữ liệu luôn thỏa $w_{p_i}<w_i$.

Ví dụ

Input

7 4
3 5 8 7 10 9 12
1 1 2 2 4 4
5 4
5 7
7 8
2 6

Output

2
-1
-1
-1

Giải thích

Đường tổ tiên của đỉnh $5$ là $1\to2$ với các giá trị $3,5$. Với ngưỡng $4$, tổ tiên gần gốc nhất đạt ngưỡng là đỉnh $2$. Đối với đỉnh $7$, đường tổ tiên là $1\to2\to4$ có giá trị $3,5,7$; ngưỡng $8$ không đạt nên kết quả là $-1$.