Traffic Flow Sensor Analysis

Farmer John has installed N sensors along a highway segment of N miles to monitor the traffic flow. Unfortunately, after an accident the sensors no longer return precise values and instead each sensor outputs an interval. Depending on the type of segment, the sensor reading is interpreted in one of three ways:

• Main highway (none): The sensor reading tells us that the highway flow entering that segment is in the interval \([L, R]\). There is no change in the highway flow across this segment.
• On-ramp (on): The sensor is placed on an on-ramp and reports that the ramp’s flow is in the interval \([L, R]\). Consequently, the highway flow increases by that amount.
• Off-ramp (off): The sensor is placed on an off-ramp and reports that the off-ramp flow is in the interval \([L, R]\). In this case, the highway flow decreases by that amount. Note that off-ramp flow cannot exceed the highway flow available and the flow must remain nonnegative.

Given the readings on all N segments (each 1 mile in length), determine the most accurate possible range for the highway flow immediately before mile 1 and immediately after mile N such that all sensor readings are consistent.

inputFormat

The input begins with a single integer N (the number of segments). Following this, there are N lines. Each line contains a string and two integers. The string represents the sensor type and is one of "on", "off", or "none". The two integers L and R indicate the lower and upper bounds of the sensor reading, respectively.

outputFormat

Output two lines:

• The first line contains two integers representing the minimum and maximum possible highway flow immediately before mile 1.
• The second line contains two integers representing the minimum and maximum possible highway flow immediately after mile N.

sample

4
none 10 14
on 1 3
none 10 14
off 2 4

10 13
7 12