There is a rooted tree consisting of n nodes numbered 0 to n - 1 . Each node's number denotes its unique genetic value (i.e. the genetic value of node x is x ). The genetic difference between two genetic values is defined as the bitwise- XOR of their values. You are given the integer array parents , where parents[i] is the parent for node i . If node x is the root of the tree, then parents[x] == -1 .
You are also given the array queries where queries[i] = [node _i , val _i ] . For each query i , find the maximum genetic difference between val _i and p _i , where p _i is the genetic value of any node that is on the path between node _i and the root (including node _i and the root). More formally, you want to maximize val _i XOR p _i .
Return an array ans where ans[i] is the answer to the i ^th query .
2 <= parents.length <= 10 ^50 <= parents[i] <= parents.length - 1 for every node i that is not the root.parents[root] == -11 <= queries.length <= 3 * 10 ^40 <= node _i <= parents.length - 10 <= val _i <= 2 * 10 ^5