Farmer John dán trên cửa chuồng một danh sách \(N\) con bò (\(1 \le N \le 50\,000\)) được sắp xếp theo thứ tự bảng chữ cái. Tên mỗi con bò được biểu diễn bằng một chuỗi phân biệt gồm từ 1 đến 20 ký tự chữ thường.

Vốn luôn thích gây rắc rối, bò Bessie thay đổi danh sách bằng cách sắp xếp lại thứ tự các con bò. Ngoài ra, cô còn xáo trộn các chữ cái trong tên của từng con bò. Cho danh sách đã bị thay đổi này, hãy giúp Farmer John tính, đối với mỗi mục trong danh sách, vị trí nhỏ nhất và lớn nhất mà mục đó có thể từng xuất hiện trong danh sách ban đầu.

Dữ liệu vào

• Dòng 1 chứa một số nguyên duy nhất \(N\).
• Các dòng \(2..1+N\): mỗi dòng chứa tên đã bị xáo trộn thứ tự các chữ cái của một con bò.

Dữ liệu ra

• Các dòng \(1..N\): dòng \(i\) cho biết vị trí nhỏ nhất và lớn nhất trong danh sách ban đầu của Farmer John mà phiên bản gốc của chuỗi đầu vào thứ \(i\) có thể từng xuất hiện.

Ví dụ

4
essieb
a
xzy
elsie

2 3
1 1
4 4
2 3

Nguồn

USACO 2012 December Contest, Bronze — Problem 2: Scrambled Letters

Tác giả đề: Brian Dean, 2012.