Gummy Candies

Time limit3sMemory limit1024 MB

Summary

Pick candies so every color appears equally often, and find the minimum cost for each total weight remainder modulo m.

Level: Medium7 of 10
Topics: Dynamic programming, Shortest path
Solved: No attempts yet

Problem

Bajtek loves gummy candies. A newly opened shop sells only gummy candies, and it offers n kinds. The i-th kind is described by its color k_i, its weight m_i in bytegrams, and its price c_i in bytegroshes. Candies are sold one at a time, and the shop has an unlimited supply of each kind. Colors are numbered from 1 to k.

Bajtek buys a multiset of candies only if every color from 1 to k appears exactly the same number of times in it. For each integer r in $[0, m-1]$ , find the minimum total price Bajtek must pay for a multiset whose total weight leaves remainder r when divided by m.

Input

The first line contains three integers n, k, and m ( $1 \le n, k, m \le 7000$ ). Each of the next n lines contains three integers k_i, m_i, and c_i ( $1 \le k_i \le k$ , $1 \le m_i \le m$ , $1 \le c_i \le 10^9$ ).

Output

Print m lines. The i-th line contains the minimum total price of a valid multiset whose total weight leaves remainder i-1 when divided by m. If no such multiset exists, print -1 instead.

Examples2

Example 1
Input
```
3 2 6
1 2 1
2 2 2
1 1 5
```
Expected output
```
0
10
6
7
3
13
```
Example 2
Input
```
2 3 3
1 1 1
3 1 1
```
Expected output
```
0
-1
-1
```