Khi học về xâu kí tự, để luyện tập thêm về nội dung này, Hạo và Huy cùng nhau chơi mộ trò chơi với các xâu kí tự như sau:

• Hạo tạo ra \(n\) xâu kí tự ngẫu nhiên, sau đó, mỗi xâu ban đầu tạo ra một xâu mới bằng cách sao chép một đoạn đầu (hoặc toàn bộ) của xâu đó để tạo thêm được xâu.
• Với xâu mà Hạo tạo ra và được đánh số theo thứ ngẫu nhiên từ \(1\) đến \(2n\), Huy cần đưa ra một phương án để giải thích cách tạo xâu của Hạo.

Yêu cầu

• Cho xâu, hãy chia xâu thành nhóm, mỗi nhóm gồm hai xâu mà xâu này là đoạn đầu (hoặc toàn bộ) của xâu kia.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(n\);
• Tiếp theo là \(2n\) dòng, mỗi dòng là một xâu chỉ gồm các kí tự 'a' đến 'z'.
• Tổng số kí tự trong file không vượt quá \(10^6\).

Dữ liệu ra

• Gồm dòng, mỗi dòng chứa hai số là chỉ số xâu gốc và chỉ số xâu được tạo ra.

Input 1

2
ab
adc
a
adce

Output 1

1 3
4 2