Under construction

Still being built. Things may change

Electric power transmission

Time limit3sMemory limit1024 MB

Summary
On a tree of wires where each wire has a threshold and divisor loss, answer queries for how much electricity reaches tower b when e units are sent from tower a.
Level

Medium6 of 10

Topics
Tree, Math
Solved
No attempts yet

Problem

You are the president of Juwon Power Company. Juwon Power Company owns NN power towers numbered 1 through NN. Of these towers, N−1N-1 pairs are connected by wires, and the wires are numbered 1 through N−1N-1. Wire ii connects tower xix_i and tower yiy_i. Every tower is connected to every other tower through the wires.

Background

Electricity demand changes from moment to moment, so sending electricity from one tower to another happens often. The problem is that the quality of a wire causes loss when electricity travels along it.

Wire ii has resistance rir_i and loss coefficient ziz_i. If ee units of electricity are sent from one tower to a neighboring tower through wire ii, then only ⌊max⁡(e−ri,0)zi⌋\left\lfloor\frac{\max(e-r_i,0)}{z_i}\right\rfloor units arrive.

You must answer QQ queries.

  • If you send ee units of electricity from tower aa to tower bb, what is the maximum amount of electricity tower bb can receive?

Input

The first line contains NN. The next N−1N-1 lines each contain xix_i, yiy_i, rir_i, and ziz_i, separated by spaces. The line after those contains QQ. The next QQ lines each contain aa, bb, and ee, separated by spaces.

Output

For each query, print the answer on its own line, in the order the queries are given.

Constraints

  • 2≤N≤100 0002 \le N \le 100\,000
  • 1≤xi,yi≤N1 \le x_i, y_i \le N (1≤i≤N−11 \le i \le N-1)
  • 1≤ri,zi≤1091 \le r_i, z_i \le 10^9 (1≤i≤N−11 \le i \le N-1)
  • 1≤Q≤100 0001 \le Q \le 100\,000
  • 1≤a,b≤N1 \le a, b \le N, a≠ba \neq b
  • 1≤e≤10181 \le e \le 10^{18}

Examples1

  1. Example 1

    Input
    5
1 2 20 23
3 1 1 4
3 4 2 2
3 5 3 1
3
5 4 23
4 5 23
1 5 1
    Expected output
    9
7
0