Bajtek adore les bonbons gélifiés. Dans un magasin nouvellement ouvert (qui ne vend que des bonbons gélifiés), il est possible d'en acheter $n$ types différents. Le $i$-ième type est décrit par la couleur du bonbon, son poids en bajtogrammes et son prix en bajtogroszy. Les bonbons sont vendus à l'unité. Les couleurs des bonbons sont notées par des nombres de $1$ à $k$. Le magasin dispose d'un nombre illimité de bonbons de chaque type.

En plus des bonbons, Bajtek adore l'esthétique des couleurs. Il ne s'autorisera à acheter un multiensemble de bonbons que si, pour chaque couleur de $1$ à $k$, il achète exactement le même nombre de bonbons.

Outre les bonbons et l'esthétique des couleurs, Bajtek adore les nombres. Pour chaque entier $r$ dans l'intervalle $[0, m - 1]$, il se demande quel est le montant minimal de bajtogroszy qu'il devrait dépenser pour acheter un multiensemble de bonbons dont la masse totale, divisée par $m$, donne un reste égal à $r$. Aidez-le et écrivez un programme qui calcule les valeurs recherchées pour lui !

Entrée

La première ligne de l'entrée standard contient trois entiers $n$, $k$ et $m$ ($1 \le n, k, m \le 7\,000$), représentant respectivement le nombre de types de bonbons vendus, le nombre de couleurs de bonbons et la valeur $m$ décrite.

Chacune des $n$ lignes suivantes contient trois entiers. Les nombres dans la $i$-ième ligne sont respectivement $k_i$, $m_i$ et $c_i$ ($1 \le k_i \le k$; $1 \le m_i \le m$; $1 \le c_i \le 10^9$) — représentant respectivement la couleur, la masse en bajtogrammes et le prix en bajtogroszy du bonbon de $i$-ième type.

Sortie

La sortie doit contenir $m$ lignes. La $i$-ième ligne doit contenir un seul entier — le prix total minimal du multiensemble de bonbons que Bajtek peut acheter et dont la masse totale des bonbons en bajtogrammes, divisée par $m$, donne un reste égal à $i-1$. Si un tel multiensemble n'existe pas, la ligne doit contenir le nombre $-1$.

Exemples

Entrée 1

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

Sortie 1

0
10
6
7
3
13

Entrée 2

2 3 3
1 1 1
3 1 1

Sortie 2

0
-1
-1

Remarque

Dans le premier exemple : Pour que la masse totale des bonbons soit divisible par $m = 6$, Bajtek peut ne pas acheter de bonbons — il ne dépense alors rien du tout. Pour que le reste de la division de la masse totale des bonbons par 6 soit égal à 1, Bajtek devrait acheter un bonbon du premier type, deux du deuxième type et un du troisième type. De cette façon, il paiera 10 bajtogroszy et obtiendra deux bonbons de chacune des deux couleurs, pour une masse totale de 7 bajtogrammes. * Pour que le reste de la division de la masse totale des bonbons par 6 soit égal à 5, Bajtek devrait acheter deux bonbons du premier type, trois du deuxième type et un bonbon du troisième type.

Dans le deuxième exemple, aucun bonbon de la deuxième couleur n'est disponible — la seule solution satisfaisant Bajtek est de ne pas acheter de bonbons.