eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Inspector is Coming

Inspector is Coming

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

After the New Great Technical Revolution in 2017 Mankind decided to conquer the entire Universe. In 2030 first spaceships were constructed and several expeditions were organized away from the Solar System. These expeditions were aimed at colonization of new planets.

In 2032 one of the spaceships reached ZetaX and the expedition met the aboriginal population. Colonization of that planet was a hard task. There were desperate struggles for every meter of the territory. As soon as the army conquered a considerable part of the land, they built a base station there to hold the territory and protect it from the enemy. A road to another base station was laid as well. But since any sort of construction during the war is a very risky business, they built exactly one road to an already existing station. There was only one army conquering ZetaX, so base stations appeared successively one by one.

Now the war is over, the army is gone, and N base stations are still on the planet. However, there is still much work to be done. Before ordinary people are allowed to come and settle here, the planet must be checked by a special Imperial inspection. Inspector Mr. Subtle has come to the planet from the Earth. He seems to be very unfriendly. He doesn’t want to confirm that the planet is livable until the road system works well enough. Inspector formulated some silly improvements to be made. He tried to make them as hard as possible to get a bribe, but nobody wants to pay him.

The requirements are: it is necessary to improve all roads that are on the way from base station u to base station v and have length from W_min to W_max. Inspector made Q such requirements.

Find the number of roads it is necessary to improve and Inspector will have to mark ZetaX as livable.

Вхідні дані

The first line of the input file contains N (2N100000) — the number of base stations. Each of the next N-1 lines contains three integers a_i, b_i and w_i (1a_i, b_iN, 1w_i1000000) — the descriptions of the roads in arbitary order. The next line contains an integer Q (0Q100000) — the number of requirements. Each of the next Q lines contains four integers u, v, W_min, and W_max (1u, vN, 1W_minW_max1000000) — the requirements themselves.

Вихідні дані

One integer — the number of roads it is needed to improve.

Приклад

Вхідні дані #1
3
1 2 20
2 3 10
2
1 3 5 15
1 3 15 25
Вихідні дані #1
2