Tên bị xáo

Có $N$ tên bò, mỗi tên là một chuỗi ký tự thường phân biệt. Danh sách gốc được sắp xếp theo thứ tự từ điển. Kẻ phá hoại đã đảo lộn thứ tự danh sách và xáo trộn các ký tự trong mỗi tên.

Với mỗi tên đã bị xáo trộn trong danh sách mới, hãy tìm vị trí nhỏ nhất và vị trí lớn nhất mà nó có thể có trong danh sách gốc.

Dữ liệu vào

• Dòng $1$: Số nguyên $N$ ($1\le N\le 50000$).
• $N$ dòng tiếp: Tên bò đã bị xáo trộn (1–20 ký tự thường).

Dữ liệu ra

• $N$ dòng, mỗi dòng gồm hai số nguyên — vị trí nhỏ nhất và lớn nhất của tên thứ $i$ trong danh sách gốc.

Ràng buộc

• $1\le N\le 50000$
• Mỗi tên có độ dài 1–20 ký tự thường.

Ví dụ