Problems
Parent
Parent
Write a program that determines for two nodes of a tree whether the first one is a parent of another.
Input data
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 data
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
Input example #1
6 0 1 1 2 3 3 5 4 1 1 4 3 6 2 6 6 5
Output example #1
0 1 1 0 0