[LNOI2014]LCA

题目描述

给出一个 $n$ 个节点的有根树(编号为 $0$ 到 $n-1$,根节点为 $0$)。 一个点的深度定义为这个节点到根的距离 $+1$。 设 $dep[i]$ 表示点i的深度,$LCA(i,j)$ 表示 $i$ 与 $j$ 的最近公共祖先。 有 $q$ 次询问,每次询问给出 $l\ r\ z$,求 $\sum_{i=l}^r dep[LCA(i,z)]$ 。

输入输出格式

输入格式


第一行 $2$ 个整数,$n, q$。 接下来 $n-1$ 行,分别表示点 $1$ 到点 $n-1$ 的父节点编号。 接下来 $q$ 行,每行 $3$ 个整数,$l, r, z$。

输出格式


输出 $q$ 行,每行表示一个询问的答案。每个答案对 $201314$ 取模输出。

输入输出样例

输入样例 #1

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

输出样例 #1

8
5

说明

对于 $20\%$ 的数据,$n\le 10000,m\le 10000$; 对于 $40\%$ 的数据,$n\le 20000,m\le 20000$; 对于 $60\%$ 的数据,$n\le 30000,m\le 30000$; 对于 $80\%$ 的数据,$n\le 40000,m\le 40000$; 对于 $100\%$ 的数据,$1\le n\le 50000,1\le m\le 50000$。