Cho một dãy điểm gồm n điểm trên tọa độ tích Đề-Các vuông góc nguyên hai chiều \(A_1(x_1,y_1),A_2(x_2,y_2),...A_n(x_n,y_n)\) sao cho 2 điểm bất kỳ không cùng tung độ hoặc hoành độ.

Bạn hãy lập trình thuật toán sắp xếp nổi bọt nổi từ dưới lên nhưng khi đã sắp được sắp \(\left\lfloor n/2 \right\rfloor \) số điểm theo hoành độ tăng dần rồi thì dừng và xuất ra dãy điểm ở dòng thứ nhất và sau đó sắp xếp dãy mới này nổi bọt từ dưới lên khi sắp được \(\left\lfloor n/2 \right\rfloor \) số điểm theo tung độ giảm dần rồi thì dừng và xuất ra dãy điểm ở hàng thứ 2.

Sắp xếp nổi bọt từ dưới lên

Input

Dòng đầu là số nguyên dương n là số điểm \((5<=n<=100)\)

n dòng tiếp theo mỗi dòng chứa 2 số nguyên có trị tuyệt đối nhỏ hơn \(30000\) và không có bất kỳ hai điểm nào có cùng tung độ hoặc hoành độ

Output

Dòng đầu chứa n điểm sau khi sắp xếp nổi bọt tăng dần theo hoành độ được các điểm từ 1 đến hết thứ \(\left\lfloor n/2 \right\rfloor \) (xem ví dụ)

Dòng thứ hai chứa n điểm sau khi sắp xếp nổi bọt giảm dần theo tung độ được các điểm từ 1 đến hết thứ \(\left\lfloor n/2 \right\rfloor \) (xem ví dụ)

Ví dụ

Input

5
7 5
2 4
0 1
8 3
6 8

Output

(0,1) (2,4) (7,5) (6,8) (8,3) 
(6,8) (7,5) (0,1) (2,4) (8,3)

Giải thích : có 5 điểm ta chỉ sắp \(\left\lfloor 5/2 \right\rfloor =2\) điểm đầu dòng 1 là theo hoành độ tăng dần, dòng hai là theo tung độ giảm dần