Qiangqiang and Mengmeng are good friends. One day, while strolling outside, they suddenly saw a Bauhinia tree in front of them. It is the season for Bauhinia flowers to dance, and countless petals are growing from the tree at a speed visible to the naked eye.

Looking closely, this large tree is actually a weighted tree. At each moment, it grows a new leaf node. Each node has a cute sprite on it, and a new sprite also appears on the newly grown node. Sprites are cute but also very fragile creatures. Each sprite $i$ has a sensitivity value $r_i$. Sprites $i$ and $j$ become friends if and only if the distance between $i$ and $j$ on the tree, $\text{dist}(i, j)$, satisfies $\text{dist}(i, j) \le r_i + r_j$, where $\text{dist}(i, j)$ denotes the sum of edge weights on the unique path between $i$ and $j$ on the tree.

Qiangqiang and Mengmeng are curious about the total number of pairs of friends on the tree after each new leaf node is added.

We assume the tree is initially empty, and nodes are numbered starting from 1 in the order they are added. Since Qiangqiang is very curious, you must provide the total number of friend pairs immediately after each new node appears, without delay.

Input

The input contains $n + 2$ lines.

The first line contains a positive integer, representing the test case number.

The second line contains a positive integer $n$, representing the total number of nodes to be added.

Let last_ans be the total number of friend pairs before adding a node, which is 0 at the beginning.

In the following $n$ lines, the $i$-th line contains three numbers $a_i, c_i, r_i$, representing that the parent of node $i$ is $a_i \oplus (\text{last\_ans} \pmod{10^9})$ (where $\oplus$ denotes XOR, and $\pmod{}$ denotes modulo; it is guaranteed that the result of this operation is between 1 and $i-1$), the edge weight between node $i$ and its parent is $c_i$, and the sensitivity value of the sprite on node $i$ is $r_i$.

Note that $a_1 = c_1 = 0$, indicating that node 1 is the root. For $i > 1$, the parent's index is at least 1.

Output

The output contains $n$ lines, each outputting 1 integer, representing the number of friend pairs on the tree after adding the $i$-th node.

Examples

Input 1

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

Output 1

0
1
2
4
7

Input 2

See flower/flower.in and flower/flower.ans in the contestant directory.

Constraints

For all data, $1 \le c_i \le 10000$, $a_i \le 2 \times 10^9$, $r_i \le 10^9$.