Bajtek loves jelly beans. In a newly opened store (which sells only jelly beans), there are $n$ types of jelly beans available. The $i$-th type is described by its color, its weight in bajtograms, and its price in bajtogrosze. Jelly beans are sold individually. The colors of the jelly beans are denoted by numbers from $1$ to $k$. There is an unlimited supply of each type of jelly bean in the store.

Besides jelly beans, Bajtek loves color aesthetics. He will only allow himself to buy a multiset of jelly beans if he buys exactly the same number of jelly beans for every color from $1$ to $k$.

In addition to jelly beans and color aesthetics, Bajtek loves numbers. For every integer $r$ in the range $[0, m - 1]$, he wonders what is the minimum number of bajtogrosze he would have to spend to buy a multiset of jelly beans in which the total weight, when divided by $m$, gives a remainder of $r$. Help him and write a program that calculates these values for him!

Input

The first line of standard input contains three integers $n, k, m$ ($1 \le n, k, m \le 7\,000$), representing the number of types of jelly beans sold, the number of colors, and the value $m$, respectively.

Each of the next $n$ lines contains three integers. The numbers in the $i$-th line are $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$) — the color, the weight in bajtograms, and the price in bajtogrosze of the $i$-th type of jelly bean, respectively.

Output

The output should contain $m$ lines. The $i$-th line should contain a single integer — the minimum total price of a multiset of jelly beans that Bajtek can buy, such that the total weight of the jelly beans in bajtograms, when divided by $m$, gives a remainder of $i-1$. If no such multiset exists, the line should contain $-1$ instead.

Examples

Input 1

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

Output 1

0
10
6
7
3
13

Input 2

2 3 3
1 1 1
3 1 1

Output 2

0
-1
-1

Note

In the first example test: To make the total weight of the jelly beans divisible by $m = 6$, Bajtek can buy no jelly beans at all — he spends no money. For the remainder of the total weight divided by $6$ to be $1$, Bajtek should buy one jelly bean of the first type, two of the second type, and one of the third type. This way, he pays $10$ bajtogrosze and receives two jelly beans of each of the two colors, with a total weight of $7$ bajtograms. * For the remainder of the total weight divided by $6$ to be $5$, Bajtek should buy two jelly beans of the first type, three of the second type, and one of the third type.

In the second example test, no jelly beans of the second color are available — the only solution that satisfies Bajtek is to buy no jelly beans.