Quân xe

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ừ trái qua phải bắt đầu từ 1. 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$ (với $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^\circ$ 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.

Vào từ file văn bản QUANXE.INP gồm:

• Dòng đầu tiên chứa số nguyên $n$ $(1 \le n \le 10^5)$.
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $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.

Ghi ra file văn bản QUANXE.OUT chứa $n$ dòng, mỗi dòng hai số nguyên là vị trí của quân xe theo trạng thái mới của bàn cờ.

• Có ít nhất $70\%$ số test ứng với $70\%$ số điểm của bài thỏa mãn: $1 \le n \le 10^3$.
• Có $30\%$ số test còn lại ứng với $30\%$ số điểm của bài thỏa mãn: $1 \le n \le 10^5$.