31094번 - 전기 전송

당신은 주원 전력 공사의 사장이다. 주원 전력 공사는 $1$번부터 $N$번까지 총 $N$개의 전력탑을 보유하고 있다.

그 중 $N-1$개의 전력탑 쌍은 서로 전선으로 이어져 있고, 전선에는 $1$번부터 $N-1$번까지 번호가 붙어 있다. $i$번 전선은 $x_i$번 전력탑과 $y_i$번 전력탑을 잇는다. 모든 전력탑은 전선을 통해 서로 이어져 있다.

전기의 수요는 시시각각 변하므로, 한 전력탑에서 다른 전력탑으로 전기를 보내야 하는 경우가 자주 생긴다. 문제는, 전기를 보낼 때 전선의 품질에 따라 손실이 발생한다는 것이다.

$i$번 전선의 저항은 $r_i$이고, 손실계수는 $z_i$이다. 한 전력탑에서 $i$번 전선을 통해 이어진 전력탑으로 전기를 $e$만큼 보내면, $\displaystyle\left\lfloor\frac{\max(e-r_i,0)}{z_i}\right\rfloor$ 만큼의 전기만이 도착하게 된다.

당신은 $Q$개의 질의를 처리해야 한다.

• $a$번 전력탑에서 $e$만큼의 전기를 $b$번 전력탑으로 보내려고 할 때, $b$번 전력탑에서 받을 수 있는 전기의 최댓값은 얼마인가?

첫째 줄에 전력탑의 수 $N$이 주어진다.

다음 $N-1$개의 줄에 $x_i$, $y_i$, $r_i$, $z_i$가 공백을 사이에 두고 차례로 주어진다.

$N+1$번째 줄에 질의의 수 $Q$가 주어진다.

다음 $Q$개의 줄에 질의 $a$, $b$, $e$가 공백을 사이에 두고 차례로 주어진다.

각 질의의 답을 순서대로 한 줄에 하나씩 출력하라.

• $2\le N\le 100\, 000$
• $1\le x_i,y_i\le N$ ($1\le i\le N-1$)
• $1\le r_i,z_i\le 10^9$ ($1\le i\le N-1$)
• $1\le Q\le 100\, 000$
• $1\le a,b\le N$, $a\neq b$
• $1\le e\le 10^{18}$