승차권 구매

이번 여름 NOI가 SZ시에서 30번째 생일을 맞는다. 전국 $n$개 도시의 OI 참가자들이 축하 행사에 참여하려고 SZ시에 모인다.

전국의 $n$개 도시는 SZ시를 루트로 하는 트리를 이룬다. 각 도시는 도로로 부모 도시와 연결되어 있다. 설명을 간단히 하려고 $n$개 도시에 1부터 $n$까지 서로 다른 번호를 붙였다. SZ시의 번호는 1이다. SZ시가 아닌 도시 $v$의 부모는 $f_v$이며, 둘을 잇는 도로의 길이는 $s_v$이다.

도시 $v$에서 SZ시까지 가는 방법은 다음과 같다. $v$의 조상 $a$를 골라 승차권을 사고 대중교통으로 $a$시까지 간다. 그다음 $a$의 조상 $b$를 골라 승차권을 사서 그곳까지 간다. SZ시에 도착할 때까지 이 과정을 반복한다.

각 도시 $v$에는 대중교통의 거리 제한 $l_v$가 있다. $v$의 조상 $a$에 대해, $v$에서 $a$까지 도로 길이의 합이 $l_v$를 넘지 않는 경우에만 승차권 한 장으로 $v$에서 $a$까지 바로 갈 수 있다. 또한 각 도시 $v$에는 음이 아닌 정수 $p_v$와 $q_v$가 주어진다. $v$에서 $a$까지 도로 길이의 합이 $d$이면, 이 구간의 승차권 요금은 $d \cdot p_v + q_v$이다.

각 OI 참가자는 가장 적은 총 요금으로 SZ시에 도착하려고 한다. 각 도시에서 SZ시까지 가는 데 필요한 최소 총 요금을 구하라.

첫 줄에는 음이 아닌 정수 $n$과 $t$가 주어진다. 각각 도시의 수와 테스트 케이스의 종류를 나타낸다.

2번째 줄부터 $n$번째 줄까지 SZ시가 아닌 도시를 설명한다. $v$번째 줄에는 음이 아닌 정수 $f_v$, $s_v$, $p_v$, $q_v$, $l_v$가 순서대로 주어진다. 각각 부모 도시, 부모와의 도로 길이, 승차권 요금 매개변수, 거리 제한을 뜻한다. 입력에는 번호 1인 SZ시가 포함되지 않는다. 2번째 줄은 2번 도시, 3번째 줄은 3번 도시에 대응하며, $n$번째 줄까지 이어진다.

$n-1$개의 줄을 출력한다. $v$번째 줄에는 도시 $v+1$에서 SZ시까지 가는 최소 총 승차권 요금을 정수 하나로 출력한다. SZ시의 답은 출력하지 않는다.

모든 테스트 케이스는 다음을 만족한다.

• $0 \le p_v \le 10^6$, $0 \le q_v \le 10^{12}$
• $1 \le f_v < v$
• $0 < s_v \le l_v \le 2 \times 10^{11}$
• 임의의 도시에서 SZ시까지의 총 거리는 $2 \times 10^{11}$을 넘지 않는다.
• $1 \le n \le 200000$

입력값 $t$는 테스트 케이스의 종류를 나타내며, $0 \le t < 4$이다.

• $t=0$ 또는 $t=2$이면 모든 $v$에 대해 $f_v = v-1$이다. 도시들이 SZ시를 한쪽 끝으로 하는 사슬을 이룬다.
• $t=0$ 또는 $t=1$이면 모든 $v$에 대해 $l_v = 2 \times 10^{11}$이다. 거리 제한이 없으므로 모든 도시에서 모든 조상으로 바로 갈 수 있다.
• $t=3$이면 별도의 특별한 조건이 없다.