Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

Language:
Cross Counting
 Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 1533 Accepted: 440

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 ≤ iN, 1 ≤ jM, 1 ≤ k, cC)

Output

Output the answer to each query.

Sample Input

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

Sample Output

0
2
0
1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator