Rating changes for the last round are temporarily rolled back. They will be returned soon.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Cutting Jigsaw Puzzle

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Hedgehog recently remembered one of his favorite childhood activities, — solving puzzles, and got into it with new vigor. He would sit day in, day out with his friend buried into thousands of tiny pieces of the picture, looking for the required items one by one.

Soon the Hedgehog came up with a brilliant idea: instead of buying ready-made puzzles, one can take his own large piece of paper with some picture and cut it into many small rectangular pieces, then mix them and solve the resulting puzzle, trying to piece together the picture. The resulting task is even more challenging than the classic puzzle: now all the fragments have the same rectangular shape, and one can assemble the puzzle only relying on the picture drawn on the pieces.

All puzzle pieces turn out to be of the same size *X* × *Y*, because the picture is cut first by horizontal cuts with the pitch of *X*, then with vertical cuts with the pitch of *Y*. If we denote the initial size of the picture as *A* × *B*, then *A* must be divisible by *X* and *B* must be divisible by *Y* (*X* and *Y* are integer numbers).

However, not every such cutting of the picture will result in a good puzzle. The Hedgehog finds a puzzle good if no two pieces in it are the same (It is allowed to rotate the pieces when comparing them, but it is forbidden to turn them over).

Your task is to count for a given picture the number of good puzzles that you can make from it, and also to find the puzzle with the minimal piece size.

Input

The first line contains two numbers *A* and *B* which are the sizes of the picture. They are positive integers not exceeding 20.

Then follow *A* lines containing *B* symbols each, describing the actual picture. The lines only contain uppercase English letters.

Output

In the first line print the number of possible good puzzles (in other words, the number of pairs (*X*, *Y*) such that the puzzle with the corresponding element sizes will be good). This number should always be positive, because the whole picture is a good puzzle itself.

In the second line print two numbers — the sizes *X* and *Y* of the smallest possible element among all good puzzles. The comparison is made firstly by the area *XY* of one element and secondly — by the length *X*.

Examples

Input

2 4

ABDC

ABDC

Output

3

2 1

Input

2 6

ABCCBA

ABCCBA

Output

1

2 6

Note

The picture in the first sample test has the following good puzzles: (2, 1), (2, 2), (2, 4).

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/25/2020 08:19:07 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|