Bajtek adora las gominolas. En una tienda recién abierta (que solo vende gominolas) se pueden comprar hasta $n$ tipos de ellas; el $i$-ésimo tipo se describe por el color de la gominola, su peso en bajtogramos y su precio en bajtogroszy. Las gominolas se venden individualmente. Los colores de las gominolas se denotan con números del 1 al $k$. En la tienda hay una cantidad ilimitada de gominolas de cada tipo.

Además de las gominolas, a Bajtek le encanta la estética del color. Solo se permitirá comprar un multiconjunto de gominolas si, para cada color del 1 al $k$, compra exactamente la misma cantidad de gominolas.

Además de las gominolas y la estética del color, a Bajtek le encantan los números. Para cada número entero $r$ en el intervalo $[0, m - 1]$, se pregunta cuántos bajtogroszy tendría que gastar como mínimo para comprar un multiconjunto de gominolas en el que la suma de sus masas, al dividirla por $m$, dé como resto $r$. ¡Ayúdale y escribe un programa que calcule los valores buscados por él!

Entrada

La primera línea de la entrada estándar contiene tres números enteros $n, k$ y $m$ ($1 \le n, k, m \le 7\,000$), que representan, respectivamente, el número de tipos de gominolas a la venta, el número de colores de las gominolas y el valor $m$ descrito.

En cada una de las siguientes $n$ líneas hay tres números enteros. Los números en la $i$-ésima de estas líneas son, respectivamente, $k_i$, $m_i$ y $c_i$ ($1 \le k_i \le k$; $1 \le m_i \le m$; $1 \le c_i \le 10^9$) — el color, la masa en bajtogramos y el precio en bajtogroszy de las gominolas del $i$-ésimo tipo.

Salida

La salida debe contener $m$ líneas. La $i$-ésima línea debe contener un único número entero: el precio total mínimo del multiconjunto de gominolas que Bajtek puede comprar y en el cual la suma de las masas de las gominolas en bajtogramos, al dividirla por $m$, da como resto $i-1$. Si dicho multiconjunto no existe, en su lugar debe aparecer el número $-1$.

Ejemplos

Entrada 1

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

Salida 1

0
10
6
7
3
13

Entrada 2

2 3 3
1 1 1
3 1 1

Salida 2

0
-1
-1

Nota

En el primer caso de prueba:

• Para que la masa total de las gominolas sea divisible por $m = 6$, Bajtek puede no comprar ninguna gominola; en ese caso, no gasta dinero en absoluto.
• Para que el resto de la división de la masa total de las gominolas por 6 sea 1, Bajtek debería comprar una gominola del primer tipo, dos del segundo tipo y una del tercer tipo. De esta manera, pagará 10 bajtogroszy y obtendrá dos gominolas de cada uno de los dos colores, con una masa total igual a 7 bajtogramos.
• Para que el resto de la división de la masa total de las gominolas por 6 sea 5, Bajtek debería comprar dos gominolas del primer tipo, tres del segundo tipo y una del tercer tipo.

En el segundo caso de prueba, no hay gominolas disponibles del segundo color; la única solución que satisface a Bajtek es no comprar ninguna gominola.