ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Square Country 4

Time limit: 1.0 second
Memory limit: 64 MB
There had never been trams in Square Country. No doubt, this worried citizens a lot. At a referendum, people decided that a tram network should be built all over the country. They also wanted this network to be connected with the tram network of adjacent Rectangular Country. However, when projecting works started, it turned out that there was a problem: Square Country and Rectangular Country had different coordinate systems; moreover, their coordinate axes were not parallel.
President of Square Country held a meeting with Square Parliament and took a historic decision to turn the coordinate system of the country by an angle α about the point (0, 0). The decision turned out to be rather unpopular because in Square Country all privately-owned plots of land were sets of squares with sides parallel to the coordinate axes and with integer-coordinate vertices. That meant that after the historic turn it would be necessary to alter the boundaries of private estates. The rules of establishing new boundaries was approved by President's decree. For each cell of unit size, a new owner was to be established as follows. If there was a citizen who owned more than a half of that cell, then this person was to become the new owner of the whole cell. Otherwise, the whole cell was to become state property.
Square Government asked you to automatize the redistribution of private property. You are given a map where all plots are shown. You must compile a new map in which plots after the turn will be shown.

Input

Plots located far from the center are not in demand in Square country; that is why all private estates are situated inside the square [−n, n] × [−n, n]. The map is a square table in each cell of which there is a lowercase English letter, which is a unique code of the owner of the corresponding plot. If there is a dot in a cell, then the corresponding plot belongs to the state. In the map, the x axis is directed to the right, and the y axis is directed upward.
The first line contains the numbers n and α separated by a space; 1 ≤ n ≤ 30; 0 ≤ α ≤ 90; the angle α is given in degrees. The following 2n lines contain 2n symbols each; they form the map of private estates inside the square [−n, n] × [−n, n].

Output

After the turn, some estates may fall out of the square [−n, n] × [−n, n]. Therefore, output the map of estates in the square [−2n, 2n] × [−2n, 2n] after the turn of coordinates and property redistribution, in the same format.

Sample

inputoutput
2 45.0
aaaa
aaaa
bb.x
bbx.
........
........
...aa...
..aa.x..
..a..x..
...bb...
........
........
Problem Author: Vladimir Yakovlev (idea — Stanislav Vasilyev)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008
To submit the solution for this problem go to the Problem set: 1616. Square Country 4