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 chọ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 lại và xuất ra dãy điểm ở dòng thứ nhất và sau đó sắp xếp chọn dãy mới này theo tung độ giảm dần đến khi sắp được $\lfloor n/2\rfloor$ số điểm thì dừng và xuất ra dãy điểm ở hàng thứ 2.

Sắp xếp chọ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 chọn 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 chọn 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) (8,3) (6,8) 
(6,8) (7,5) (2,4) (8,3) (0,1)

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