Colouring Game

Little R is a cute girl who came up with this interesting problem while being petted on the head. You are given an (n \times m) grid initially uncolored, and you have (k) brushes, each with a unique color labeled from 1 to (k). You will be given (q) operations. Each operation consists of five parameters: (op, l, r, c, t).

There are two types of operations:

• If \(op = 1\), paint all cells in rows \(l \sim r\) with color \(c\).
• If \(op = 2\), paint all cells in columns \(l \sim r\) with color \(c\).

The parameter \(t\) determines the painting mode:

• If \(t = 0\), then if a cell is already colored, do not repaint it.
• If \(t = 1\), then if a cell is already colored, overwrite it with the new color \(c\).

After all operations, for each color \(i\) from 1 to \(k\), report how many cells are painted with color \(i\).

inputFormat

The input consists of multiple lines. The first line contains four integers (n), (m), (k) and (q) representing the number of rows, columns, colors and operations respectively. Each of the following (q) lines contains five integers (op), (l), (r), (c) and (t) that describe an operation as stated in the problem description.

outputFormat

Output (k) integers separated by spaces. The (i^{th}) integer represents the number of cells painted with color (i) after performing all operations.

sample

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

2 6