Bajtek rất thích kẹo dẻo. Trong một cửa hàng mới mở (chỉ bán kẹo dẻo), có $n$ loại kẹo dẻo được bày bán. Loại kẹo thứ $i$ được mô tả bởi màu sắc, khối lượng (tính bằng bajtogram) và giá tiền (tính bằng bajtogrosz). Kẹo dẻo được bán lẻ từng viên. Các màu sắc của kẹo được đánh số từ $1$ đến $k$. Cửa hàng có số lượng không giới hạn cho mỗi loại kẹo.

Ngoài kẹo dẻo, Bajtek còn rất chú trọng đến tính thẩm mỹ về màu sắc. Anh chỉ mua một đa tập hợp (multiset) kẹo dẻo nếu và chỉ nếu với mỗi màu từ $1$ đến $k$, anh mua số lượng kẹo của màu đó là như nhau.

Bên cạnh kẹo dẻo và tính thẩm mỹ, Bajtek còn rất yêu thích các con số. Với mỗi số nguyên $r$ trong khoảng $[0, m - 1]$, anh tự hỏi mình cần chi ít nhất bao nhiêu bajtogrosz để mua một đa tập hợp kẹo dẻo sao cho tổng khối lượng của chúng chia cho $m$ có số dư là $r$. Hãy giúp anh ấy viết một chương trình tính toán các giá trị này!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào tiêu chuẩn chứa ba số nguyên $n, k$ và $m$ ($1 \le n, k, m \le 7\,000$), lần lượt là số loại kẹo dẻo, số lượng màu sắc và giá trị $m$ đã nêu.

Trong mỗi dòng tiếp theo trong số $n$ dòng, chứa ba số nguyên. Các số trong dòng thứ $i$ lần lượt là $k_i, m_i$ và $c_i$ ($1 \le k_i \le k; 1 \le m_i \le m; 1 \le c_i \le 10^9$) – tương ứng là màu sắc, khối lượng (bajtogram) và giá tiền (bajtogrosz) của loại kẹo thứ $i$.

Dữ liệu ra

Dữ liệu ra cần in ra $m$ dòng. Dòng thứ $i$ chứa một số nguyên duy nhất – tổng giá tiền tối thiểu của đa tập hợp kẹo dẻo mà Bajtek có thể mua sao cho tổng khối lượng của chúng chia cho $m$ có số dư là $i-1$. Nếu không tồn tại đa tập hợp như vậy, hãy in ra $-1$ trên dòng đó.

Ví dụ

Ví dụ 1

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

0
10
6
7
3
13

Ví dụ 2

2 3 3
1 1 1
3 1 1

0
-1
-1

Ghi chú

Giải thích ví dụ: Trong ví dụ đầu tiên: Để tổng khối lượng kẹo chia hết cho $m = 6$, Bajtek có thể không mua viên kẹo nào – khi đó anh không tốn chi phí nào cả. Để số dư của tổng khối lượng kẹo khi chia cho $6$ bằng $1$, Bajtek nên mua một viên kẹo loại thứ nhất, hai viên loại thứ hai và một viên loại thứ ba. Bằng cách này, anh sẽ trả $10$ bajtogrosz và nhận được hai viên kẹo cho mỗi màu, với tổng khối lượng là $7$ bajtogram. * Để số dư của tổng khối lượng kẹo khi chia cho $6$ bằng $5$, Bajtek nên mua hai viên kẹo loại thứ nhất, ba viên loại thứ hai và một viên loại thứ ba.

Trong ví dụ thứ hai, không có loại kẹo nào thuộc màu thứ hai – giải pháp duy nhất làm Bajtek hài lòng là không mua bất kỳ viên kẹo nào.