A set of points on a plane is called good, if for any two points at least one of the three conditions is true:

• those two points lie on same horizontal line;
• those two points lie on same vertical line;
• the rectangle, with corners in these two points, contains inside or on its borders at least one point of the set, other than these two. We mean here a rectangle with sides parallel to coordinates' axes, the so-called bounding box of the two points.

You are given a set consisting of n points on a plane. Find any good superset of the given set whose size would not exceed 2·10⁵ points.

Input

The first line contains an integer n (1 ≤ n ≤ 10⁴) — the number of points in the initial set. Next n lines describe the set's points. Each line contains two integers x_i and y_i ( - 10⁹ ≤ x_i, y_i ≤ 10⁹) — a corresponding point's coordinates. It is guaranteed that all the points are different.

Output

Print on the first line the number of points m (n ≤ m ≤ 2·10⁵) in a good superset, print on next m lines the points. The absolute value of the points' coordinates should not exceed 10⁹. Note that you should not minimize m, it is enough to find any good superset of the given set, whose size does not exceed 2·10⁵.

All points in the superset should have integer coordinates.

Example

Input

2 1 1 2 2

Output

3 1 1 2 2 1 2 大致题意：给定一些点，要求添加一些点，使得任意一对点满足三个条件之一即可：1.横坐标相同.2.纵坐标相同.3.两个点围成的矩形内部或边上有其他的点. 分析：构造题，看到平面上分布着一些点，想到了平面上的分治.常见的方法是取中间点为中轴，左右两边分治.关键是两边的答案不好合并.           一开始的想法是枚举位于左边的点再枚举位于右边的点，如果两个点之间没有其它点，就必须在另外两个拐角之一放一个点，这样还要分类讨论，而且枚举的复杂度高，不是很好.在网上看到了其他人的构造方法，非常巧妙：以中间的点的所在的竖线为中轴，其他所有点向中轴投影，投影的点即为要添加的点.这样既满足了矩形内部有点的性质，又使得新添加的点全部在一条直线上，不用再对新添加的点来继续讨论.感觉平面上的分治都和中轴有关，以后这类问题要多往这个方向上想.           最后要去重，点数可能比10w要多，数组要开大一点.

#include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;struct node{    int x,y;}e[100010],ans[1000010],print[1000010];int n,cnt,tot;bool cmp(node a,node b){    if (a.x == b.x)        return a.y < b.y;    return a.x < b.x;}void solve(int l,int r){    if (l == r)        ans[++cnt] = e[l];    if (l >= r)        return;    int mid = (l + r) >> 1;    solve(l,mid - 1);    solve(mid + 1,r);    for (int i = l; i <= r; i++)    {        node temp;        temp.x = e[mid].x;        temp.y = e[i].y;        ans[++cnt] = temp;    }}int main(){    scanf("%d",&n);    for (int i = 1; i <= n; i++)        scanf("%d%d",&e[i].x,&e[i].y);    sort(e + 1,e + 1 + n,cmp);    solve(1,n);    sort(ans + 1,ans + 1 + cnt,cmp);    print[++tot] = ans[1];    for (int i = 2; i <= cnt; i++)        if (ans[i].x != ans[i - 1].x || ans[i].y != ans[i - 1].y)            print[++tot] = ans[i];    printf("%d\n",tot);    for (int i = 1; i <= tot; i++)        printf("%d %d\n",print[i].x,print[i].y);    return 0;}