Ancestor

Input

The first line contains an integer $n$ (1 \le n \le 10^5), the number of vertices in the tree.

The second line contains $n$ integers, where the $i$-th number represents the parent of the vertex numbered $i$. If the value is $0$, the vertex is the root of the tree.

The third line contains an integer $m$ (1 \le m \le 10^5), the number of queries.

Each of the following $m$ lines contains two distinct integers $a$ and $b$ (1 \le a, b \le n), representing a query.

Output

For each of the $m$ queries, print $1$ on a separate line if vertex $a$ is an ancestor of vertex $b$, and $0$ otherwise.

Examples