Cho dãy \((A, B)\) gồm \(N\) phần tử là các cặp số nguyên \(A_1, A_2, ..., A_N\) và \(B_1, B_2, ..., B_N\). Dãy \((C, D)\) được gọi là dãy con tăng độ dài \(K\)của dãy \((A, B)\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(D_1 = B_{i_1}, D_2 = B_{i_2}, ..., D_K = B_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\).
• \(D_1 < D_2 < ... < D_K\) nếu \(K \geq 2\).

Yêu cầu: Tìm dãy \((C, D)\) thoả mãn \(K\) lớn nhất có thể, tức là tìm dãy con \((C, D)\) dài nhất.

Input

Gồm \(N + 1\) dòng:

• Dòng thứ nhất gồm số nguyên dương \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên (\(A_i, B_i\)). \((|A_i|, |B_i| \leq 10^9)\).

Output

Gồm \(K+1\) dòng:

• Dòng đầu tiên in ra số \(K\) là độ dài dãy con \((C, D)\) dài nhất.
• \(K\) dòng tiếp theo, dòng thứ \(i\) in ra hai số nguyên \(C_i, D_i\) là dãy có độ dài \(K\) dài nhất.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(25\%\) số điểm): \(N \leq 10^5\), \(|A_i|, |B_i| \leq 10^3\).
• Subtask \(3\) (\(25\%\) số điểm): \(N \leq 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): \(N \leq 5.10^5\).
• Nếu xuất đúng số \(K\) sẽ được \(50\%\) số điểm của test. Nếu xuất thêm đúng dãy \((C, D)\) tương ứng thì sẽ được thêm \(50\%\) số điểm của test.

Example

5
1 5
2 3
4 5
6 8
9 9

4
2 3
4 5
6 8
9 9