Bajtek은 젤리를 매우 좋아합니다. 새로 문을 연 젤리 가게에서는 $n$ 종류의 젤리를 판매하며, 각 종류는 젤리의 색상, 무게(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은 아무 젤리도 사지 않을 수 있으며, 이때 비용은 $0$입니다. 총 무게를 $6$으로 나눈 나머지가 $1$이 되기 위해, Bajtek은 첫 번째 종류 젤리 1개, 두 번째 종류 젤리 2개, 세 번째 종류 젤리 1개를 구매해야 합니다. 이렇게 하면 10 bajtogrosz를 지불하게 되며, 두 가지 색상의 젤리를 각각 2개씩 얻게 되고 총 무게는 7 bajtogram이 됩니다. * 총 무게를 $6$으로 나눈 나머지가 $5$가 되기 위해, Bajtek은 첫 번째 종류 젤리 2개, 두 번째 종류 젤리 3개, 세 번째 종류 젤리 1개를 구매해야 합니다.

두 번째 예제에서는 두 번째 색상의 젤리를 구할 수 없으므로, Bajtek이 만족할 수 있는 유일한 방법은 젤리를 전혀 구매하지 않는 것입니다.