问题描述

假设你有一个城市的光照强度地图，表示为一个二维矩阵，矩阵中的每个元素代表对应区域的光照强度。由于城市的建筑规划和天气变化，某些区域的光照强度会发生变化。

你的任务是处理一系列查询，每次查询给出一个矩形区域，你需要计算并返回该区域内的总光照强度。

输入

第一行包含两个整数 n 和 m，分别表示光照地图的行数和列数。 接下来 n 行，每行包含 m 个整数，表示光照地图的初始状态。 然后是一个整数 q，表示查询和更新次数的总和。 接下来 q 行，每行的格式如下： 如果是查询：输入字符串 "QUERY"，后跟四个整数 x1, y1, x2, y2，表示查询的矩形区域的左上角和右下角坐标。 如果是更新：输入字符串 "UPDATE"，后跟三个整数 x, y, val，表示将坐标 (x, y) 的光照强度更新为 val。

输出

对于每个 "QUERY" 操作，输出一个整数，表示查询区域内的总光照强度。

样例

3 3
1 2 3
4 5 6
7 8 9
5
QUERY 1 1 2 2
UPDATE 2 2 10
QUERY 2 2 3 3
UPDATE 3 3 5
QUERY 1 1 3 3

12
33
46

Limitation

1 ≤ n, m ≤ 1000 -1000 ≤ 光照强度 ≤ 1000 1 ≤ q ≤ 1000 0 ≤ x1 ≤ x2 < n 0 ≤ y1 ≤ y2 < m 查询和更新操作交替出现