Equal Color Bean Purchase Optimization

The problem is as follows:

You are given n types of jelly beans. Each bean type i has a color k_i (an integer between 1 and k), a weight m_i, and a cost c_i. You must purchase some jelly beans so that:

• You have at least one bean of every color from 1 to k.
• The number of beans purchased for every color is the same.

Let this common number be x (with x ≥ 1). Then you end up buying k*x beans in total. The total weight of the purchased beans is the sum of the individual weights, and the total cost is the sum of the costs.

For a given positive integer m, for every remainder r in the range \( [0, m-1] \), you are to determine the minimum total cost of a purchase plan such that the total weight modulo \( m \) is equal to \( r \). If no valid purchase plan exists that produces a remainder \( r \), output \(-1\) for that remainder.

All formulas are given in \( \LaTeX \) format. For example, the condition on the remainder is formulated as: if the total weight is \( W \), then we want \[ W \equiv r \pmod{m}, \] for each \( r \in \{0, 1, \ldots, m-1\} \).

Note: You have an unlimited supply of each bean type. However, you can only choose beans among the given n types. The purchase plan must satisfy that for every color between 1 and k you buy exactly the same number of beans.

This problem is translated from [PA 2024 Runda 3 Żelki](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/), thanks to Macaronlin for the translation.

inputFormat

The input begins with three integers n, k and m on a single line, where:

• n is the number of jelly bean types,
• k is the total number of colors, and
• m is the modulus used for the weight remainder.

Then follow n lines. The i-th of these lines contains three integers: k_i (the color of the bean), m_i (the weight of the bean) and c_i (the cost of the bean).

You have an unlimited supply of each bean type.

outputFormat

Output a single line containing m space‐separated integers. For each remainder \( r \) in \( [0, m-1] \), print the minimum total cost among all valid purchase plans whose total weight is congruent to \( r \) modulo \( m \). If no valid plan exists for some remainder, output \(-1\) for that remainder.

sample

2 2 5
1 2 3
2 3 4

7 -1 -1 -1 -1