eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Падение яйца

Падение яйца

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Существует классическая задача, где вам даются два яйца и k - этажное здание, и Вы хотите знать наивысший этаж, с которого можно сбросить яйцо, не разбив его.

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

Вы знаете, что яйцо не разобьется если упадет с этажа 1, и разобьется если упадет с этажа k. Вы также знаете, что результаты эксперимента непротиворечивы: если яйцо не разбилось с этажа x, то оно не разобьется и с нижних этажей, если яйцо разбилось с этажа y, оно разобьется и на всех этажах выше.

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

Первая строка содержит два целых числа n и k (1n100, 3k100) - количество бросаний яиц и число этажей в здании. Каждая из следующих n строк содержит номер этажа и результат падения яйца. Номер этажа лежит между 1 и k, результатом падения является или SAFE или BROKEN.

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

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

Пример

Входные данные #1
2 10
4 SAFE
7 BROKEN
Выходные данные #1
5 6
Входные данные #2
3 5
2 SAFE
4 SAFE
3 SAFE
Выходные данные #2
5 4
Источник 2015 ACM North America - Pacific Northwest, Дивизион 2, Задача N