Background

You can take a look at this discussion: https://www.luogu.com.cn/discuss/703835.

Problem Description

Little R is a lovely girl. One day, while someone was patting her on the head, she suddenly got inspired, and casually made a problem harder for you to solve.

This problem is called the Coloring Game. Initially, you have an $n$-row $m$-column grid, and all cells are uncolored. There are $k$ brushes of different colors, with color IDs from $1$ to $k$. Then you are given $q$ operations. Each operation provides five parameters $op,l,r,c,t$:

• If $op=1$, it means coloring all cells in rows $l\sim r$ with color $c$.
• If $op=2$, it means coloring all cells in columns $l\sim r$ with color $c$.
• If $t=0$, it means that if you encounter a cell that is already colored during coloring, you stop coloring further.
• If $t=1$, it means that if you encounter a cell that is already colored during coloring, you overwrite it with the new color.

After all coloring operations are finished, for each color, compute how many cells are colored with that color.

Input Format

The first line contains four integers $n,m,k,q$, representing the number of rows, columns, colors, and operations.

The next $q$ lines each contain five integers $op,l,r,c,t$, representing the parameters of this operation.

Output Format

Output one line with $k$ integers. The $i$-th integer represents the number of cells colored with color $i$.

5 5 2 4
1 2 4 1 0
2 4 5 1 1
2 2 4 2 0
1 1 1 2 1

17 7

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

5 4 16

Hint

Sample $1$ Explanation

Use light gray to represent color $1$, and gray to represent color $2$.

The coloring process is shown in the figure:

There are $17$ cells colored with color $1$, and $7$ cells colored with color $2$.

Constraints

This problem has a total of $20$ test points, each worth $5$ points.

For all data, it is guaranteed that $1\le n,m,q\le 2\times 10^6$, $1\le k\le 5\times 10^5$, $op\in\{1,2\}$. If $op=1$, then $1\le l\le r\le n$; if $op=2$, then $1\le l\le r\le m$. Also, $1\le c\le k$, and $t\in\{0,1\}$.

• For test points $1\sim 3$: it is guaranteed that $n,m,k,q\le 200$.
• For test points $4\sim 6$: it is guaranteed that $n,m,k,q\le 2\times 10^3$.
• For test points $7\sim 9$: it is guaranteed that $n,m,k,q\le 10^5$, and $op=1$.
• For test points $10\sim 12$: it is guaranteed that $n,m,k,q\le 10^5$, and $t=1$.
• For test points $13\sim 18$: it is guaranteed that $n,m,k,q\le 10^5$.
• For test points $19\sim 20$: there are no special constraints.

Translated by ChatGPT 5