Trên trục Ox có \(n\) điểm đánh số từ 1 đến \(n\), điểm thứ \(i\) ở vị trí có toạ độ \(x_{i}\ (1 \leq i \leq n)\). Mỗi điểm được tô một trong ba màu xanh, đỏ, vàng. Hãy tìm trên trục số một đoạn thẳng thoả mãn hay điều kiện sau:

- Trong đoạn thẳng đó mỗi màu xuất hiện một lần.

- Độ dài đoạn thẳng là nhỏ nhất.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên dương \(n\ (1 \leq n \leq 10^{6})\).

+ \(n\) dòng tiếp theo, mỗi dòng chứa hai giá trị \(x_{i},\ m_{i}\), trong đó \(x_{i}\) cho biết toạ độ của điểm thứ \(i\) trên trục số \((1 \leq x_{i} \leq 10^{9},1 \leq i \leq n)\); số \(m_{i}\) kí hiệu màu của các điểm, \(m_{i} = 1\) là màu xanh, \(m_{i} = 2\) là màu đỏ, \(m_{i} = 3\) là màu vàng.

Kết quả:

+ Một số là độ dài đoạn thẳng thoả mãn yêu cầu bài toán, nếu không tìm thấy đoạn thẳng nao thoản mãn yêu cầu thì ghi \(- 1\)

Ví dụ

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm có \(1 \leq n \leq \ 10^{2}\);

+ Có 30% số test khác tương ứng 30% số điểm có \(1 \leq n \leq 10^{3}\);

+ Có 40% số test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.