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

• An 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 \(n\) xâu nữa.
• Với \(2n\) xâu mà An tạo ra và được đánh số theo thứ tự ngẫu nhiên từ \(1\) đến \(2n\), Bình cần đưa ra một phương án để giải thích cách tạo xâu của An.

Yêu cầu: Cho \(2n\) xâu, hãy chia \(2n\) xâu thành \(n\) nhóm, mỗi nhóm gồm hai xâu mà xâu này là đoạn đầu (tiền tố - prefix) của xâu kia hoặc ngược lại.

Input

• 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.

Output

• Gồm \(n\) dòng, mỗi dòng chứa hai số là chỉ số của hai xâu được ghép vào cùng một nhóm.

Constraints

• Tổng số kí tự trong tất cả các xâu không vượt quá \(10^6\).
• Subtask 1: \(n \le 10\).
• Subtask 2: Không có giới hạn nào thêm.

Example

2
ab
adc
a
adce

1 3
4 2