In Bajtocja, there are $n$ cities and $m$ bidirectional roads connecting them. Traveling along a road connecting two cities takes one day. The cities are numbered from 1 to $n$. A knight is located in city 1 and wants to reach city $n$ within at most $d$ days, where he is to defeat a powerful beast.

To defeat the beast, the knight will use $k$ swords, each of a different type. The sword types are numbered from 1 to $k$. Each sword has a value, which is a non-negative integer. Initially, the knight has a sword of each type from 1 to $k$, and each sword he possesses has a value of 0.

At each road, there are $k$ craftsmen who are experts in swords. The $j$-th craftsman at the $i$-th road can make the value of the sword of type $j$ equal to $a_{i,j}$. When traveling along a road, the knight can use the services of any subset of craftsmen and modify any subset of his swords in this way. Each sword type can be modified any number of times.

The knight would like the value of the sword of type 1 to be as large as possible; among the options that maximize the value of the sword of type 1, he would like the value of the sword of type 2 to be as large as possible, and so on, up to the sword of type $k$. The order in which the swords of different types are modified does not matter. He is only interested in the final values of the swords.

It is known that it is possible to reach city $n$ from city 1 within at most $d$ days using the road network. The knight can pass through each city and each road multiple times. What swords will the knight be fighting with if he plans his path optimally?

Input

The first line of the input contains four integers $n, m, d$, and $k$ ($2 \le n \le 10\,000$, $1 \le m, d \le 10\,000$, $1 \le k \le 10$), representing the number of cities, the number of roads in Bajtocja, the maximum number of days, and the number of sword types, respectively. Each of the next $m$ lines describes one road using a sequence of $k+2$ integers $u_i, v_i, a_{i,1}, \dots, a_{i,k}$. The numbers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) represent the numbers of the cities connected by the $i$-th road. The number $a_{i,j}$ ($0 \le a_{i,j} \le 10^9$) represents the new value of the sword of type $j$ after choosing it for modification by the craftsman located at the $i$-th road. There may be multiple edges connecting the same cities.

Output

In the only line of the output, print a sequence of $k$ non-negative integers $w_1, \dots, w_k$ separated by single spaces. The number $w_1$ represents the maximum value of the sword of type 1 that the knight can obtain while traveling to city $n$ in at most $d$ days. The number $w_2$ represents the maximum value of the sword of type 2 that the knight can obtain while traveling to city $n$ in at most $d$ days, if he also obtains a sword of type 1 with value $w_1$, and so on. In other words, the sequence $(w_1, \dots, w_k)$ must be lexicographically largest among the sequences for which the knight can reach city $n$ within at most $d$ days, obtaining, for each $1 \le j \le k$, a sword of type $j$ with value $w_j$.

Examples

Input 1

7 7 6 2
1 2 7 9
2 7 1 0
1 3 5 6
3 4 10 1
4 7 0 0
5 6 2 17
5 7 3 15

Output 1

10 15

Note

The best possible path is marked in the figure above with bold lines and arrows, according to the direction of the knight's travel along the road. Underlined bold edge labels indicate modifications made at that road.

The road from city 3 to city 4 allows obtaining the largest value for the first type of sword. It is not possible to reach city 7 within at most 6 days while passing through the road connecting cities 3 and 4 and the road connecting cities 5 and 6. Therefore, the knight will have to settle for a second-type sword with a value of 15, passing through the road between cities 5 and 7. His path will pass through the following cities: 1, 3, 4, 7, 5, 7. He will have one day left, which he will not use.

Sample Tests

Test 0 is the test from the example above. Additionally:

1. $n = 5, m = 4, d = 3, k = 4$. Every city is connected by a road to city 1. On each road, there is only one craftsman capable of modifying a sword to a value greater than 0.
2. $n = 100, m = 4950, d = 5, k = 8$. Every city is connected to every other city. Random sword values.
3. $n = 10\,000, m = 9999, d = n-1, k = 1$. City $i$ is connected to city $i+1$ ($1 \le i \le n-1$).

Subtasks