通过超越时空流传下来的编码和解码方法，零散的记录开始呈现出新的形式。

虽然仍不完整，但 Brue 已经开始解读这座岛屿过去的场景。

很久以前，一束耀眼的光芒开始从岛屿的中心流淌。但这并非普通的光芒——它承载着秩序与平衡，是一种揭示世界原理的力量。

为了维持和谐，古人试图控制流光的颜色。他们相信，引导光的颜色就能引导世界走向和平。

见证光芒首次流淌那一天的记忆，并揭开它分裂为光与影的原因。

光线流经一个由 $N$ 行 $M$ 列组成的网格空间。光线从第一行开始，垂直向下直行流到第 $N$ 行。从上数第 $r$ 行、从左数第 $c$ 列的单元格记为 $(r, c)$。

每一列开头都有一束特定颜色的光，用介于 $1$ 和 $T$ 之间（含边界）的整数表示。第 $i$ 列的光初始颜色为 $A_i$，除非被改变，否则它会一直垂直向下流动，使该列中的每个单元格都填充相同的颜色。

为了平衡光流，古代工程师在网格中放置了 $K$ 个神器。每个神器跨越连续的一段列，并位于两个相邻行之间。神器会将其穿过的光线的颜色修改为一种新的特定颜色。

这些神器互不重叠，但它们的端点可以接触。每个神器都会将穿过它的任何光线的颜色改变为其指定的颜色。

你的任务是计算填充了 $T$ 种颜色中每种颜色的单元格总数。

输入格式

第一行包含四个由空格隔开的整数 $N$、$M$、$K$ 和 $T$，分别表示空间的大小、神器的数量以及颜色的数量。

第二行包含 $M$ 个由空格隔开的整数 $a_1, a_2, \dots, a_M$，表示每列光线的初始颜色。

接下来的 $K$ 行，每行包含四个由空格隔开的整数 $r_i, s_i, e_i, c_i$。这表示第 $i$ 个神器放置在第 $r_i - 1$ 行和第 $r_i$ 行之间的网格线上，并跨越从第 $s_i$ 列到第 $e_i$ 列（含边界）的所有列。该神器会将穿过它的光线颜色改变为颜色 $c_i$。

数据范围

• $2 \le N \le 10^9$
• $2 \le M \le 2 \times 10^5$
• $1 \le T \le 2 \times 10^5$
• $0 \le K \le 2 \times 10^5$
• $1 \le a_i \le T$ ($1 \le i \le M$)
• $2 \le r_i \le N$ ($1 \le i \le K$)
• $1 \le s_i \le e_i \le M$ ($1 \le i \le K$)
• $1 \le c_i \le T$ ($1 \le i \le K$)
• 如果 $i \ne j$ 且 $r_i = r_j$，则 $e_i < s_j$ 或 $e_j < s_i$ 成立。($1 \le i \le K, 1 \le j \le K$)
• 输入中的所有值均为整数。

输出格式

对于从 $1$ 到 $T$ 的每种颜色，按顺序在一行中输出填充了该颜色的单元格数量，用空格隔开。

子任务

• 子任务 1（3 分）：$K = 0$
• 子任务 2（8 分）：$K = 1$
• 子任务 3（19 分）：$N \le 100, M \le 100, K \le 100$
• 子任务 4（25 分）：$N \le 2000, M \le 2000, K \le 2000$
• 子任务 5（6 分）：$N \le 3000, M \le 3000$
• 子任务 6（39 分）：无附加限制。

样例

输入样例 1

9 5 5 4
1 2 3 2 4
3 1 3 3
6 4 5 2
6 2 3 4
4 3 4 1
8 3 3 1

输出样例 1

8 13 13 11

输入样例 2

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

输出样例 2

16 18 8