교통량 측정

Farmer John의 농장 옆 고속도로에서 최근 교통량이 급격히 늘어난 것처럼 보인다. 이를 확인하기 위해 Farmer John은 고속도로의 교통 흐름을 측정하려고 한다. 각 센서는 도로의 한 구간에서 흐르는 교통량의 비율을 측정할 수 있다.

그런데 어느 날 헛간을 걷다가 넘어지면서 센서 상자를 큰 우유 통에 빠뜨리고 만다. 그 뒤로 센서는 제대로 작동하지 않는다. 센서는 이제 교통 흐름 비율을 하나의 정확한 값으로 출력하지 않고, 가능한 값의 범위를 출력한다. 예를 들어 센서가 범위 $[7, 13]$을 출력하면, 해당 도로 구간의 교통 흐름 비율이 7 이상 13 이하라는 뜻이다.

고속도로는 농장 옆으로 $N$마일 뻗어 있고, 교통은 1마일 지점에서 $N$마일 지점 방향으로만 흐른다. Farmer John은 고속도로의 1마일 구간마다 하나씩, 모두 $N$개의 센서를 설치하려고 한다. 어떤 구간에는 고속도로로 진입하는 진입로가 있고, 그런 경우 Farmer John은 진입로에 센서를 설치해 유입되는 교통량을 대략 측정한다. 어떤 구간에는 고속도로에서 빠져나가는 진출로가 있고, 그런 경우에는 진출로에 센서를 설치한다. 각 구간에는 기껏해야 하나의 진입로 또는 진출로만 있다. 진입로도 진출로도 없는 구간에서는 Farmer John이 고속도로 본선에 센서를 설치한다.

Farmer John의 $N$개 센서가 출력한 값을 보고, 1마일 지점 이전에 고속도로에 처음 있던 교통 흐름 비율과 $N$마일 지점을 지나 계속 고속도로에 남아 있는 교통 흐름 비율을 나타내는 가장 좁은 범위를 구하라. 이 범위는 $N$개 센서 값 모두와 모순이 없어야 한다.

첫째 줄에 $N$이 주어진다 ($1 \leq N \leq 100$). 다음 $N$개 줄은 1마일 구간을 1마일부터 $N$마일 순서대로 나타낸다. 각 줄은 "on" (이 구간에 진입로가 있음), "off" (진출로가 있음), "none" (진입로도 진출로도 없음) 중 하나인 문자열과, $0 \ldots 1000$ 범위의 두 정수로 이루어진다. 두 정수는 해당 구간 센서 범위의 하한과 상한이다. 구간에 진입로 또는 진출로가 있으면 센서 값은 그 진입로 또는 진출로에서 나온 것이고, 그렇지 않으면 고속도로 본선에서 나온 것이다. 고속도로 구간 중 적어도 하나는 "none"으로 지정된다.

첫째 줄에는 1마일 지점 이전 교통 흐름 비율의 가능한 가장 좁은 범위를 나타내는 두 정수를 출력한다. 둘째 줄에는 $N$마일 지점 이후 교통 흐름 비율의 가능한 가장 좁은 범위를 나타내는 두 정수를 출력한다. 유효한 답이 항상 존재한다.

이 예에서 2번 구간과 3번 구간의 센서 값을 종합하면 이 구간을 지나는 흐름 비율은 $[11, 14]$ 범위 안에 있다. $[10,14]$와 $[11,15]$ 두 값 모두와 모순이 없는 범위가 이것뿐이기 때문이다. 1마일 구간에서는 진입로로 정확히 1단위의 흐름이 들어오므로, 1마일 지점 이전의 흐름 비율은 $[10, 13]$ 범위여야 한다. 4마일 구간에서는 진출로로 2단위에서 3단위 사이의 흐름이 빠져나가므로, 그 이후 가능한 흐름 비율의 범위는 $[8,12]$이다.