Description

You are given a rooted tree with $n$ nodes (numbered from $0$ to $n - 1$), with root $0$.

The depth of a node is defined as its distance to the root $+1$.

Let $dep[i]$ denote the depth of node $i$, and let $\operatorname{LCA}(i, j)$ denote the lowest common ancestor of $i$ and $j$.

There are $m$ queries. For each query with given $l, r, z$, compute $\sum_{i=l}^{r} dep[\operatorname{LCA}(i, z)]$.

Input Format

• The first line contains $2$ integers $n, m$.
• The next $n - 1$ lines give parent indices: for each $i$ from $1$ to $n - 1$, the $i$-th of these lines contains the parent of node $i$.
• The next $m$ lines each contain $3$ integers $l, r, z$.

Output Format

Output $m$ lines. Each line contains the answer for one query, taken modulo $201314$.

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

8
5

Hint

Constraints

• For $20\%$ of the testdata, $n \le 10000$, $m \le 10000$.
• For $40\%$ of the testdata, $n \le 20000$, $m \le 20000$.
• For $60\%$ of the testdata, $n \le 30000$, $m \le 30000$.
• For $80\%$ of the testdata, $n \le 40000$, $m \le 40000$.
• For $100\%$ of the testdata, $1 \le n \le 50000$, $1 \le m \le 50000$.

Translated by ChatGPT 5