Fastest Segment on the Tram

Patrik and Josip were riding a tram for \(n\) stations. Except for the boarding station, at each subsequent station one of the following events occurs:

• Patrik says: "It has taken \(t\) minutes from boarding until now." In this case, \(t\) is the cumulative time from station 1 to the current station.
• Josip says: "It took \(t\) minutes from station \(y\) to here." In this case, the time for the segment from station \(y\) to the current station is \(t\) minutes.

Your task is to determine, based on these announcements, the two consecutive stations between which the travel time is the shortest and output those station numbers along with the minimal travel time.

Note: Station 1 is the boarding station with a time of \(0\) minutes. It is guaranteed that the input data allows the calculation of cumulative times for every station.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10^5\)) representing the number of stations.

Each of the following \(n-1\) lines describes an event taking place at stations 2 through \(n\). Each event is in one of the following two formats:

• P t: Patrik reports that the cumulative time from the boarding station is \(t\) minutes. (\(1 \le t \le 10^9\))
• J y t: Josip reports that the time from station \(y\) to the current station is \(t\) minutes. (\(1 \le y <\) current station, \(1 \le t \le 10^9\))

It is guaranteed that the events are given in the order of increasing station number and that sufficient information is provided to derive the cumulative time at each station (with station 1 having a time of \(0\)).

outputFormat

Output three space-separated integers: the first station number, the second station number (these two stations being consecutive) between which the travel time is minimal, and the minimal travel time.

sample

4
P 10
J 1 15
J 2 10

2 3 5