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.
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,
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.
Problem Author: Vladimir Yakovlev (idea — Stanislav Vasilyev)
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008