题目描述

给出一个 n 个节点的有根树（编号为 0 到 n-1，根节点为 0）。 一个点的深度定义为这个节点到根的距离 +1。 设 dep[i] 表示点 i 的深度，LCA(i,j) 表示 i 与 j 的最近公共祖先。 有 m 次询问，每次询问给出 l,r,z，求 ∑dep[LCA(i,z)] 其中i=l~r。 ∑是累加运算的意思。

输入格式

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

输出格式

输出 m 行，每行表示一个询问的答案。每个答案对 201314 取模输出。

样例

输入样例 1

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

输出样例 1

8
5

输入样例 2

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

输出样例 2

3
5
3

输入样例 3

10 5
0
0
1
1
2
2
3
3
4
1 5 2
2 7 3
3 9 4
4 10 5
5 10 0

输出样例 3

7
11
14
10
6

提示

数据范围：1≤n≤50000,1≤m≤50000。