Description

This summer, NOI celebrates its 30th anniversary in SZ City. OIers from $n$ cities across the country will set off from their respective locations to attend this grand event in SZ City.

The cities in the country form a rooted tree with SZ City as the root, where each city is connected to its parent by a road. For convenience, we label the $n$ cities with integers from $1$ to $n$. SZ City is labeled $1$. For any city other than SZ City, we are given its parent city $f_v$ and the length of the road to its parent $s_v$.

The method to travel from city $v$ to SZ City is as follows: choose an ancestor $a$ of city $v$, pay the ticket fare, and travel to $a$ using transportation. Then, choose an ancestor $b$ of city $a$, pay the fare, and travel to $b$. Repeat this process until SZ City is reached.

For any city $v$, we are given a distance limit $l_v$ for the transportation. For an ancestor $a$ of city $v$, city $v$ can reach city $a$ in one trip if and only if the total length of all roads between them does not exceed $l_v$; otherwise, it cannot be reached in one trip. For each city $v$, we are also given two non-negative integers $p_v, q_v$ as fare parameters. If the total length of all roads from city $v$ to city $a$ is $d$, then the ticket fare from city $v$ to city $a$ is $d \times p_v + q_v$.

Every city's OIer wants to minimize the total ticket fare spent to reach SZ City. Your task is to tell the OIers from each city the minimum total cost they need to spend.

Input

Read data from the file ticket.in.

The first line of the input file contains two non-negative integers $n, t$, representing the number of cities and the data type (its meaning will be explained later).

The next $n-1$ lines each describe a city other than SZ City. The $v$-th line (for cities $2$ to $n$) contains 5 non-negative integers $f_v, s_v, p_v, q_v, l_v$, representing the parent city of city $v$, the length of the road to its parent, the two fare parameters, and the distance limit, respectively.

Note: The input does not include SZ City (labeled 1). The 2nd to $n$-th lines describe cities 2 through $n$, respectively.

Output

Output to the file ticket.out.

The output contains $n-1$ lines, each containing one integer. The $v$-th line represents the minimum ticket fare to reach SZ City starting from city $v+1$.

Note: The output does not include SZ City (labeled 1).

Examples

Input 1

7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10

Output 1

40
150
70
149
300
150

Note 1

The example is shown in the figure on the right.

The routes from each city to SZ are as follows (arrows indicate a direct trip):

City 2: Can only choose $2 \to 1$, cost is $2 \times 20 + 0 = 40$.

City 3: Can only choose $3 \to 1$, cost is $5 \times 10 + 100 = 150$.

City 4: Since $4 + 2 = 6 \le l_4 = 10$, one can choose $4 \to 1$. If choosing $4 \to 1$, the cost is $(4 + 2) \times 10 + 10 = 70$; if choosing $4 \to 2 \to 1$, the cost is $(4 \times 10 + 10) + (2 \times 20 + 0) = 90$; therefore, choose $4 \to 1$.

City 5: Can only choose $5 \to 2 \to 1$, cost is $(9 \times 1 + 100) + (2 \times 20 + 0) = 149$; cannot choose $5 \to 1$ because $l_5 = 10$, but the total distance from city 5 to city 1 is $9 + 2 = 11 > l_5$, so city 5 cannot reach city 1 directly.

City 6: If choosing $6 \to 1$, cost is $(5 + 5) \times 20 + 100 = 300$; if choosing $6 \to 3 \to 1$, cost is $(5 \times 20 + 100) + (5 \times 10 + 100) = 350$; therefore, choose $6 \to 1$.

City 7: Choose $7 \to 4 \to 1$, cost is $(4 \times 20 + 0) + ((4 + 2) \times 10 + 10) = 150$; other schemes are worse than this one.

Examples

Input 2

See ticket/ticket.in and ticket/ticket.ans in the contestant directory.

This set of examples is divided into 4 parts almost equally by city index, with each part having different characteristics. You can use them for targeted testing.

Constraints

For all test data, it is guaranteed that $0 \le p_v \le 10^6$, $0 \le q_v \le 10^{12}$, $1 \le f_v < v$; it is guaranteed that $0 < s_v \le l_v \le 2 \times 10^{11}$, and the total distance from any city to SZ City does not exceed $2 \times 10^{11}$.

The input $t$ represents the data type, $0 \le t < 4$, where:

• When $t = 0$ or $2$, for all input cities $v$, $f_v = v - 1$, meaning all cities form a chain ending at SZ City.
• When $t = 0$ or $1$, for all input cities $v$, $l_v = 2 \times 10^{11}$, meaning there is no distance limit, and every city can reach all its ancestors.
• When $t = 3$, the data has no special properties.

The $n$ and $t$ for each test case are as follows:

Note

During final evaluation, there is no separate limit on the space occupied by the call stack. If your program involves stack overflow issues, please read ticket/stack.pdf. Note that the space occupied by the call stack is counted towards the total memory usage and is subject to the memory limit along with other parts of the program.

The input and output of the data require the use of 64-bit integers. If you need to multiply two 64-bit integers in your calculation, please be sure to check whether the result will overflow.