Bajtek 熱愛軟糖。在一家新開的商店（只販售軟糖）中，總共有 $n$ 種軟糖可供購買。第 $i$ 種軟糖由其顏色、重量（以 bajtogram 為單位）以及價格（以 bajtogrosz 為單位）來描述。軟糖是單個販售的。軟糖的顏色以 $1$ 到 $k$ 的數字表示。商店中每種軟糖的數量都是無限的。

除了軟糖之外，Bajtek 還熱愛色彩美學。他只有在為每一種顏色（從 $1$ 到 $k$）都購買了相同數量的軟糖時，才會購買該軟體多重集（multiset）。

除了軟糖和色彩美學，Bajtek 還熱愛數字。對於區間 $[0, m - 1]$ 中的每個整數 $r$，他想知道：若要購買一個軟糖多重集，使得其總重量除以 $m$ 的餘數為 $r$，他最少需要花費多少 bajtogrosz？請幫助他編寫一個程式來計算這些數值。

輸入格式

第一行包含三個整數 $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$ 種軟糖的顏色、重量（以 bajtogram 為單位）以及價格（以 bajtogrosz 為單位）。

輸出格式

輸出應包含 $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$，Bajtek 應該購買一個第一種軟糖、兩個第二種軟糖和一個第三種軟糖。這樣他將支付 $10$ bajtogrosz，並獲得兩種顏色各兩個軟糖，總重量為 $7$ bajtogram。
• 為了使軟糖總重量除以 $6$ 的餘數為 $5$，Bajtek 應該購買兩個第一種軟糖、三個第二種軟糖和一個第三種軟糖。

在第二個範例測試中，沒有任何第二種顏色的軟糖可供購買——唯一能讓 Bajtek 滿意的方案就是不購買任何軟糖。