时空限制

1S/512M

题目描述

给定一个大小为 $n \times m$ 的字符矩阵，你需要依次执行 $Q$ 次操作。每次操作有两种类型：

• 操作类型 $1$：1 l r k

对第 $l$ 行到第 $r$ 行（包括两端）的每一行，进行如下处理：

将该行中的所有元素向右循环平移 $k$ 次。

一次向右循环平移指的是每一行中最右侧的字符会移到最左侧，其余字符依次向右平移。

• 操作类型 $2$：2 l r k

对第 $l$ 列到第 $r$ 列（包括两端）的每一列，进行如下处理：

将该列中的所有元素向下循环平移 $k$ 次。

一次向下循环平移指的是每一列中最下方的字符会移到最上方，其余字符依次向下平移。

请你在所有操作执行完成后，输出最终的字符矩阵。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，表示矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个大写字母，表示初始矩阵。

第 $n+2$ 行是一个整数 $Q$，表示操作次数。

接下来的 $Q$ 行，每行描述一次操作，格式如下：

• 1 l r k：表示对第 $l$ 行到第 $r$ 行右移 $k$ 次。

• 2 l r k：表示对第 $l$ 列到第 $r$ 列下移 $k$ 次。

输出格式

输出 $n$ 行，每行 $m$ 个字符，表示所有操作完成后的矩阵状态。

样例

样例输入 #1

4 4 
ABCD
EFGH
IJKL
MNOP
2 
1 2 3 2
2 1 3 5

样例输出 #1

MNOD
ABCF
GHEJ
KLIP

样例解释 #1

对于第一个操作，需要将第 $2$ 行和第 $3$ 行的元素向右循环移位 $2$ 次

• 第 $2$ 行：E F G H → G H E F
• 第 $3$ 行：I J K L → K L I J

更新后矩阵：

ABCD  
GHEF  
KLIJ  
MNOP

对于第二个操作，需要将前 $3$ 列的元素向下循环移位 $5$ 次。

• 第 1 列：A G K M → M A G K
• 第 2 列：B H L N → N B H L
• 第 3 列：C E I O → O C E I

更新后的矩阵为：

MNOD
ABCF
GHEJ
KLIP

数据规模

对于 $30\%$ 的数据，$k \leq \min(n,m)$。

对于 $100\%$ 的数据，$1 \leq n,m \leq 20$， $1 \leq Q \leq 100$，$k \leq 10^9$，且字符矩阵内仅包含大写字母。