Description

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

Format

Input

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

Output

对每个测试用例，都输出一行“$Case$#$t$:”（不带引号，$t$表示测试用例的编号），对每种操作都输出已更新单元格的颜色值。

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