#2558. 马赛克处理

马赛克处理

Description

对一些图片进行像素化处理(打马赛克),先把每一张图片都分成n×nn×n个单元格,每个单元格都有一个颜色值,然后选择一个单元格,检查以该单元格为中心的L×LL×L区域的颜色值。假设区域中的最大颜色值和最小颜色值分别为AABB,则用floor((A+B)/2)floor((A+B)/2)替换所选单元格的颜色值。

Format

Input

第1行包含一个整数TT5T(T≤5),表示测试用例的数量,每个测试用例都以整数nn为开头5<n<800(5<n<800);接下来的nn行,每行都有nn个整数表示原始颜色值,第ii行中的第j个整数是图片单元格(i,j)(i,j)的颜色值,颜色值是非负整数,不超过10910^9。之后有一个整数QQ105Q(Q≤10^5),表示打马赛克的数量。在QQ个操作中,第i行表示第i个处理位置xi,yi,Li1xi,yin1Li<104Lixi,yi,Li(1≤xi,yi≤n,1≤Li<10^4,Li是奇数),表示将根据上文所述的Li×Li区域修改(xi,yi)的颜色值。查询(2,3,3)(2,3,3)表示根据区域$(1,2)、(1,3)、(1,4)、(2,2)、(2,3)、(2,4)、(3,2)、(3,3)、(3,4)$更新第22行和第33列单元格的颜色值。注意:若区域不完全在图片中,则只考虑同时位于区域和图片中的单元格,并按照输入顺序逐个更新。

Output

对每个测试用例,都输出一行“CaseCase#tt:”(不带引号,tt表示测试用例的编号),对每种操作都输出已更新单元格的颜色值。

Samples

1
3
1 2 3
4 5 6
7 8 9
5
2 2 1
3 2 3
1 1 3
1 2 3
2 2 3
Case #1:
5
6
3
4
6