Problem Description

Given a tree with $n$ vertices, labeled $1,\dots,n$, and a sequence $a_1,\dots,a_{n_0}$ of length $n_0$. There are $m$ queries. Each query gives $l,r,x$. Starting from vertex $x$, move one step toward $a_l,\dots,a_r$ in order, and output the vertex you finally reach.

If $x=y$, then moving one step from vertex $x$ toward $y$ still stays at $x$. Otherwise, you move to the vertex that is adjacent to $x$ on the tree and is closest to $y$.

Input Format

The first line contains three integers $n,n_0,m$.

The next line contains $n-1$ integers, representing $f_2,\dots,f_n$ in order, where $f_i$ is the parent of vertex $i$, and $1$ is the root.

The next line contains $n_0$ integers, representing $a_1,\dots,a_{n_0}$ in order.

The next $m$ lines each contain three integers $l,r,x$, describing one query.

Output Format

Output $m$ lines. Each line is the answer to the corresponding query.

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

3
2
1

Hint

Idea: Ynoi, Solution: zhoukangyang & ccz181078, Code: zhoukangyang, Data: ccz181078.

Constraints: For $100\%$ of the testdata, $1\le n,n_0,m\le 10^6$.

Translated by ChatGPT 5