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 $\lfloor n/2\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 $\lfloor n/2\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ứ $\lfloor n/2\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ứ $\lfloor n/2\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 $\lfloor 5/2\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