K. Bocchi the Tour
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After barely surviving her finals, Bocchi has decided to tour the country to do some sightseeing!

The country can be described by $$$n$$$ cities connected by $$$n - 1$$$ roads. The $$$i$$$-th road connects cities $$$u_i$$$ and $$$v_i$$$ with length $$$l_i$$$. It is possible to visit all the cities starting from any city using a sequence of roads.

Being an introvert, Bocchi hasn't seen much of the country, so she wants to visit as many cities as possible. However, she won't think a city is exciting if she has visited it within the last $$$k$$$ weeks. For example, if she visits some city on week $$$w,$$$ regardless of whether or not she thinks the city is exciting, she will not find the city exciting again before week $$$w+k$$$, at which point she will find it exciting again.

Bocchi is planning on going on $$$q$$$ tours. Specifically, for her $$$i$$$-th tour, she will start on week $$$w_i$$$ (there are many weeks in the strange land of Bocchi!) and start from city $$$u_i.$$$ But because Bocchi doesn't like being on the road for too long, she will travel to every city she can reach, as long as the length of each individual road does not exceed $$$s_i$$$. Each tour takes one week, and she can't be on multiple tours in the same week.

Bocchi is lazy and doesn't want to replan her tours. Please help her determine, for each tour, how many exciting cities she visits.

Input

The first line contains three integers $$$n, q, $$$ and $$$k$$$ $$$(1\leq n, q\leq 10^5, 1\leq k\leq 10^9)$$$ — the number of cities, the number of tours, and the amount of time before she thinks a city will become exciting again, respectively.

The next $$$n-1$$$ lines contain three integers $$$u_i, v_i, $$$ and $$$l_i$$$ $$$(1\leq u_i, v_i\leq n, 1\leq l_i\leq 10^9)$$$, representing a road of length $$$l_i$$$ connecting cities $$$u_i$$$ and $$$v_i$$$.

The next $$$q$$$ lines contain three integers $$$w_i, u_i, $$$ and $$$s_i$$$ $$$(1\leq u_i\leq n, 1\leq w_i, s_i\leq 10^9)$$$ — the week the $$$i$$$-th tour is on, the starting city, and the maximum length road Bocchi is willing to go through.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1-2$$$ satisfies $$$n = 100$$$, $$$q = 100$$$, and $$$k\leq 1000$$$.

Test $$$3-10$$$ satisfies that there is a road between city $$$i$$$ and city $$$i+1$$$ for $$$1 \leq i \leq n-1$$$

Tests $$$11-20$$$ satisfy no additional constraints.

Output

For each of Bocchi's $$$Q$$$ tours, output a single integer — the number of exciting cities she visits.

Examples
Input
4 5 2
1 2 8
2 3 3
2 4 5
1 2 4
2 4 7
4 4 7
5 3 8
10 2 10
Output
2
1
3
1
4
Input
10 10 5
3 9 24
2 3 45
1 5 20
1 6 11
6 8 26
1 4 26
3 7 26
5 7 36
5 10 40
1 4 37
6 7 32
9 9 12
16 10 45
25 7 8
27 3 1
35 6 45
39 3 34
44 5 8
45 8 44
Output
8
3
0
10
1
1
10
0
1
8
Note

In the first sample:

In Bocchi's first tour on week $$$1$$$, she visits city $$$2$$$ and city $$$3$$$, both of which she finds exciting.

In Bocchi's second tour on week $$$2$$$, she visits cities $$$2$$$, $$$3$$$, and $$$4$$$, but she only finds city $$$4$$$ exciting.

In Bocchi's third tour on week $$$4$$$, she visits the same $$$3$$$ cities, and finds them all exciting.

—

Problem Idea: training4usaco

Problem Preparation: training4usaco

Occurrences: Advanced K