Colorful Grid Painting

You are given a grid with \(n\) rows and \(m\) columns; initially, all cells are blank.

You will perform \(q\) painting operations. In each operation, you choose either a row or a column. All cells in that row or column get one additional layer of color. Immediately after each operation, every cell that has exactly \(k\) layers of color will have its color removed (i.e. it becomes blank).

After all operations have been performed, determine how many cells remain colored (i.e. have a number of layers not equal to 0). Note that the painting process is sequential and when a cell reaches exactly \(k\) layers, its color is reset to blank. In effect, the final number of layers on a cell is \((r_i + c_j) \bmod k\), where \(r_i\) is the number of operations on row \(i\) and \(c_j\) is the number of operations on column \(j\).

Input Format: The first line contains four integers \(n, m, q, k\). The next \(q\) lines each contain an operation in the format R x or C y indicating a painting operation on row \(x\) or column \(y\) respectively. Rows and columns are 1-indexed.

Output Format: Output a single integer representing the number of colored cells after all operations.

inputFormat

The first line contains four space-separated integers \(n, m, q, k\), where \(n\) and \(m\) denote the number of rows and columns, \(q\) denotes the number of operations, and \(k\) is the color removal threshold.

Then \(q\) lines follow, each containing an operation. An operation is given as a letter and an integer separated by a space. The letter is either R or C, indicating a row or column operation respectively, and the integer denotes the index (1-indexed) of the row or column to be painted.

outputFormat

Output a single integer: the number of cells that remain colored after performing all the operations.

sample

3 3 4 2
R 1
C 2
R 2
C 2

6