Байтек обожает желейные конфеты. В недавно открывшемся магазине (который продает только желейные конфеты) можно купить $n$ их видов. $i$-й вид характеризуется цветом, массой в байтограммах и ценой в байтогрошах. Конфеты продаются поштучно. Цвета конфет обозначены числами от $1$ до $k$. В магазине доступно неограниченное количество конфет каждого вида.

Байтек, помимо конфет, любит эстетику цвета. Он позволит себе купить какой-либо мультимножество конфет только в том случае, если для каждого цвета от $1$ до $k$ он купит ровно одинаковое количество конфет.

Байтек также любит числа. Для каждого целого числа $r$ из интервала $[0, m - 1]$ он задается вопросом, какое минимальное количество байтогрошей ему придется потратить, чтобы купить мультимножество конфет, суммарная масса которых при делении на $m$ дает остаток $r$. Помогите ему и напишите программу, которая вычислит искомые значения!

Входные данные

В первой строке стандартного ввода находятся три целых числа $n, k$ и $m$ ($1 \le n, k, m \le 7\,000$), обозначающие количество видов конфет, количество цветов и значение $m$ соответственно.

В каждой из следующих $n$ строк находятся по три целых числа. Числа в $i$-й строке — это $k_i, m_i$ и $c_i$ ($1 \le k_i \le k; 1 \le m_i \le m; 1 \le c_i \le 10^9$) — соответственно цвет, масса в байтограммах и цена в байтогрошах конфет $i$-го вида.

Выходные данные

На выходе должно быть $m$ строк. В $i$-й строке должно находиться одно целое число — минимальная суммарная цена мультимножества конфет, которое может купить Байтек и в котором суммарная масса конфет в байтограммах при делении на $m$ дает остаток $i-1$. Если такое мультимножество не существует, в этой строке должно быть число $-1$.

Примеры

Пример 1

Входные данные:

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

Выходные данные:

0
10
6
7
3
13

Пример 2

Входные данные:

2 3 3
1 1 1
3 1 1

Выходные данные:

0
-1
-1

Примечание

В первом примере: Чтобы суммарная масса конфет была кратна $m = 6$, Байтек может не покупать ни одной конфеты — тогда он не потратит денег вовсе. Чтобы остаток от деления общей массы конфет на $6$ был равен $1$, Байтек должен купить одну конфету первого вида, две второго вида и одну третьего вида. Таким образом, он заплатит $10$ байтогрошей и получит по две конфеты каждого из двух цветов с суммарной массой, равной $7$ байтограммам. * Чтобы остаток от деления общей массы конфет на $6$ был равен $5$, Байтек должен купить две конфеты первого вида, три конфеты второго вида и одну конфету третьего вида.

Во втором примере конфеты второго цвета недоступны — единственным решением, удовлетворяющим Байтека, является отказ от покупки каких-либо конфет.