There is a tree, $n$ nodes, numbered from $1$ to $n$, each node has a weight, but each leaf node is the father of the root,
we call such a tree as Transmigration tree, The root of each tree is node $1$.
We need to minimize the sum of weights that node $u$ to node $v$ and know who is the biggest weights node in this path.
Input
The first line of the input is a single integer $T (T \leq 10)$, indicating the number of testcases.
Then $T$ testcases follow.In each testcase,
The first line contains two integers $n,q$, the number of nodes and inquiry$(2 \leq n \leq 50000, 1 \leq q < 100000)$.
The second line contains $n - 1$ integers $A_i ( 1 \leq A_i \leq i )$ represent the node $i + 1$'s father is node $A_i$.
The third line contains $n$ integers $B_i ( 1 \leq i \leq n, 0 \leq B_i \leq 1000)$ represent the node $i$'s weight is $B_i$.
Then $q$ line follow,each line contains two integers $u,v$,it represents a query$(1 \leq u,v \leq n)$.
Output
For each query,we should output one line "$x \ y$", where $x$ is the smallest the sum of weights that node $u$ to node $v$ and $y$ is the weight of the biggest weights node in this path.(If there are multiple paths, please calculating the maximum node weights largest)