Problem Description

Translated from PA 2024 Round 3 Żelki, thanks to Macaronlin for the translation

There are $n$ types of candy beans, with $k$ colors. The $i$-th type of candy bean has color $k_i$, weight $m_i$, and price $c_i$. The goal is to purchase candy beans that include all $k$ colors, with each color being purchased in equal quantities.

For each integer $r$ in the interval $[0, m-1]$, find the minimum cost of a purchase plan where the total weight of the purchased candy beans modulo $m$ equals $r$. If no such purchase plan exists, output $-1$.

Input Format

The first line contains three integers $n, k$, and $m$ $(1 \le n, k, m \le 7,000)$, representing the number of candy bean types, the number of colors, and a parameter, respectively.

The following $n$ lines each contain 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)$, representing the color, weight, and price of the $i$-th type of candy bean, respectively.

Output Format

Output $m$ lines. The $i$-th line should indicate the minimum cost for a purchase where the total weight of the candy beans modulo $m$ equals $i-1$. If no such purchase is possible, output $-1$.

Sample Input and Output

Sample Input #1

3 2 6
1 2 1
2 2 2
1 1 5

Sample Output #1

0
10
6
7
3
13

Sample Input #2

2 3 3
1 1 1
3 1 1

Sample Output #2

0
-1
-1

Notes

In the first sample:

• To make the total weight of the candy beans divisible by $m = 6$, you can choose not to buy any candy beans, thus spending nothing.
• To make the total weight of the candy beans modulo $6$ equal to $1$, you should buy one of the first type, two of the second type, and one of the third type. This costs $10$ and results in two candies of each color, with a total weight of $7$.
• To make the total weight of the candy beans modulo $6$ equal to $5$, you should buy two of the first type, three of the second type, and one of the third type.

In the second sample, there are no candy beans of the second color, so the only feasible plan is not to buy any candy beans.

见题面 Input 部分

见题面 Output 部分