Given a rooted tree with $n$ vertices, each vertex $i$ has a weight $v(t, i)$ at time $t$.

For each vertex, $v(0, i)$ is given. It is guaranteed that for non-leaf nodes $i$, $v(0, i) = 0$, and for leaf nodes $i$, $0 \le v(0, i) \le n$.

There are $m$ queries. Each query provides $x, y, t$, and asks for the minimum, maximum, and sum of the weights on the path from $x$ to $y$ at time $t$.

For leaf nodes $i$, $v(t, i) = v(0, i)$.

For non-leaf nodes $i$ and $t > 0$, $v(t, i)$ is the maximum of $v(t-1, j)$ for all children $j$ of $i$.

Input

The first line contains two integers $n$ and $m$.

The next $n-1$ lines each contain an integer, representing $f_2, \dots, f_n$ respectively, where $f_i$ is the parent of node $i$. The root is $1$.

The next $n$ lines each contain an integer, representing $v(0, 1), v(0, 2), \dots, v(0, n)$ respectively.

The next $m$ lines each contain three integers representing $x, y, t$.

Output

Output $m$ lines, each containing three integers representing the answer to each query.

Examples

Input 1

8 3
1
2
3
3
3
4
4
0
0
0
0
7
5
7
5
7 5 8
1 2 8
8 2 8

Output 1

7 7 28
7 7 14
5 7 26

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, $1 \le n, m \le 10^6$, $1 \le f_i \le i-1$, $0 \le v(0, i) \le n$, $1 \le x, y, t \le n$.