Có \(n\) hộp quà có dạng hình khối và cùng chiều cao bằng \(1\), hộp quà thứ \(i\) (\(1 \le i \le n\)) có đáy là \(a_i \times b_i\). Người ta muốn xếp \(n\) hộp quà vào một hộp cũng có chiều cao bằng \(1\) và có diện tích đáy càng nhỏ càng tốt. Các cạnh đáy của các hộp quà phải đặt song song hoặc vuông góc với các cạnh đáy của hộp đựng quà.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ \(i\) (\(1 \le i \le n\)) chứa hai số nguyên dương \(a_i,b_i\) (\(a_i,b_i \le 10^6\)).

Dữ liệu đảm bảo tồn tại một hình hộp chữ nhật có diện tích đáy bằng tổng diện tích dáy của các hộp quà và chứa được hết tất cả các hộp quà.

Output

• Dòng đầu tiên gồm hai số nguyên dương \(W,H\) là kích thước đáy hình hộp để chứa \(n\) hộp quà. Quy ước đặt hộp quà trên hệ trục tọa độ với góc trái dưới là \((0,0)\) và tọa độ phải trên là \((W,H)\).
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) (\(1 \le i \le n\)) gồm bốn số là tọa độ phải dưới và phải trên mô tả vị trí đặt hộp quà thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 50\).
• Cách tính điểm: Có \(20\) test, mỗi test \(5.0\) điểm. Gọi diện tích dáy của hình hộp cần dùng do thí sinh tìm được là \(c\), \(q\) là tổng diện tích đáy của các hộp quà, khi đó số điểm bạn đạt được cho mỗi test là \(5.0 \times min\{1,\frac{q^2}{c^2}\}\).

Example

3
1 3
2 2
1 2

3 3
0 2 3 3
1 0 3 2
0 0 1 2