你有 $T$ 个线程正在向一个包含 $N$ 个位置的循环数据结构（每个位置存储一个整数）中写入数据，所有线程每秒写入 $1$ 个整数。每个线程 $i$ 从时间 $t_i$ 开始，从数据结构中的位置 $p_i$ 开始写入，并连续写入 $v_i$ 个整数 $a_i$。线程将按顺序写入每个位置（从 $p_i$ 开始，然后写入 $(p_i + 1)\%N$，$(p_i + 2)\%N$，依此类推）。如果到达索引 $N - 1$，由于数据结构是循环的，下一个索引将是 $0$。如果两个或多个线程在同一时间尝试向同一位置写入不同的整数，则会发生竞争条件（race condition），这意味着该位置的值是不确定的，因为根据哪个线程成功执行了写入操作，它可能是多个值之一。然而，如果所有线程在同一时间向同一位置写入相同的值 $v$，由于没有歧义，该位置的值将为 $v$。

例如，在第一个样例中，数据结构的最终结果是 $\{1, 0, 1, 1, 0\}$。尽管线程 2 和线程 3 在同一时间写入相同的位置，但这不会引起竞争条件，因为它们写入了相同的整数。另一方面，在第二个样例中，数据结构的最终结果是 $\{1, 0, ?, ?, 0\}$，其中 ? 表示不确定的字符，因为两个线程在同一时间向同一位置写入了不同的字符。

线程可以写入的值在区间 $[0, A)$ 内。在所有线程写入结束后，对于每个整数 $i \in [0, A)$，设其在数据结构中出现的次数为 $k_i$。已知在任何线程开始写入之前，数据结构中的每个位置都初始化为 $0$。请按顺序输出所有的 $k_i$，并在最后输出不确定字符的数量。

输入格式

输入的第一行包含三个空格分隔的整数 $T$（$1 \le T \le 50\,000$）、$N$（$1 \le N \le 10^9$）和 $A$（$1 \le A \le 100\,000$）。它们分别代表线程的数量、循环数据结构的大小以及线程可以写入数据结构的整数个数。

接下来的 $T$ 行，每行包含四个空格分隔的整数 $t_i$（$0 \le t_i \le 10^9$）、$p_i$（$0 \le p_i < N$）、$v_i$（$1 \le v_i \le 10^9$）和 $a_i$（$0 \le a_i < A$）。它们分别代表线程 $i$ 开始写入的时间、开始写入的位置、写入的值的数量以及写入每个位置的数值。每个线程每秒写入 $1$ 个整数。

输出格式

输出 $A + 1$ 个空格分隔的数字 $k_0\ k_1\ \dots\ k_{A-1}\ k_?$。其中 $k_i$ 代表在所有线程结束写入后，数字 $i$ 在数据结构中出现的次数（对于 $0 \le i < A$）。$k_?$ 代表在所有线程结束写入后，不确定字符在数据结构中出现的次数。

样例

输入样例 1

3 5 2
0 0 1 1
1 2 2 1
1 2 2 1

输出样例 1

2 3 0

输入样例 2

3 5 2
0 0 1 1
1 2 2 0
1 2 2 1

输出样例 2

2 1 2