题目描述

给定一个 N × M 的网格，每个格子有不同的颜色。你的任务是计算特定颜色的十字架的总数。我们称以格子 (x, y) 为中心、大小为 k 的十字架存在，当且仅当：

• 所有位于第 x 行或第 y 列，且与 (x, y) 的距离不超过 k 的格子颜色相同。
  注意，如果两个十字架中心相同但大小不同，我们认为是不同的十字架。
  此外，每个格子的颜色可能会随时间变化，你需要处理所有的查询。

输入格式

第一行包含四个整数 N, M, C, Q。（1 ≤ N, M, C ≤ 100，1 ≤ Q ≤ 10000）
接下来 N 行，每行包含 M 个 1 到 C 之间的整数，表示网格中格子的颜色。
接下来的 Q 行，每行格式为：

• "C i j k"：表示将格子 (i, j) 的颜色改为 k。
• "Q c"：表示查询颜色为 c 的十字架的总数。

输出格式

对每个查询输出对应的答案。

示例输入

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

来源

POJ Monthly--2007.11.25, Yang Yi