L. My Hero Photographia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

My Hero Academia (you) has taken a break from saving my grades and has now decided to help me with my burgeoning photography hobby. I have taken an image with my camera, but there are a few problems with it. Please help me fix it.

Specifically, I will provide you with my image, represented as a matrix of $$$n \times m$$$ integers. The edges of the matrix "loop around", meaning that the left-most column is considered adjacent to the right-most column, and the top-most row is considered adjacent to the bottom-most row. To fully process the image, we will apply $$$k$$$ transformations sequentially on the image. These transformations will be of the following form (where +x is to the right, +y is up):

  • Blur: Given a pixel $$$(i, j)$$$ in the image, replace its value with the average (rounded down to the nearest integer) of its $$$3\times 3$$$ neighboring pixels in the input image (from the original unblurred image), with the edge pixels wrapping around to the opposite side of the image.
  • Shift x y: Shift each pixel by $$$x$$$ units horizontally in the +x (right) direction and $$$y$$$ units vertically in the +y direction (up), with the edge pixels wrapping around to the opposite side of the image.
  • Sharpen: Given a pixel $$$(i, j)$$$ in the image, if its value is larger than all of its $$$3\times 3$$$ neighboring pixels in the input image (excluding itself, of course), add $$$100$$$ to its value. If its value is less than the minimum value among its $$$3\times 3$$$ neighboring pixels (excluding itself, of course), subtract $$$100$$$ from its value. Again, the edge pixels should wrap around the opposite side of the image when determining neighbors.
  • Rotate CW: Rotate the image 90 degrees clockwise.
  • Rotate CCW: Rotate the image 90 degrees counter-clockwise.
  • Flip Horizontal: Flip the image across the y-axis.
  • Flip Vertical: Flip the image across the x-axis.

Given the image and a list of $$$k$$$ operations, please be My Hero Photographia and provide me with the final image.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ $$$(3 \leq n, m \leq 100)$$$, the dimensions of the image. The following $$$n$$$ lines contain $$$m$$$ integers each (between $$$0$$$ and $$$100$$$ inclusive), representing the image.

The next line of input contains a single integer $$$k$$$ $$$(1 \leq k \leq 1000)$$$, the number of operations to be performed on the image. The following $$$k$$$ lines each contain a single operation to be performed on the image. Each operation is one of the following:

  • Blur
  • Shift x y ($$$-100 \leq x, y \leq 100$$$)
  • Sharpen
  • Rotate CW
  • Rotate CCW
  • Flip Horizontal
  • Flip Vertical
Output

After performing all operations, output the resulting image.

The image should be formatted as $$$n$$$ lines, each containing $$$m$$$ integers separated by spaces, or $$$m$$$ lines, each containing $$$n$$$ integers separated by spaces (depending on the rotation of the image.

Examples
Input
4 5
3 3 3 10 16
3 3 3 12 38
3 3 3 40 4
5 6 7 8 9
1
Blur
Output
9 4 6 11 11 
8 3 8 14 14 
8 4 9 13 13 
5 4 9 11 10
Input
3 3
1 2 3
4 5 6
7 8 9
1
Shift 0 1
Output
4 5 6 
7 8 9 
1 2 3
Input
3 3
1 2 3
4 5 6
7 8 9
1
Sharpen
Output
-99 2 3 
4 5 6 
7 8 109
Input
3 4
1 2 3 4
5 6 7 8
9 10 11 12
2
Rotate CW
Flip Horizontal
Output
1 5 9 
2 6 10 
3 7 11 
4 8 12