На шоссе, прилегающем к ферме Фермера Джона сильно увеличился трафик,
или по крайней мере так показалось ФД. Чтобы убедиться, он хочет измерить
трафик на шоссе посредством множества датчиков, установленных на некотором
участке дороги.
К несчастью, ФД уронил свои датчики в молоко, и теперь они работают
не очень хорошо. Вместо вывода точного значения трафика, датчик теперь
выдаёт диапазон возможных значений. Например, датчик может показывать
диапазон \([7, 13]\), означающий, что плотность трафика на этом участке
не меньше чем 7 и не больше чем 13.
Шоссе вдоль фермы имеет протяжённость в \(N\) миль и движение происходит
в одном направлении от мили 1 к миле \(N\). ФД хочет установить \(N\) датчиков,
по одному на каждом одномильном сегменте шоссе. В некоторых из этих сегментов
имеются пандусы для въезда, которые позволяют трафику вливаться на шоссе;
в каждом из таких случаев ФД устанавливает свой датчик так, чтобы измерять
(примерно) входящий трафик. В некоторых сегментах имеются пандусы для выезда,
здесь ФД устанавливает датчик так, чтобы измерять выходящий трафик. Каждый
сегмент содержит не более одного пандуса. Если на сегменте нет пандусов,
ФД устанавливает датчик на собственно шоссе.
По заданным показаниям \(N\) датчиков, определите наиболее точно
диапазоны, описывающие движение на шоссе от мили 1 к миле \(N\). Эти диапазоны
должны не противоречить показаниям всех \(N\) датчиков.
ФОРМАТ ВВОДА (файл traffic.in):
Первая строка содержит число \(N\) (\(1 \leq N \leq 100\)). Каждая из оставшихся
\(N\) строк описывает одномильный сегмент дороги в порядке от мили 1 к миле \(N\).
Каждая строка сначала содержит символы "on" (если это сегмент с пандусом для
въезда), "off" (если это сегмент с пандусом для выезда), "none", если сегмент
не содержит пандусов, за которыми следуют два целых числа в интервале \(0 \ldots 1000\),
описывающих интервал, показанный соответствующим датчиком. Если сегмент с пандусом - считывается показание с датчика на пандусе, иначе - с датчика на шоссе.
Как минимум для одного датчика будет указано "none".
ФОРМАТ ВЫВОДА (файл traffic.out):
Первая строка вывода должна содержать два целых числа наиболее точно задающих
интервал трафика до мили 1. Вторая строка должна содержать два целых числа,
определяющих возможный диапазон трафика после мили \(N\). Гарантируется, что
решение существует для всех тестов.
ФОРМАТ ВВОДА:
4
on 1 1
none 10 14
none 11 15
off 2 3
ФОРМАТ ВЫВОДА:
10 13
8 12
В этом примере, комбинация считываний датчиков с сегментов 2 и 3 сужает интервал
до \([11, 14]\), поскольку только показания в этом интервале соответствуют обоим
считываниям \([10,14]\) и \([11,15]\). На миле 1 ровно значение 1 представляет входящий трафик,
поэтому входящий трафик может быть в диапазоне \([10, 13]\). На миле 4 от 2 до 3
единиц потока может покинуть трафик, поэтому выходной поток после мили 4
может быть \([8,12]\).
Автор: Brian Dean