Problem Description
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≤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≤n≤50000,1≤q<100000).
The second line contains n−1 integers Ai(1≤Ai≤i) represent the node i+1's father is node Ai.
The third line contains n integers Bi(1≤i≤n,0≤Bi≤1000) represent the node i's weight is Bi.
Then q line follow,each line contains two integers u,v,it represents a query(1≤u,v≤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)
Sample Input
1
5 1
1 2 3 4
413 127 263 869 960
1 5
Sample Output
1373 960