Farmer John thấy giao thông trên đường cao tốc cạnh nông trại dường như tăng mạnh. Để chắc chắn, ông muốn cảm biến đo lưu lượng từng đoạn.

Nhưng một ngày đi qua kho ông vấp và làm rơi hộp cảm biến vào thùng sữa lớn. Chúng chỉ còn cho khoảng thay vì số chính xác: $[7,13]$ nghĩa là ít nhất 7 và nhiều nhất 13.

Đường dài $N$ dặm cạnh trại, chỉ lưu thông từ dặm 1 đến $N$. Ông lắp $N$ cảm biến, mỗi đoạn một dặm một cái. Có đường vào thì đo xấp xỉ lưu lượng vào trên đó; có đường ra thì đo trên nó. Mỗi đoạn tối đa một nhánh; không có thì đo đường chính.

Từ $N$ kết quả, tìm khoảng khả dĩ chặt nhất trước dặm 1 và sau dặm $N$, phù hợp mọi kết quả.

Dữ liệu vào

Đầu tiên $N$ ($1\le N\le100$), rồi $N$ dòng theo thứ tự $1\ldots N$. Mỗi dòng on (vào), off (ra), none (không nhánh), rồi hai số nguyên $0\ldots1000$ là cận dưới và trên. Có nhánh thì đo nhánh, không thì đường chính. Ít nhất một đoạn none.

Dữ liệu ra

Dòng một hai số nguyên của khoảng chặt nhất trước dặm 1; dòng hai sau dặm $N$. Luôn có lời giải hợp lệ.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

10 13
8 12

Ghi chú

Đoạn 2, 3 cho $[10,14]$ và $[11,15]$, cùng giới hạn $[11,14]$. Dặm 1 thêm đúng 1 nên trước đó $[10,13]$. Dặm 4 bớt 2 đến 3 nên sau đó $[8,12]$.

Tác giả bài toán: Brian Dean