Sections > Unsorted > problem:

Captcha

Section problems

• Making Potions
• Santa Gifts
• Chessboard Pattern
• 10^6
• A + B
• A+B
• Amuz Deluxe
• C++ и Java
• Captcha
• Hello World
• Radar Defence
• World of Warlcraft
• World of Warlcraft
• 1
• XOR на прямоугольнике
• XOR на прямоугольнике (усложнё...
• You're in the army now

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Captcha

Чтобы предотвратить автоматизацию запросов к различным веб-сервисам (например, для защиты форума от спама), в настоящее время чаще всего используют капчу — простейший тест Тьюринга, задачу, которую просто выполнить человеку и сложно — машине.

В одном из наиболее популярных вариантов капчи нужно определить различные символы (например, цифры) на деформированном изображении. Ваша компания в настоящее время занимается созданием средства для обхода такой капчи. Часть работы уже сделана, а вам поручили реализовать распознавание цифр 7, 8 и 9.

$\text{[math]}$

Изображение цифры получено из одного из показанных выше оригинальных изображений (размера 80 × 80 пикселей) путём следующих преобразований:

Поворота на угол от 0 до 2π;
Скоса вдоль оси абсцисс с относительным смещением противоположных сторон от -100% до 100%;
Масштабирования вдоль осей абсцисс и ординат (независимо) с изменением размеров от 20% до 200%.

Закрашенная область изображения связна (между любыми двумя закрашенными пикселями есть путь, проходящий только через закрашенные пиксели, являющиеся соседями по стороне или углу) и не содержит пикселей на границе изображения.

Гарантируется, что цифра на изображении может быть распознана однозначно.

Входные данные

Первая строка содержит целые числа N и M (10 ≤ N, M ≤ 200) — высоту и ширину изображения.

Следующие N строк содержат по M символов 'x' или '.', образующих изображение. Символы 'x' соответствуют закрашенным пикселям изображения, символы '.' — незакрашенным.

Выходные данные

Выведите одно целое число — распознанную цифру.

Примеры

Входные данные

16 20
....................
...xxx..............
..xxxxxx............
..x...xxx...........
..xx...xxx..........
..xx.....x..........
...xx.....xxxx......
....xxx...xxxxxx....
.....xxxxxx..xxxx...
......xxxxx....xx...
.........x.x....xx..
...........xx....x..
............xxx..xx.
.............xxxxxx.
..............xxxx..
....................

Выходные данные

Входные данные

17 24
........................
.........xxx............
........xxxxxxxxx.......
........xxxxxxxxxx......
........x....xxxxx......
...............xx.......
..............xxx.......
..............xx........
.............xx.........
............xx..........
...........xxx..........
...........xx...........
..........xx............
.........xxx............
........xxx.............
........xx..............
........................

Выходные данные

Входные данные

12 20
....................
.........xxxxxxx....
........xxxx........
.......xxx..........
......xxxxx.........
.....xxx...xx.......
.....xx....xx.......
....xxx....xx.......
....xxx...xxx.......
.....x...xxx........
......xxxxx.........
....................

Выходные данные

Для отправки решений необходимо выполнить вход.