Trong một vương quốc toán học, nhà vua tổ chức một cuộc thi để tìm ra những phân số "quyền lực" nhất. Mỗi phân số thứ \(i\) được đại diện bởi một cặp số nguyên dương \((x_i, y_i)\), trong đó \(x_i\) là tử số và \(y_i\) là mẫu số.

Nhiệm vụ của bạn là giúp nhà vua sắp xếp danh sách \(n\) phân số này theo thứ tự giảm dần về giá trị. Trong trường hợp có hai hoặc nhiều phân số có giá trị bằng nhau, phân số nào có tổng tử số và mẫu số (\(x_i + y_i\)) lớn hơn sẽ được ưu tiên đứng trước.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x_i\) và \(y_i\) (\(x_i, y_i \leq 10^9\)) lần lượt là tử số và mẫu số của phân số thứ \(i\).

Output

• In ra \(n\) dòng, mỗi dòng gồm hai số \(x_i\) và \(y_i\) của các phân số sau khi đã được sắp xếp theo quy tắc trên.

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 10^3\) và \(x_i, y_i \leq 10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
1 2
2 4
3 4
1 3

3 4
2 4
1 2
1 3