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, 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.