eolymp
bolt
Try our new interface for solving problems
Problems

Laser Turret Maintenance

Laser Turret Maintenance

Time limit 3 seconds
Memory limit 256 MiB

As the Chief Weapons Officer of an Imperial Star Destroyer, one of your duties is the routine maintenance of laser turret panels. Each panel is a square composed of n×n turret sockets, n of which house a turret. To avoid asymmetric wear and tear on the panel circuits, turrets should be regularly moved between sockets. Turrets are capable of rotating in-place in 45^o increments, but may not fire in between such rotations. All turrets are aligned with the panel grid upon insertion.

The most important constraint on turret placement is that turrets should not "conflict", meaning they should not be able to shoot each other. Thus, they must be positioned such that no two turrets on the same panel share the same grid horizontal, vertical, or diagonal line. To streamline the process of turret maintenance and reduce placement errors, the Empire has mandated that all turret socket exchanges be performed as rotations or reflections of existing configurations, as conflict prevention is invariant under such transformations.

Given a valid (non-conflicting) n×n panel configuration, there are three clockwise rotations: 90^o, 180^o, and 270^o. In addition there are four mirror planes: vertical, horizontal, diagonal (across the cells where row = col), and anti-diagonal (across the cells where row + col = n - 1). Thus there are eight Empire-approved configurations (some of which may be identical for configurations that are symmetric under rotation by 90^o and/or 180^o). Figure 1 shows eight approved configurations for n = 5, while Figure 2 shows an example from n = 6 of a configuration with an 180^osymmetry and an example from n = 4 of a configuration with a 90^o symmetry.

Figure 1: Set of configurations for n = 5 obtainable by symmetry operations

Figure 1: Set of configurations for n = 5 obtainable by symmetry operations

Figure 2: Examples of rotational symmetry in configurations

While the panel is a two-dimensional matrix, the nature of a valid configuration (that there is only one turret in each row) allows it to be represented by a one-dimensional vector, giving the column positions for the turret in each row. The top row of the panel has index zero, similar to the numbering of screen coordinates.

Write a method that receives one valid panel configuration and computes, in the same one-dimensional form, the other seven configurations that are approved by the Empire under the rotations and reflections listed above. Specifically, your program is to write back the configuration received, followed by the configurations obtained by the90^o, 180^o, and 270^o rotations in that order followed by the reflections in the order vertical mirror, antidiagonal mirror, horizontal mirror, and diagonal mirror.

Input data

Input consists of an indeterminate number of lines consisting of integers separated by white space. The first integer on the line gives the size of the problem (n); zero indicates the end of processing, otherwise 4n20. Following that n will be n integers giving the column positions.

Output data

For each problem, print eight lines giving the approved configurations in the order specified above, in which on each line the numbers are right justified in fields of three characters. These eight lines are followed by a blank line, which is shown in Sample Output as "(blank line)".

Examples

Input example #1
4 1 3 0 2
5 0 2 4 1 3
6 1 3 5 0 2 4
0
Output example #1
  1  3  0  2
  1  3  0  2
  1  3  0  2
  1  3  0  2
  2  0  3  1
  2  0  3  1
  2  0  3  1
  2  0  3  1

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

  1  3  5  0  2  4
  2  5  1  4  0  3
  1  3  5  0  2  4
  2  5  1  4  0  3
  4  2  0  5  3  1
  3  0  4  1  5  2
  4  2  0  5  3  1
  3  0  4  1  5  2

Source ACM ICPC Regionals 2009: North America - Pacific Northwest