有原数据惹。

但是还是现在 LG 上过了再来卡评测喵

题目描述

给以棵树，边有边权，点有权值 $r_i$，统计有多少点对 $(i,j)$ 满足 $i < j, dis(i,j)\leq r_i+r_j$

树一开始只有一个点，之后每次加一个叶子，每次加完之后你要回答上述问题的答案，强制在线。

$n\leq 10^5$。

输入格式

第一行包含一个整数， 表示测试点编号。

第二行包含一个正整数 $n$，表示总共要加入的节点数。

我们令上一次询问的答案为 $last_ans$，在一开始时它的值为 0。

接下来 $𝑛$ 行中第 $𝑖$ 行有三个非负整数 $𝑎𝑖,𝑐𝑖,𝑟𝑖$，表示结点 𝑖 的父节点的编号为 $𝑎_𝑖\oplus(last_ans\bmod10^9)$(数据保证这样操作后得到的结果介于 1 到 $𝑖−1$ 之间），与父结点之间的边权为 $c_i$，节点 $𝑖$ 上的点权为 $𝑟_𝑖$。

特别的，$a_1=c_1=0$

输出格式

$n$ 行，每行一个数表示加入第 $i$ 个节点后的答案。

样例输入

0
5
0 0 6
1 2 4
0 9 4
0 5 5
0 2 4

样例输出

0
1
2
4
7

数据范围

$1\leq c_i\leq 10^4,a_i\leq 2\times 10^9, r_i\leq 10^9$。