My Ancestor

Source: Thailand ICPC National

Version: Phuoc Hung OJ Extended

Problem Statement

A rooted family tree has root vertex $1$. Each vertex $v$ has a positive value $w_v$. For every parent-child edge $p\to v$, $w_p<w_v$, so values are strictly increasing on every root-to-vertex path.

For each query $(v,P)$, find the proper ancestor of $v$ that is closest to the root and whose value is at least $P$. Print $-1$ if no such ancestor exists. The PHOJ version fixes root $1$ and explicitly lists the parent of every vertex $2,\ldots,n$.

Input

• The first line contains $n,q$.
• The second line contains $w_1,\ldots,w_n$.
• The third line contains parents $p_2,\ldots,p_n$, with $1\le p_i<i$.
• Each of the next $q$ lines contains $v,P$.

Output

For each query, print the required ancestor index or -1.

Subtasks

• Subtask 1 — 20%: $n,q\le200$, $w_i\le10^6$.
• Subtask 2 — 30%: $n\le5000$, $q\le5000$, $w_i\le10^9$.
• Subtask 3 — 50%: $n\le80000$, $q\le20000$, $w_i\le10^9$, and $w_{p_i}<w_i$.

Example

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

Explanation

For vertex $5$, proper ancestors have values $3,5$; threshold $4$ selects vertex $2$. For vertex $7$, no proper ancestor reaches threshold $8$.