Bajtekはグミが大好きです。新しくオープンしたグミ専門店では、$n$ 種類のグミが販売されており、$i$ 番目の種類はグミの色、重さ（バイトグラム単位）、価格（バイトグロシュ単位）によって定義されています。グミは1個ずつ販売されています。グミの色は $1$ から $k$ までの番号で表されます。店には各種類のグミが無限に用意されています。

Bajtekはグミだけでなく、色の美学も大切にしています。彼は、$1$ から $k$ までのすべての色について、購入するグミの個数が完全に一致する場合にのみ、グミの多重集合を購入することにします。

Bajtekはグミと色の美学に加えて、数字も大好きです。彼は、$0$ から $m - 1$ までのすべての整数 $r$ について、購入したグミの合計重量を $m$ で割った余りが $r$ となるようなグミの多重集合を購入するために必要な最小の費用（バイトグロシュ単位）がいくらになるかを知りたがっています。彼のために、これらの値を計算するプログラムを作成してください。

入力

標準入力の最初の行には、3つの整数 $n, k, m$ ($1 \le n, k, m \le 7\,000$) が含まれており、それぞれ販売されているグミの種類数、グミの色の数、および値 $m$ を表します。

続く $n$ 行の各行には、3つの整数が含まれています。$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$ 行目には、Bajtekが購入可能なグミの多重集合のうち、合計重量を $m$ で割った余りが $i-1$ となるような最小の合計価格を整数で出力してください。そのような多重集合が存在しない場合は、その行に $-1$ を出力してください。

入出力例

入力 1

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

出力 1

0
10
6
7
3
13

入力 2

2 3 3
1 1 1
3 1 1

出力 2

0
-1
-1

注記

最初の例の解説： グミの合計重量を $m = 6$ で割った余りが $0$ になるようにするには、Bajtekはグミを一つも買わないという選択肢があり、その場合費用は一切かかりません。 グミの合計重量を $6$ で割った余りが $1$ になるようにするには、1番目の種類のグミを1個、2番目の種類のグミを2個、3番目の種類のグミを1個購入する必要があります。これにより、彼は10バイトグロシュを支払い、2つの色のそれぞれについて2個ずつ、合計重量が7バイトグラムのグミを手に入れることができます。 * グミの合計重量を $6$ で割った余りが $5$ になるようにするには、1番目の種類のグミを2個、2番目の種類のグミを3個、3番目の種類のグミを1個購入する必要があります。

2番目の例では、2番目の色のグミが手に入らないため、Bajtekが満足できる唯一の解決策はグミを一つも買わないことです。