AQT is suspicious that brainworms are running wild in DMOJistan! To limit the spread of these IQ-reducing creatures, the admins require that cities of DMOJistan quarantine for a specific amount of time.

DMOJistan can be mapped as a tree with $N$ nodes that each represent a city, and $N-1$ edges that represent roads. People can only move between cities by only using the roads. Whenever DMOJ admins orders city $n$ to be in quarantine, starting from the beginning of day $a$ the node $n$, and its neighbouring cities, form a bubble, where they must quarantine until the end of day $b$. This means that no one inside the bubble can go outside the bubble and vice versa. Note that for any day, we can group cities into disjoint sets of cities where two nodes are in the same set if and only if we can visit each city without violating any of the quarantine rules. For each middle of the day (after the beginning and before the end of the day) from day $1$ to day $T$, report the number of such sets.

Constraints

For all subtasks:

$1\le N,Q,T\le 5\cdot {10}^5$

For all $1\le i<N$:

$1\le u_i,v_i\le N$

For all $1\le q\le Q$:

$1\le n_q\le N$

$1\le a_q\le b_q\le T$

Subtask 1 [15%]

$1\le N,Q,T\le 3\cdot {10}^3$

Subtask 2 [60%]

$1\le N,Q,T\le {10}^5$

Subtask 3 [25%]

No additional constraints.

Input Specification

The first line is a single integer $N$.

The next $N-1$ lines where the $i$-th line contains $u_i$ and $v_i$ separated by a space representing that there is a direct road between nodes $u_i$ and $v_i$.

The following line contains $Q$ and $T$ separated by a single space.

The next $Q$ lines each represent a different type of brainworm, where the $q$-th line contains $3$ integers separated by spaces, $n_q$, $a_q$ and $b_q$.

Output Specification

For each day from $1$ to $T$, output the number of such sets described in a problem statement on a new line, where the $t$-th line is the answer of the $t$-th day.

Sample Input 1

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

Sample Output 1

2
5
5
4
3

Explanation for Sample 1

At the beginning of day 1, city 3 will form a bubble with its neighbouring cities.

At the middle of day 1, two sets are formed $\{1,2,3,5\}$ and $\{4\}$.

At the end of day 1, nothing happens.

At the start of day 2, city 2 and 4 will form bubbles with their neighbouring cities.

At the middle of day 2, the sets are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$ and $\{5\}$.

At the end of day 2, nothing happens.

At the start of day 3, city 5 forms a bubble with its neighbouring cities.

At the middle of day 3, the sets are still $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$ and $\{5\}$.

At the end of day 3, city 3 and its neighbouring cities will lift their restrictive measures.

At the start of day 4, city 5 will form another bubble with its neighbouring cities.

At the middle of day 4, the sets are $\{1\}$, $\{2,4\}$, $\{3\}$, $\{5\}$.

At the end of day 4, city 5 and its neighbouring cities lift their first bubble restriction but are still in quarantine from their second bubble restriction, and city 2, and its neighbouring cities, lift their quarantine restriction.

At the start of day 5, nothing happens.

At the middle of day 5, the sets are $\{1\}$, $\{2,4\}$, $\{3,5\}$.

At the end of day 5, the rest of the restrictions are lifted.

Sample Input 2

3
1 2
2 3
3 1
1 1 1
1 1 1
3 1 1

Sample Output 2

3

Explanation for Sample 2

Note that for the only day, $\{1\},\{2\},\{3\}$ are the sets.