#P18778. [Kaist2021]Flowerbed Redecoration

[Kaist2021]Flowerbed Redecoration

Flowerbed Redecoration

题目描述

一个花坛是 nn 行 mm 列的网格,每格种有一朵花。花有 2626 种颜色,分别用大写字母 A 到 Z 表示。

为了重新布置花坛,你租来一台能够抬起并旋转 d×dd\times d 正方形区域的设备。施工按如下顺序进行:

  1. 最开始,设备覆盖前 dd 行、前 dd 列组成的正方形。
  2. 将设备覆盖的正方形顺时针旋转 90∘90^\circ。若它覆盖的是最后 dd 行、最后 dd 列组成的正方形,则施工结束。否则,若它尚未覆盖最后 dd 列,就把设备向右移动 xx 格;若它已经覆盖最后 dd 列,就把设备向下移动 yy 格,并移回最左侧,使其覆盖前 dd 列。
  3. 重复第 2 步,直到施工结束。

参数保证设备始终位于花坛内,并且能够恰好到达右下角的目标位置。移动设备本身不会移动花朵;只有旋转操作改变花朵的位置。

请输出施工结束后的花坛。

花坛示意图

输入格式

第一行五个整数 n,m,y,x,dn,m,y,x,d,注意竖直步长 yy 在水平步长 xx 前。

接下来 nn 行,每行一个长度为 mm 的大写字母串,表示初始花坛。

输出格式

输出 nn 行,每行一个长度为 mm 的大写字母串,表示最终花坛。

数据范围

  • 1≤nm≤1061\le nm\le10^6。
  • 1≤y≤n1\le y\le n,1≤x≤m1\le x\le m。
  • 1≤d≤min⁡(n,m)1\le d\le\min(n,m)。
  • n≡d(mody)n\equiv d\pmod y,m≡d(modx)m\equiv d\pmod x。

样例 1

输入

4 4 1 1 2
AAAA
BBBB
AAAA
BBBB

输出

BAAA
ABBB
BAAA
BBBA

样例 2

输入

6 5 1 2 3
RBRCY
YBPBR
PBRCY
CYPBR
PBRCY
CYPBR

输出

PYRBR
CRCBB
PPBPY
CRCYB
YRBCY
PYRBR

样例说明

第一个样例中,每次旋转后的花坛如下,绿色方框表示该次旋转的区域:

样例1的旋转过程