Câu lạc bộ quần vợt MatchBall đang tổ chức một tuần lễ quảng cáo để thu hút thành viên mới vào câu lạc bộ. Họ có mời một vài ngôi sao trong làng quần vợt đến chơi một vài trận đấu mang tính chất biểu diễn. Có tất cả \(n\) đấu thủ được mời đánh số từ \(1\) tới \(n\) và mỗi người trong số họ đều cho biết họ muốn chơi bao nhiêu trận. Ban tổ chức muốn tránh sự nhàm chán cho các khán giả nên muốn tổ chức các trận đấu biểu diễn sao cho:

• Mỗi trận đấu gồm đúng hai đấu thủ.
• Đấu thủ nào cũng chơi đúng số trận họ muốn chơi.
• Hai đấu thủ bất kỳ chỉ đấu với nhau không quá một trận.

Yêu cầu: Hãy giúp Ban tổ chức lên lịch thi đấu, biết rằng luôn tồn tại phương án thỏa mãn các yêu cầu trên.

Input

• Dòng 1 chứa số nguyên dương \(n \le 10^5\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số trận mà đấu thủ thứ \(i\) muốn chơi. Biết rằng tổng số trận đấu của giải không vượt quá \(10^5\).

Output

• Ghi ra các dòng, mỗi dòng ghi chỉ số hai đấu thủ trong một trận đấu.

Example

3
1
1
2

1 3
2 3