문제
정올국은 N개의 도시가 트리 형태로 연결되어 있는 모양이다. 각 도로는 현재 전체적으로 노후되어 있기에 정올국의 대통령인 준혁이는 돈을 들여 도로를 개선하기로 한다.
i번째 도로는 현재 제한 속도 si, 개선하는데 드는 비용 ci, 개선 뒤 제한 속도 vi의 세 정수로 표현할 수 있다. 이때 si<vi를 항상 만족한다.
도로 개선 계획이 Q개 수립되었다. 각 계획은 도시 두개 ui와 vi와 사용 가능 비용 ei로 표현할 수 있는데, ui와 vi를 잇는 경로상의 도로를 최대 ei의 비용을 사용하여 개선하겠다는 뜻이다. 이때 개선 방법은 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대화하는 방법으로 하기로 했다.
각 개선 계획에 대해 ui와 vi를 잇는 도로 상의 최소 제한 속도를 최대 ei의 비용을 사용해서 최대화하여라.
입력
첫 줄에 도시의 개수 N (1<=N<=100000)이 주어진다.
그 다음 N-1줄에 걸쳐 도로의 정보 xi, yi, si, ci, vi가 순서대로 주어진다. 이는 xi와 yi 사이를 잇는 도로의 정보를 뜻한다. (1<=si<vi<=10^9, 1<=ci<=10^9)
그 다음 개선 계획의 개수 Q(1<=Q<=100000)이 주어진다.
그 다음 Q줄에 걸쳐 개선 계획 ui, vi, ei가 주어진다. (1<=ei<=10^18)
Subtask #1(21점) : N, Q<=1000
Subtask #2(29점) : 각 도시는 최대 2개의 다른 도시와 연결되어있다.
Subtask #3(60점) : 제한 없음
출력
Q줄에 걸쳐 각 쿼리의 답을 출력하시오.
예제1
6
125710
13489
347115
356311
36568
3
2415
645
3510
7
5
11
예제2
4
12558
23469
346107
4
1416
2416
1410
3410
6
7
5
7