Trên bàn có một bàn cờ là lưới ô vuông kích thước \(n \times n\). Các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái qua phải. Người ta đặt \(n\) quân xe lên bàn cờ, sao cho mỗi hàng có đúng một quân xe và mỗi cột cũng có đúng một quân xe. Mỗi quân xe được xác định trên bàn cờ có vị trí ở hàng \(x\), cột \(y\) \((1 \le x, y \le n)\). Khi mang bàn cờ này sang bàn khác. bàn cờ bị xoay đi một góc \(90^0\) theo chiều kim đồng hồ.

Yêu cầu:

• Hãy xác định vị trí (hàng, cột) của từng quân xe theo trạng thái mới của bàn cờ và đưa ra các vị trí tìm được theo chiều tăng dần của hàng.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 10^5)\)
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x\) và \(y\) là vị trí hàng \(x\), cột \(y\) của mỗi quân xe trong bàn cờ lúc đầu.

Kết quả:

• Chứa \(n\) dòng, mỗi dòng ghi hai số nguyên là vị trí quân xe theo trạng thái mới của bàn cờ.

Input

5
1 4
2 2
3 3
4 5
5 1

Output

1 1
2 4
3 3
4 5
5 2