[LNOI2014]LCA

题目描述

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

说明

共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。