Parent

Write a program that determines for two nodes of a tree whether the first one is a parent of another.

Input

The first line contains the number of vertices $n(1\le n\le 10^5)$ in a tree. The second line contains $n$ numbers, the $i$-th one gives the vertex number of direct ancestor for the vertex $i$. If this value is zero, then the vertex is a root of a tree.

The third line contains the number of queries $m(1\le m\le 10^5)$. Each of the next $m$ lines contains two different numbers $a$ and $b(1\le a,b\le n)$.

Output

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

Examples