Maximizing LCA Depth in a Tree Interval

Given a rooted tree with (n) nodes (numbered from 1 to (n)) and (q) queries, you are to answer queries defined as follows. The tree is rooted at node 1 and each node (u) has a depth (\text{dep}u) defined as the number of nodes on the simple path from (u) to the root (including both ends).

In addition, define (\mathrm{LCA}^(l, r)) as the lowest common ancestor (i.e. the common ancestor with maximum depth) of all nodes whose labels lie in the interval ([l, r]), that is, nodes (l, l+1, \dots, r).

For each query, you are given three integers (l, r, k). The query asks for the maximum possible depth of (\mathrm{LCA}^(l', r')) among all contiguous subintervals ([l', r']) contained in ([l, r]) that have length at least (k). Formally, you need to compute [ \max{l\le l'\le r'\le r ;\land; r'-l'+1\ge k} ; \text{dep}_{\mathrm{LCA}^*(l',r')} ]

Your task is to answer all the queries.

inputFormat

The first line contains two integers (n) and (q) separated by a space, representing the number of nodes and the number of queries respectively.

The second line contains (n-1) integers: (p_2, p_3, \dots, p_n), where (p_i) is the parent of node (i) in the tree.

Each of the next (q) lines contains three integers (l), (r), and (k) describing a query.

outputFormat

For each query, output a single integer on a new line — the maximum depth of the lowest common ancestor for some contiguous subinterval of nodes in ([l, r]) with length at least (k).

sample

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

3
2
1