Школьники Вася и Петя играют в
следующую игру. Имеется клетчатое поле размером M на N клеток,
изначально все клетки пусты. На каждом ходу игрок выбирает строку или столбец,
содержащий (содержащую) хотя бы одну пустую клетку, и закрашивает все пустые
клетки в этой строке или столбце. Выигрывает тот игрок, кто закрасил последнюю
пустую клетку.
Определите, кто из игроков
победит, если оба всегда делают наилучшие возможные ходы. Если выиграет первый
игрок, то определите также, сколько у него есть различных вариантов первого
хода, гарантированно приводящих к победе.
Входные данные
Два целых числа M и N,
разделенных пробелом.
Ограничения: 1 ≤ M, N ≤ 106.
Выходные данные
В первой
строке выведите цифру 1, если выигрывает первый игрок (то есть начинающий
игру), и цифру 2, если выиграет второй игрок. Если выиграет первый игрок, то во
второй строке выведите количество вариантов его первого хода, ведущих к победе.
|
Пример ввода 1
2
2
Пример вывода 1
2
|
Пример ввода 2
3
2
Пример вывода 2
1
3
|
Система оценивания.
Решения, верно работающие при M, N ≤ 1000, будут
оцениваться из 75 баллов.
