Задача D. Принцесса или тигр?

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

У Фрэнка Стоктона есть сказка, которая называется «Принцесса или тигр?» В этой сказке один узник должен угадать, в какой из трех комнат находится принцесса, а в какой — тигр. Если он угадает, в какой комнате находится принцесса, то женится на ней, если не угадает, то его (вполне возможно) растерзает тигр.

В некотором царстве правил король. Однажды он тоже прочитал эту сказку.

— В самый раз для моих заключенных! — сказал он своему министру. — Только я не хочу полагаться на случайности. Пусть на дверях каждой комнаты повесят номера, а заключенному будет кое-что сказано о них. Если узник не дурак и способен рассуждать логически, он сумеет сохранить себе жизнь и в придачу заполучить прелестную невесту.

— Блестящая идея, ваше величество! — согласился министр.

Настал день первого испытания. Потирающий руки король, объявил узнику, что в одной комнате находится принцесса, в другой - тигр, третья комната пуста. После этого стражник произнес два высказывания, в которых говорилось о наличии или отсутствии принцессы или тигра в комнате с некоторым номером.

Поскольку в королевстве принцесс на выданье очень много, а содержание узников обходится недешево, король потихоньку дал указание министру решить две проблемы разом и составить программу для выбора нужной комнаты. Ну а поскольку придворным программистом сейчас являетесь именно вы - кому решать эту проблему?

Поговорив с узником, вы выяснили его приоритеты предпочтений:

1. Если комната с принцессой определяется однозначно - выбираем номер этой комнаты (ура, свадьба).

2. Иначе, если комната с принцессой определяется неоднозначно, а комната с тигром однозначно - выбираем номер комнаты, в которой возможно есть принцесса и точно нет тигра (вдруг повезет).

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

Осталось составить программу...

Формат входного файла

В первой строке входного файла записано первое высказывание - одно из четырех возможных предложений:

Princess is in room

Princess is not in room

Tiger is in room

Tiger is not in room

В конце предложения через пробел указан номер комнаты.

Во второй строке в том же формате записано второе высказывание. Гарантируется, что высказывания истинны, не совпадают и не противоречат друг другу.

Формат выходного файла

Выведите номер комнаты, который следует выбрать узнику в соответствии с приоритетом предпочтений. Если однозначный выбор сделать нельзя - выведите номера всех подходящих комнат через пробел в порядке возрастания.

Ограничения

Номер комнаты - целое число 1, 2 или 3.

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: В высказываниях речь идет только о принцессах, баллы: 30.

Подзадача 2: Нет ограничений, баллы: 70.

Пояснения к примерам

В первом примере принцесса в комнате 2 - выбираем эту комнату.

Во втором примере принцессы нет в комнатах 1 и 3, значит она в комнате 2.

В третьем примере принцессы нет в комнате 2, значит она может быть в комнатах 1 и 3, но в первой комнате тигр, поэтому выбираем комнату 3.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
Princess is not in room 3
Princess is in room 2
2
2
Princess is not in room 3
Princess is not in room 1
2
3
Tiger is in room 1
Princess is not in room 2
3

0.131s 0.024s 15