Bajtek 非常喜欢软糖。在一家新开的商店（只卖软糖）里，可以买到 $n$ 种软糖。第 $i$ 种软糖由其颜色、重量（单位：bajtogram）和价格（单位：bajtogrosz）描述。软糖是单个出售的。软糖的颜色用 $1$ 到 $k$ 的数字表示。商店里每种软糖的数量都是无限的。

除了软糖，Bajtek 还非常讲究色彩美学。他只会在购买的软糖多重集满足以下条件时才购买：对于 $1$ 到 $k$ 的每种颜色，他购买的该颜色软糖数量必须完全相同。

除了软糖和色彩美学，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

说明 1

在第一个样例中： 为了使总重量除以 $m = 6$ 的余数为 $0$，Bajtek 可以不买任何软糖——此时他不需要花费任何钱。 为了使总重量除以 $6$ 的余数为 $1$，Bajtek 应该购买一个第一种软糖、两个第二种软糖和一个第三种软糖。这样他将花费 $10$ bajtogrosz，并获得两种颜色各两个软糖，总重量为 $7$ bajtogram。 * 为了使总重量除以 $6$ 的余数为 $5$，Bajtek 应该购买两个第一种软糖、三个第二种软糖和一个第三种软糖。

在第二个样例中，没有第二种颜色的软糖可供购买——满足 Bajtek 要求的唯一方案是不购买任何软糖。