Задача D. Треугольник Максима ≡

Условие

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.

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

Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.

Система оценивания

Решения, правильно работающие только для целых чисел f_i, имеющих одинаковую четность, будут оцениваться из 40 баллов.

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

Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера. Последующие n строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число f_i — частоту, выставленную на тюнере, в герцах, и слово closer или слово further для каждой частоты, кроме первой.

Слово closer означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |f_i − f_треуг.| < |f_i − 1 − f_треуг.|.

Слово further означает, что частота данной ноты дальше, чем предыдущая.

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

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

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

В выходной файл необходимо вывести через пробел два вещественных числа с точностью не менее 10^− 8 — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.

Ограничения

2 ≤ n ≤ 1000, 30 ≤ f_i ≤ 4000

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

3
440
220 closer
300 further

30.0 260.0

4
554
880 further
440 closer
622 closer
	

531.0 660.0