Description

Given a N × M grid with different colors on each cell, your task is to calculate the total amount of crosses of a specific color. We say there exists a cross of size k centered at the cell (x,y) iff all cells lying in the x-th row or the y-th column and within a distance of k from (x,y) share the same color. Note that if two crosses have the same center but different sizes we consider they are distinct. Unfortunately, the color of each cell may varies by time and you have to respond to all the queries.

Input

There are four integers, N, M, C, Q, in the first line. (1 ≤ N, M, C ≤ 100, 1 ≤ Q ≤ 10000)
The next N lines each contains M integers between 1 and C which describe the color of cells.
The following Q lines each has either the form "C i j k" indicating to change the color of cell (i, j) into k, or the form "Q c" indicating to query the total amount of crosses of color c. (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ k, c ≤ C)

Output

Output the answer to each query.

5 5 3 6
1 3 2 3 1
3 3 2 3 3
2 2 2 2 2
3 3 2 3 3
1 3 2 3 1
Q 1
Q 2
Q 3
C 2 3 3
C 3 2 3
Q 3

0
2
0
1

Source

POJ Monthly--2007.11.25, Yang Yi