Problem: Based on a peculiar incident at basketball practice, Akari came up with the following competitive programming problem!

You are given n points on the plane, no three of which are collinear. The i-th point initially has a label a_i, in such a way that the labels a_1, a_2, ..., a_n form a permutation of 1, 2, ..., n.

You are allowed to modify the labels through the following operation:

  1. Choose two distinct integers i and j between 1 and n. 
  2. Swap the labels of points i and j, and finally 
  3. Draw the segment between points i and j. 



A sequence of operations is valid if after applying all of the operations in the sequence in order, the k-th point ends up having the label k for all k between 1 and n inclusive, and the drawn segments don't intersect each other internally. Formally, if two of the segments intersect, then they must do so at a common endpoint of both segments.

In particular, all drawn segments must be distinct.

Find any valid sequence of operations, or say that none exist. 

Input

The first line contains an integer n (3 ≤ n ≤ 2000) — the number of points.

The i-th of the following n lines contains three integers x_i, y_i, a_i (-10^6 ≤ x_i, y_i ≤ 10^6, 1 ≤ a_i ≤ n), representing that the i-th point has coordinates (x_i, y_i) and initially has label a_i.

It is guaranteed that all points are distinct, no three points are collinear, and the labels a_1, a_2, ..., a_n form a permutation of 1, 2, ..., n.

Output

If it is impossible to perform a valid sequence of operations, print -1.

Otherwise, print an integer k (0 ≤ k ≤ (n(n - 1))/(2)) — the number of operations to perform, followed by k lines, each containing two integers i and j (1 ≤ i, j ≤ n, i≠ j) — the indices of the points chosen for the operation.

Note that you are not required to minimize or maximize the value of k.

If there are multiple possible answers, you may print any of them.

Examples

Input


5
-1 -2 2
3 0 5
1 3 4
4 -3 3
5 2 1


Output


5
1 2
5 3
4 5
1 5
1 3


Input


3
5 4 1
0 0 2
-3 -2 3


Output


0

Note

The following animation showcases the first sample test case. The black numbers represent the indices of the points, while the boxed orange numbers represent their labels.

<image>

In the second test case, all labels are already in their correct positions, so no operations are necessary.

Solution (in CPP):

Solution:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define infL (1LL<<60)
#define inf (1<<30)
#define inf9 (1000000000)
#define MOD 998244353//1000000007
#define EPS 1e-9
#define Gr 9.8
#define PI acos(-1)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REQ(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define readmp(n) for(int i=0,u,v;i<n;i++) {scanf("%d%d",&u,&v); mp[u].push_back(v); mp[v].push_back(u);}
typedef  long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef ll ValType;
template<typename  T> void maxtt(T& t1, T t2) {
    t1=max(t1,t2);
}
template<typename  T> void mintt(T& t1, T t2) {
    t1=min(t1,t2);
}
#define MAX (2135)

bool debug = 0;
int n,m,k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
string direc="RDLU";
const ll MOD2 = (ll)MOD * (ll)MOD;
ll ln, lk, lm;
void etp(bool f = 0) {
    puts(f ?"YES" : "NO");
    exit(0);
}
void addmod(int &x, int y, int mod = MOD){
    x+=y; if (x>=mod) x-=mod;
    if(x<0) x+=mod;
    assert(x>=0 && x<mod);
}
void et(int x=-1) {
    printf("%d\n", x); exit(0);
}
ll fastPow(ll x, ll y, int mod=MOD) {
    ll ans = 1;
    while(y>0) {
        if(y&1) ans = (x * ans)%mod;
        x = x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gcd1(ll x, ll y) {
    return y?gcd1(y,x%y):x;
}

//#include <atcoder/all>
//using mint = atcoder::modint1000000007;

struct Point {
    ValType x, y;
    int id;
    Point() { }
    Point(ValType x, ValType y) : x(x), y(y) { }
    ld abs() const { return hypot(x, y); }
    ld arg() const { return atan2(y, x); }
  
    Point operator*(double o) const { return Point(x * o, y * o); }
    Point operator+(const Point& o) const { return Point(x + o.x, y + o.y); }
    Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
    Point operator/(double o) const { return Point(x / o, y / o); }

    bool operator<(const Point& o) const { return x < o.x - EPS || (x < o.x + EPS && y < o.y - EPS); }
    friend bool operator == (const Point &r1,const Point &r2)
    {return r1.x==r2.x&&r1.y==r2.y;}
    
    Point scale(double o) const { return *this * (o / abs()); }
    Point rotY() const { return Point(-y, x); }
    Point rotX() const { return Point(y, -x); }
    ValType cross(Point b) const {return x*b.y- b.x*y;}
    ValType dot(Point b) const {return x*b.x + y*b.y;}
    ld disToSeg(Point &a, Point &b) {
        return fabs(((*this)-a).cross(b-a) / (b-a).abs());
    }
    pair<ll, ll> getVec() {
        if (x==0) return {0, y>0?1:-1};
        if (y==0) return {x<0?-1:1, 0};
        ll gg = gcd1(::abs(x),::abs(y));
        ll px=x/gg,py=y/gg;
        return {px,py};
    }
    void readin() {
        scanf("%lld%lld", &x, &y);
    }
}pt[MAX];
int cid,c[MAX],p[MAX], f[MAX];
vector<int> cyl[MAX];
vector<pii> Ans;
int ff(int x) {
    return x==f[x] ? f[x] : f[x]=ff(f[x]);
}
bool lik(int x, int y) {
    int fx=ff(x), fy=ff(y);
    if(fx==fy) return 0;
    f[fx]=fy;
    return 1;
}
void fmain(int tid) {
    scanf("%d",&n);
    REQ(i,n) {
        pt[i].readin(); pt[i].id=i;
        scanf("%d", &p[i]);
    }
    REQ(i,n) f[i]=i;
    for(int i=1;i<=n;i++) if(c[i]==0) {
        ++cid;
        for(int x=i;c[x]==0;x=p[x]) {
            c[x]=cid; cyl[cid].push_back(x);
        }
        for(int j=1;j<cyl[cid].size();j++) lik(cyl[cid][0], cyl[cid][j]);
    }
    int R=-1;
    REQ(i,cid) {
        if (cyl[i].size()>1) {
            R=cyl[i][0]; break;
        }
    }
    if(R==-1)et(0);

    vector<pair<ld, int>> vp;
    REQ(i,n) if(i!=R) {
        Point z=pt[i]-pt[R];
        vp.push_back({z.arg(), i});
    }
    sort(vp.begin(), vp.end());
    int N=vp.size();
    REP(i,N) {
        int x=vp[i].second, y=vp[(i+1)%N].second;
        ld tx=vp[i].first, ty=vp[(i+1)%N].first;
        if(tx>ty) {
            ty+=PI*2;
        }
        ld cc=ty-tx;
        if (cc>PI) continue;
        if(lik(x,y)) {
        Ans.push_back({x,y});
        swap(p[x],p[y]);
        }
    }
    while (p[R]!=R) {
        Ans.push_back({p[R], R});
        swap(p[p[R]], p[R]);
    }
    printf("%d\n", Ans.size());
    for(auto p: Ans) printf("%d %d\n",p.first,p.second);
}
int main() {
//    freopen("in21.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    int t=1;
//    init();
//    scanf("%d", &t);
    REQ(i,t) {
        fmain(i);
    }
    return 0;
}