Вы всемогущее существо и создали прямоугольный мир. Ваш мир настолько удобный, что может быть представлен в виде таблицы размером \(r \times c\). Каждая клетка этой таблицы обозначает некоторую страну. Каждая страна принадлежит некоторой религии. Всего существует две религии в этом мире. Одна из религий называется Beingawesomeism, люди этой религии делают добрые поступки, чтобы быть хорошими. Другая религия называется Pushingittoofarism, люди этой религии совершают убийства, чтобы быть плохими.
На самом деле вы не абсолютно всемогущи. У вас есть только одна сила, которую вы можете применить бесконечное число раз! Ваша сила позволяет вам посылать миссионерские группы. Когда миссионерская группа из определенной страны, назовем ее \(a\), приходит в другую страну \(b\), она меняет религию страны \(b\) на религию страны \(a\).
Силу можно использовать следующим образом:
- Вы выбираете горизонтальную полоску \(1 \times x\) или вертикальную полоску \(x \times 1\) внутри таблицы. Вы можете выбирать любое значение \(x\);
- Вы выбираете направление \(d\). Если вы выбрали горизонтальную полоску, вы можете выбрать направления СЕВЕР или ЮГ. Если вы выбрали вертикальную полоску, вы можете выбрать направления ВОСТОК или ЗАПАД;
- Вы выбираете количество шагов \(s\);
- Вы командуете каждой стране находящейся внутри выбранной полоски послать миссионерскую группу, которая пройдет \(s\) шагов в направлении \(d\). На каждом шаге, она посетит и возможно поменяет религию (способом описанным ранее) у всех \(s\) стран на своем пути;
- параметры \(x\), \(d\), \(s\) можно выбирать такими, чтобы никакая миссионерская группа не вышла за пределы таблицы.
Следующая картинка показывает один возможный способ использования силы. Здесь символ A обозначает страну с религией Beingawesomeism и символ P обозначает страну с религией Pushingittoofarism. Здесь мы выбрали горизонтальную полоску \(1 \times 4\), направление СЕВЕР и количество шагов \(s = 2\).
Вы существо, которое верит в свободную волю каждого человека. Однако, вы хотите немедленно приостановить убийства. Таким образом вы решили использовать силу и попробовать сделать Beingawesomeism религией всех стран.
Какое минимальное количество применений силы требуется, чтобы сделать религией каждой страны Beingawesomeism?
Если это сделать невозможно, вы должны признать свой провал и сообщить об этом.
Выходные данные
Для каждого тестового случая, выведите единственную строку, содержащую минимальное возможное количество использований силы нужное, чтобы сделать Beingawesomeism религией во всех странах. Если сделать Beingawesomeism религией во всех странах невозможно, выведите строку «MORTAL» (без кавычек).
Примечание
В первом тестовом случае можно добиться требуемого за два применения силы.
Первое использование:
Второе использование:
Во втором тестовом случае можно добиться требуемого за одно применение силы.
В третьем тестовом случае невозможно сделать религией всех стран Beingawesomeism, поэтому ответ «MORTAL».