Genetic Difference

Problem statement

In a family of $N$ people, individuals are numbered from $0$ to $N-1$ and each individual has a unique binary representation. The genetic difference between two individuals is calculated as the XOR of their binary representations. For example, if two individuals in a family are denoted by $1$ and $2$, then their genetic difference is calculated as $1 \space XOR \space 2 = 3$.

You're provided with an integer array parent, where $parent[i]$ is the parent of an individual $i$. Also, the head (root) of the family does not have any parent, so the value of parent for root is $-1$. The scientists are now comparing the individuals in this family with a new external individual, and they wish to find the person in this family who is genetically most dissimilar to this new individual. But to limit the search space, they define the limit on the people to whom they'll be comparing the new individual.

You are given $Q$ queries in the format $(node_i, value_i)$. For every query, find the maximum genetic difference between $value_i$ and $p_i$, where $p_i$ is the genetic value of any node that's on the path between $node_i$ and the root (including $node_i$ and the root). In other words, maximize $value_i$ XOR $p_i$.

Example

Sample input