Patrik và Josip đang đi du lịch trên chuyến tàu Đông-Tây bao gồm tổng cộng ~n~ trạm xe với ~n-1~ tuyến đường nối giữa trạm ~i~ và trạm ~i+1~ ~(1 \le i < n)~. Chuyến đi xuất phát từ trạm ~1~, đi qua từng trạm và kết thúc ở trạm ~n~. Cả hai đang thảo luận xem tuyến đường nào là ngắn nhất trong số ~n-1~ tuyến đường, vì vậy mỗi lần đi đến một trạm ~i~ ~(2 \le i \le n)~, Patrik hoặc Josip sẽ nói một câu:

• Patrik: "Đã qua ~t_i~ giờ kể từ lúc xuất phát ở trạm ~1~."
• Josip: "Mất ~t_i~ giờ để đi từ trạm ~y_i~ đến trạm hiện tại."

Dựa trên đoạn hội thoại của Patrik và Josip, bạn hãy xác định tuyến đường nào ngắn nhất.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 1000)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa thông tin thuộc một trong hai dạng: ~\text{Patrick} \; t_i~ ~(1 \le t_i \le 10^9)~ thể hiện câu nói của Patrick hoặc ~\text{Josip} \; y_i \; t_i~ ~(y_i < i; \; 1 \le t_i \le 10^9)~ thể hiện câu nói của Josip.

Output

• In ra trên một dòng gồm ba số nguyên ~t~, ~x_1~ và ~x_2~ lần lượt là thời gian để đi hết tuyến đường ngắn nhất và hai trạm nối trên tuyến đường ngắn nhất. Nếu có ít nhất hai tuyến đường ngắn nhất, ưu tiên tuyến đường có chỉ số trạm nhỏ hơn.

Samples

Sample Input 1

4
Patrik 3
Patrik 5
Josip 1 7

Sample Output 1

2 2 3

Sample Input 2

2
Josip 1 5

Sample Output 2

5 1 2

Sample Input 3

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

Sample Output 3

2 3 4

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~t_i \le 1000~
• Subtask ~2~ với ~30\%~ số điểm: Mọi câu nói đều là của Patrik
• Subtask ~3~ với ~40\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

• Trong ví dụ đầu tiên, mất ~3~ giờ để đi từ trạm ~1~ đến trạm ~2~ và mất ~5~ giờ để đi từ trạm ~1~ đến trạm ~3~, vì vậy tuyến đường nối trạm ~2~ và trạm ~3~ mất ~2~ giờ di chuyển, cũng là tuyến đường ngắn nhất.
• Trong ví dụ thứ ba, tuyến đường nối trạm ~3-4~ và tuyến đường nối trạm ~4-5~ đều mất ~2~ giờ di chuyển, nhưng ưu tiên tuyến đường nối trạm chỉ số nhỏ hơn.