#P17805. [Ontak2024]WOK

[Ontak2024]WOK

题目描述

给定一个 n×nn\times n 的方格矩阵,每格有一个非负整数颜色。

按顺序执行 qq 次操作。每次选择一个子正方形,将其中的格子整体逆时针旋转 90∘90^\circ,其他格子不变。

输出执行所有操作后的矩阵。

输入格式

第一行是该测试的子任务编号,官方样例使用 00。

第二行整数 nn。随后 nn 行,每行 nn 个整数 ci,jc_{i,j},描述初始矩阵。

下一行整数 qq。随后 qq 行,每行三个整数 wi,ki,biw_i,k_i,b_i:子正方形左上角位于第 wiw_i 行、第 kik_i 列,边长为 bib_i。行、列从 11 开始编号。

对于子正方形内从 00 开始的局部坐标,旧格子 (r,c)(r,c) 旋转后到达 (bi−1−c,r)(b_i-1-c,r)。

输出格式

输出 nn 行,每行 nn 个整数,表示最终颜色矩阵。

数据范围

  • 1≤n≤10001\le n\le1000,1≤q≤50001\le q\le5000。
  • 0≤ci,j≤n20\le c_{i,j}\le n^2。
  • 1≤wi,ki≤n1\le w_i,k_i\le n。
  • 1≤bi≤n−max⁡(wi,ki)+11\le b_i\le n-\max(w_i,k_i)+1,保证操作区域不越界。

样例 1

输入:

0
3
1 2 3
4 5 6
7 8 9
3
1 1 2
2 1 2
2 1 2

输出:

2 5 3
8 7 6
4 1 9

样例 2

输入:

0
4
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8
7
2 3 2
2 3 2
2 3 2
4 3 1
2 3 2
2 3 2
2 3 2

输出:

1 2 3 4
5 6 4 3
1 2 8 7
5 6 7 8

样例 3

输入:

0
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
6
1 1 3
3 2 2
3 2 2
3 2 2
1 3 2
1 3 2

输出:

0 1 0 1
1 0 1 0
0 0 1 1
1 1 0 0

子任务

编号 附加限制 分值
1 n≤50n\le50 7
2 n≤400n\le400,所有颜色不超过 11 14
3 n≤400n\le400 18
4 nn 和所有 bib_i 都是 22 的幂,且 wi−1,ki−1w_i-1,k_i-1 均为 bib_i 的倍数 16
5 所有被旋转子正方形的中心均与整个矩阵的中心重合 13
6 至多 nn 个格子的颜色为正数 11
7 无附加限制 21