Back to Space

For the 50th anniversary of the first crewed spaceflight, a new reusable spacecraft called "Vostorg" is being built. The rectangular part of its hull (called the rectangle below) must be covered with square heat-shield tiles of one size and several colors. The rectangle has $r$ rows of $c$ tiles each. The tiles must form a given pattern.

Laying tiles one at a time is too laborious, so the pattern is built from identical rectangular panels made of tiles. Panels are attached one after another, filling the rectangle row by row from top to bottom. Each row of panels may be shifted to the right by the same number of tiles relative to the previous row. Panels may extend beyond the rectangle. All panels must have the same orientation: when one panel is translated onto another, the colors of their tiles must match.

The chief designer wants to pick a panel size $a \times b$ and a shift $s$ so that the pattern can be laid out with these panels, and the panel area is as small as possible. Here $0 \le s < b$ is the shift to the right of each next row relative to the previous one.

An example of panels with $a = 2$, $b = 3$, $s = 1$.

The first line contains two integers $r$ and $c$, the size of the rectangle in tiles. The next $r$ lines give the tile colors. Each of the $k \le 26$ colors is one of the first $k$ uppercase Latin letters. It is guaranteed that a panel of size $a \times b$ exists for this rectangle with $2a \le r$ and $2b \le c$.

Print three integers $a$, $b$, and $s$ that satisfy the conditions. If several solutions exist, print any of them.

The shift $s$ has no restriction. Both $r$ and $c$ do not exceed 1961.

The tiling for the second example is shown below. Parts of the panels that stick out past the rectangle are not drawn.