ACM PTIT 2020 Round 5

Nông dân John (FJ) giữ một dãy thứ tự từ điển của N (1 <= N <= 50,000) con bò của ông ta được dán vào cửa chuồng. Tên của mỗi con bò được thể hiện bởi một chuỗi các chữ cái viết thường có độ dài từ 1 đến 20.

Được biết đến với danh hiệu vua phá rối, cô bò Bessie thay đổi danh sách bằng cách thay đổi thứ tự các chữ cái trong tên các con bò trong danh sách. Hơn nữa, cô ta còn thay đổi kí tự trên tên của các con bò. Bạn được cho danh sách đã được sửa đổi, hãy giúp FJ tính toán rằng, với mỗi tên trong danh sách, tìm ra vị trí cao nhất hoặc thấp nhất mà cái tên đó có thể xuất hiện ở dãy ban đầu.

Input

*Dòng 1: Một số tự nhiên N.

*Dòng 2..1+N: Mỗi dòng chứa một cái tên đã được thay đổi của một con bò.

Output

*Dòng 1..N: Dòng thứ i chứa hai số tự nhiên là vị trí nhỏ nhất và lớn nhất có thể mà tên của con bò thứ i có thể xuất hiện trong danh sách ban đầu.

Example

Input:
4
essieb
a
xzy
elsie

Output:
2 3
1 1
4 4
2 3

Giải thích:
Có 4 con bò với các cái tên như trên.
Chuỗi “a” luôn luôn xuất hiện trước, và chuỗi “xzy” luôn xuất hiện cuối bất kể theo hoán vị nào của nó. Hai chuỗi “essieb” và “elsie” có thể xuất hiện ở vị trí 2 hoặc 3 khi nó phụ thuộc vào thứ tự ban đầu. Ví dụ, “bessie” ở vị trí 2 và “elsie” ở vị trí 3, hoặc “sisbee” ở vị trí 3 và “ilees” ở vị trí 2.