1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import sys
from collections import Counter


n, k, m = list(map(int, sys.stdin.readline().split()))
M = { x: [] for x in range(1, k+1) }

for _ in range(n):
    ki, *mici = list(map(int, sys.stdin.readline().split()))
    M[ki].append(mici)


def map_add_or_update(map, k, v: int):
    k %= m
    if k in map:
        if map[k] > v:
            map[k] = v
            return True
    else:
        map[k] = v
        return True
    return False


def prep1() -> dict[int, int]:
    prev = {0: 0}
    for x in range(1, k+1):
        if not M[x]:
            return None
        new = {}
        for pm, pc in prev.items():
            # print('pm, pc', pm, pc)
            for lm, lc in M[x]:
                map_add_or_update(new, pm + lm, pc + lc)
        # print('new', new)
        prev = new
    return prev


by1 = prep1()
# print('by1', by1)
if not by1:
    print(0)

    for x in range(1, k):
        print(-1)
    exit(0)

z = by1.copy()

B = [-1] * m
for pm, pc in z.items():
    B[pm] = pc

for x in range(1, k+1):
    nz = {}
    anyChange = False
    for pm, pc in z.items():
        for lm, lc in by1.items():
            # print(pm, pc)
            nm = (pm + lm) % m
            nc = pc + lc
            map_add_or_update(nz, nm, nc)
            if B[nm] == -1 or B[nm] > nc:
                B[nm] = nc
                anyChange = True

    if not anyChange:
        break

    z = nz

# print(z)

print(0)
for x in range(1, m):
    print(B[x])