题目描述
小 R 是一个可爱的女孩子。有一天,她在被摸头时,突然灵光乍现,便随手加强了一道题给你做。
这道题的名字叫涂色游戏。初始时你有一个 $n$ 行 $m$ 列的网格,所有格子上都没有颜色。有 $k$ 种颜色的刷子,颜色编号为 $1\sim k$。然后给出 $q$ 次操作,每次操作给出 $op,l,r,c,t$ 五个参数:
- 如果 $op=1$,表示将第 $l\sim r$ 行的所有格子涂成颜色 $c$。
- 如果 $op=2$,表示将第 $l\sim r$ 列的所有格子涂成颜色 $c$。
- 如果 $t=0$,意味着如果涂色时遇到已经被染色的格子,就不再进行染色。
- 如果 $t=1$,意味着如果涂色时遇到已经被染色的格子,就用新的颜色覆盖它。
在所有涂色操作结束以后,对于每种颜色,求出有多少个格子被染成了这种颜色。
输入格式
第一行四个整数 $n,m,k,q$,表示行数、列数、颜色数和操作数。
接下来 $q$ 行,每行五个整数 $op,l,r,c,t$,表示这次操作的参数。
输出格式
一行 $k$ 个整数,第 $i$ 个整数表示被染成颜色 $i$ 的格子数量。
样例 #1
样例输入 #1
5 5 2 4
1 2 4 1 0
2 4 5 1 1
2 2 4 2 0
1 1 1 2 1
样例输出 #1
17 7
样例 #2
样例输入 #2
5 5 3 6
2 1 3 3 1
2 2 4 1 0
1 4 4 2 0
2 1 1 1 0
1 2 5 2 0
1 1 5 3 0
样例输出 #2
5 4 16
提示
样例 $1$ 解释
用浅灰色表示颜色 $1$,灰色表示颜色 $2$。
涂色过程如图所示:
共有 $17$ 个区域被染成颜色 $1$,$7$ 个区域被染成颜色 $2$。
数据范围
本题共 $20$ 个测试点,每个测试点 $5$ 分。
对于全部数据,保证 $1\le n,m,q\le 2\times 10^6$,$1\le k\le 5\times 10^5$,$op\in\{1,2\}$,若 $op=1$ 则 $1\le l\le r\le n$,若 $op=2$ 则 $1\le l\le r\le m$,$1\le c\le k$,$t\in\{0,1\}$。
- 对于测试点 $1\sim 3$:保证 $n,m,k,q\le 200$。
- 对于测试点 $4\sim 6$:保证 $n,m,k,q\le 2\times 10^3$。
- 对于测试点 $7\sim 9$:保证 $n,m,k,q\le 10^5$,$op=1$。
- 对于测试点 $10\sim 12$:保证 $n,m,k,q\le 10^5$,$t=1$。
- 对于测试点 $13\sim 18$:保证 $n,m,k,q\le 10^5$。
- 对于测试点 $19\sim 20$:无特殊限制。