5988 - NOI：树链剖分：LCA累计和

给出一个 n 个节点的有根树（编号为 0 到 n-1，根节点为 0）。

一个点的深度定义为这个节点到根的距离 +1。

设 dep[i] 表示点 i 的深度，\operatorname{LCA}(i, j) 表示 i 与 j 的最近公共祖先。

有 m 次询问，每次询问给出 l, r, z，求 \sum_{i=l}^r dep[\operatorname{LCA}(i,z)] 。

第一行 2 个整数，n, m。

接下来 n-1 行，分别表示点 1 到点 n-1 的父节点编号。

接下来 m 行，每行 3 个整数，l, r, z。

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

数据范围及约定

• 对于 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。