Pharm

A pharmer owns a rectangular pharm sized n×m. In order to break from the mundane, he devised a plan for his 2015 seasonal crops. He drew a map of his pharm, and colored each unit cell according to which type of crop he was going to cultivate on it. The same crop type can be grown on multiple cells.

As a consequence, different color zones can be spotted on his map. Two cells belong to the same zone if they share a common edge, and have the same color. The pharmer decided to only provide water to a single zone (the largest one), so he's now wondering which zone to choose. Moreover, he is willing to change the crop on a single unit cell, if that meant he would obtain a new largest zone. Your task is to help him achieve his goal.

Input

The first line of input contains an integer type, 1 ≤ type ≤ 2.
The second line of input contains integers m and n.
Each of the following m lines contains a sequence of n lowercase letters, indicating the color codes of the crop cultivated on each cell.

Output

If type = 1, you should only output one integer, equal to the maximum surface of any zone on the pharmer's map.
If type = 2, you should output the following:

  • on the first line, two integers x and y, indicating the coordinates of the cell which can be replanted in order to obtain a new largest zone.
  • on the second line, a single lowercase letter, indicating the color code of the new crop which should be planted at coordinates (x, y).

Constraints

  • 2 ≤ m ≤ 400
  • 2 ≤ n ≤ 400
  • 2 ≤ the total number of different crops ≤ 26
  • 30% of all testcases will ask the first type of question.
  • 70% of all testcases will ask the second type of question.
  • For the second question, in case of multiple cells that grant the same maximum sized zone, you should output the first one, lexicographically.
  • Each test will be scored separately. Your final score will be equal to the sum of all tests' scores.
  • This statement was written by Phteven.

Sample

InputOutput
1
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag
11
2
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag
3 4
v
First case: the largest zone is #6. It contains 11 cells.
Second case: by coloring the (3, 4) cell green, zones #6 and #8 would become a single zone (surface = 20).
Questions?

Sponsors Gold