시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

Figure 1: VR view of a Lego downtown

As an urban Lego engineer, it is vital to obtain every possible technological advantage over your competition. You have recently noticed how popular virtual reality technology is with human engineers and wish to have something similar to help woo venture capitalists. Luckily, a VR view of a Lego downtown is very simple. First, you only have to show buildings, and you already know the heights and locations of all the buildings you want to build. Secondly, Lego VR is only capable of presenting a view of cube-shaped section of the city. It does this by projecting the cube onto one of the planes containing one of the cubefs faces. Lego engineers may browse the view by rotating the cube-shaped city section 90 degrees at a time about any one of the X, Y , or Z-axes passing through its center.

You are to write a Lego VR program that will take as input an N ×N matrix view of a downtown area and a series of rotational commands and produce the resulting N × N matrix view of the same downtown area from the resulting perspective. The N × N input matrix will represent an overhead view of an N × N × N cube of a Lego downtown (with one face of the cube at ground level).

Each number in the input matrix indicates the height of the building in the corresponding location. For example, 0 indicates that no building is present, while 3 indicates a building 3 stories (Legos) high. Note that, in the initial overhead view, there is no hidden open space. In other words, the buildings are solid. Also note that only buildings are represented in the view, not the ground. Any region of the view that does not contain a block of a building will have value 0.

입력

Input consists of an unspecified number (at least one) of sets of three sections:

  1. Grid size — A single line containing a single integer N (1 ≤ N ≤ 9) which represents the size of the cube of buildings represented.
  2. Building heights — An N × N array of whole numbers in the range 0 to N (inclusive). Each row in the array is given on its own input line, and array elements are not delimited. This initial N × N array represents an overhead view of an N × N solid structure of Lego buildings, with each number representing the height of the building in the corresponding location. Height of 0 indicates that no Lego exists in the given location.
  3. A series of rotational commands about the center of the N × N × N cube containing the Legos, one of:
    • “X” — rotates about the horizontal axis in the current view. The cube rotates such that the face of the cube that is at the top of the current view moves forward to become the new viewing face.
    • “Y” — rotates about the vertical axis in the current view. The cube rotates such that the face of the cube that is at the left of the current view moves forward to become the new viewing face.
    • “Z” — rotates about the line-of-sight axis in the current view. The viewing face does not change but is rotated 90 degrees counterclockwise.
    • These commands are a single-unbroken string with at most 80 commands.

Between each two sets of input data is exactly one blank line. There will be no blank line before the first input set or following the last input set.

No invalid input will be provided.

출력

For each input case, output consists of an N ×N array of numbers in the range 0 to N (inclusive) representing the final view for each input array and its associated set of rotations. Output arrays must be separated by exactly one blank line, and there must be no white space following the last digit of the last output array. Similarly, the first digit of the first output array must be the first character in the output.

No extraneous output of any kind should be printed.

Since this program essentially generates views of 3-dimensional objects, it is good to be very specific in describing how these views are calculated. Looking at the figure above, note that the cube has six sides, top, left, bottom, and right are labeled. The front is the side of the cube nearest the viewer, and the back is the side farthest from the viewer. The initial input view is meant to represent a Lego city from above. Each number represents the heights of the building at that location (or correspondingly, the maximum distance from the back of the cube for any Lego piece in that row and column). When the cube is rotated, the numbers no longer indicate the height of buildings since the view is no longer (necessarily) a view from above. Instead, the numbers continue to represent the maximum distance from the back of the cube for any Lego piece in that row and column of the cube. The idea is that the numbers will represent those Legos that are nearest the viewer, and therefore those Legos that are visible to the viewer.

예제 입력 1

3
010
021
010
Z

5
11111
22222
33333
44444
55555
XXXY

9
000010000
000020000
000030000
000040000
135797531
000040000
000030000
000020000
000010000
ZXXXXZYYYYZXXXXZYYYYY

예제 출력 1

010
121
000

00005
00055
00555
05555
55555

500000000
550000000
555000000
555500000
988776655
555500000
555000000
550000000
500000000