Fluffalo States

You are given several types of mythical creatures called Fluffalos. Each Fluffalo starts in state \(0\) and can transition to other states according to a set of rules. Each rule is represented as a tuple \((f, s, t, s')\), where:

• \(f\) (an integer) is the identifier of the Fluffalo type (ranging from \(1\) to \(n\)).
• \(s\) is the current state.
• \(t\) is the herb cost required to transition.
• \(s'\) is the new state after the transition.

Starting from state \(0\) with a herb count of \(0\), a Fluffalo may apply a transition rule if the total herb cost does not exceed a given maximum \(k\); that is, if \(\text{currentHerb} + t \le k\). Note that each Fluffalo counts its initial state \(0\). Your task is to determine, for each Fluffalo type, the number of distinct states (including state \(0\)) that are reachable by applying one or more transitions.

Note: A state is counted only once even if it can be reached through different sequences of transitions.

inputFormat

The input is given from stdin and has the following format:

p n k
f1 s1 t1 s'1
f2 s2 t2 s'2
...

Where:

• \(p\): the number of transition rules.
• \(n\): the number of Fluffalo types.
• \(k\): the maximum herb cost allowed.
• Each of the next \(p\) lines contains four integers representing a transition rule: the Fluffalo type \(f\) (1-indexed), the current state \(s\), the herb cost \(t\), and the new state \(s'\).

outputFormat

Output to stdout a single line with \(n\) integers separated by spaces. The \(i\)th integer represents the number of distinct states that the \(i\)th Fluffalo can reach (including the initial state \(0\)).

## sample

6 3 2
1 0 1 1
1 1 1 2
2 0 1 1
2 1 1 2
2 2 1 2
3 0 1 0

3 3 1