Gần đây, lưu lượng xe trên tuyến đường cao tốc cạnh trang trại của Farmer John tăng mạnh, hoặc ít nhất Farmer John cảm thấy như vậy. Để biết chắc, ông muốn đo lưu lượng giao thông trên đường cao tốc bằng một bộ cảm biến, mỗi cảm biến có khả năng đo lưu lượng xe trên một đoạn đường.

Đáng tiếc, một ngày nọ khi đi qua chuồng bò, Farmer John vấp ngã và làm rơi hộp cảm biến vào một bể sữa lớn, khiến chúng không còn hoạt động tốt như trước. Thay vì đưa ra một giá trị lưu lượng chính xác duy nhất, giờ đây mỗi cảm biến xuất ra một khoảng giá trị có thể có. Chẳng hạn, một cảm biến có thể xuất ra khoảng \([7, 13]\), cho biết lưu lượng xe trên một đoạn đường không nhỏ hơn 7 và không lớn hơn 13.

Đường cao tốc chạy cạnh trang trại trong \(N\) dặm và xe trên đường chỉ đi theo một hướng, từ dặm 1 về phía dặm \(N\). Farmer John muốn lắp \(N\) cảm biến — mỗi đoạn dài 1 dặm của đường cao tốc có một cảm biến. Một số đoạn có đường dẫn nhập cho phép xe đi vào đường cao tốc; trong mỗi trường hợp như vậy, Farmer John sẽ lắp cảm biến trên đường dẫn nhập để đo (xấp xỉ) lượng xe đi vào. Một số đoạn có đường dẫn ra cho phép xe rời đường cao tốc; trong mỗi trường hợp như vậy, Farmer John sẽ lắp cảm biến trên đường dẫn ra. Mỗi đoạn có nhiều nhất một đường dẫn. Nếu một đoạn đường cao tốc không có đường dẫn nhập hay đường dẫn ra, Farmer John lắp cảm biến ngay trên đường cao tốc chính.

Với số liệu từ \(N\) cảm biến của Farmer John, hãy xác định những khoảng cụ thể nhất có thể mô tả lưu lượng xe ban đầu trên đường cao tốc trước dặm 1 và lưu lượng xe tiếp tục đi trên đường cao tốc sau dặm \(N\). Các khoảng này phải nhất quán với số liệu của cả \(N\) cảm biến.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng còn lại mô tả một đoạn đường dài 1 dặm, theo thứ tự từ dặm \(1\) đến dặm \(N\). Mỗi dòng chứa một chuỗi là on (nếu đoạn này có đường dẫn nhập), off (nếu có đường dẫn ra), hoặc none (nếu không có đường dẫn), theo sau là hai số nguyên trong phạm vi \(0 \ldots 1000\), biểu thị đầu mút dưới và đầu mút trên của khoảng đo từ cảm biến trên đoạn này. Nếu đoạn đường có một đường dẫn, số liệu cảm biến được đo trên đường dẫn đó. Nếu không, số liệu được đo trên đường cao tốc chính. Có ít nhất một đoạn đường cao tốc được ký hiệu là none.

Dữ liệu ra

Dòng đầu tiên chứa hai số nguyên biểu thị khoảng cụ thể nhất có thể của lưu lượng xe trước dặm 1. Dòng thứ hai chứa hai số nguyên biểu thị khoảng cụ thể nhất có thể của lưu lượng xe sau dặm \(N\). Dữ liệu luôn bảo đảm tồn tại một lời giải hợp lệ.

Ví dụ

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

10 13
8 12

Nguồn

USACO 2019 February Contest, Bronze — Measuring Traffic

Tác giả: Brian Dean.