Tree Weight Query

You are given a rooted tree with \(n\) vertices (numbered from 1 to \(n\)). The tree is described by specifying the parent for every node except node 1 which is the root. Each vertex \(i\) has a weight function \(v(t,i)\) defined as follows:

• At time \(t=0\), the weight \(v(0,i)\) is provided. It is guaranteed that for non-leaf nodes, \(v(0,i)=0\), and for leaf nodes, \(0 \le v(0,i) \le n\).
• For leaf nodes, \(v(t,i)=v(0,i)\) for all \(t \ge 0\).
• For internal (non-leaf) nodes and for \(t>0\), the weight is defined recursively by \[ v(t,i)=\max_{j\in \text{child}(i)} v(t-1,j). \]</p>

In other words, for an internal node \(i\):

• If \(t=0\), \(v(0,i)=0\).
• If \(t\ge 1\), then \(v(t,i)\) equals the maximum \(v(0,\cdot)\) among all leaf descendants in the subtree of \(i\) (since the recurrence propagates the maximum leaf value upward).

You are then given \(m\) queries. Each query provides three integers \(x, y, t\) and asks you to compute on the unique simple path from vertex \(x\) to vertex \(y\) (including both endpoints) the following three values at time \(t\):

1. The minimum weight,
2. The maximum weight,
3. The sum of the weights.

Input Format: (see below)

Output Format: (see below)

inputFormat

The first line contains two integers \(n\) and \(m\): the number of vertices and the number of queries.

The second line contains \(n\) integers \(v(0,1), v(0,2), \ldots, v(0,n)\). Note that for any non-leaf node the value is guaranteed to be 0, and the leaf nodes have values between 0 and \(n\).

The third line contains \(n-1\) integers: for vertices \(2, 3, \ldots, n\), the \(i\)th integer denotes the parent of vertex \(i\). Vertex \(1\) is the root.

Each of the next \(m\) lines contains three integers \(x, y, t\), representing a query on the path from vertex \(x\) to vertex \(y\) at time \(t\).

outputFormat

For each query, output three space‐separated integers: the minimum weight, the maximum weight, and the sum of the weights along the path from \(x\) to \(y\) at time \(t\).

sample

5 3
0 0 2 5 3
1 1 2 2
4 3 0
4 3 1
2 5 2

0 5 7
2 5 17
3 5 8

</p>