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 comment(linker, "/stack:1000000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#define _CRT_SECURE_NO_WARNINGS
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_map>
# include <unordered_set>
# include <chrono>
 
using namespace std;
 
#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
#define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
#define macro_dispatcher___(macro, nargs) macro ## nargs
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
#define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
#define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
 
#ifdef _MSC_VER
#define PREFETCH(ptr, rw, level) ((void)0)
#else
#define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
#endif
 
#if defined _MSC_VER
#define ASSUME(condition) ((void)0)
#define __restrict
#else
#define ASSUME(condition) ((condition) ? true : (__builtin_unreachable(), false))
#endif
 
#ifdef LOCAL
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#else
#define CURTIME()
#endif
 
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef int itn;
 
template<class T1, class T2, class T3>
struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
template<class T1, class T2, class T3>
bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
template<class T1, class T2, class T3>
bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
#define tri triple<int,int,int>
#define trll triple<ll,ll,ll>
 
#define FI(n) for(int i=0;i<(n);++i)
#define FJ(n) for(int j=0;j<(n);++j)
#define FK(n) for(int k=0;k<(n);++k)
#define FL(n) for(int l=0;l<(n);++l)
#define FQ(n) for(int q=0;q<(n);++q)
#define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
#define all(a) std::begin(a), std::end(a)
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
 
#define sqr(x) ((x) * (x))
#define sqrt(x) sqrt(1.0 * (x))
#define pow(x, n) pow(1.0 * (x), n)
 
#define COMPARE(obj) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b)
#define COMPARE_BY(obj, field) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b) { return a.field < b.field; }

//long double cpu_time() {
//#if defined(_WIN32) || defined(_WIN64)
//    FILETIME creation_ft, exit_ft, kernel_ft, user_ft;
//    GetProcessTimes(GetCurrentProcess(), &creation_ft, &exit_ft, &kernel_ft, &user_ft);
//    auto extract_time = [](const FILETIME& ft) {
//        return 1e-7L * (ft.dwLowDateTime | uint64_t(ft.dwHighDateTime) << 32);
//    };
//    return extract_time(user_ft) + extract_time(kernel_ft);
//#else
//    return (long double) clock() / CLOCKS_PER_SEC;
//#endif
//}
#define checkbit(n, b) (((n) >> (b)) & 1)
#define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
#define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
#define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return(((v+(v>>4))&0xF0F0F0F)*0x1010101)>>24;}
inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
inline int countBits(ll v){return countBits((ull)v); }
inline int countBits(int v){return countBits((uint)v); }
unsigned int reverseBits(uint x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
constexpr ll power(ll x, int p) { return p == 0 ? 1 : (x * power(x, p - 1)); }
template<class T>
inline bool inRange(const T& val, const T& min, const T& max) { return min <= val && val <= max; }
//template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
unsigned long long rdtsc() { unsigned long long ret = 0;
#ifdef __clang__
    return __builtin_readcyclecounter();
#endif
#ifndef _MSC_VER
    asm volatile("rdtsc" : "=A" (ret) : :);
#endif
    return ret; }
// Fast IO ********************************************************************************************************
const int __BS = 4096;
static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
auto c = []() { if (__ir == __er) {std::fill(__bur, __bur + __BS, 0); cin.read(__bur, __BS); __ir = __bur; };};
template<class T = int> T readInt() {
    c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
    bool m = false; if (*__ir == '-') {++__ir; c(); m = true;}
    T r = 0; while (*__ir >= '0' && *__ir <= '9') {r = r * 10 + *__ir - '0', ++__ir; c();}
    ++__ir; return m ? -r : r;
}
string readString() {
    string r; c(); while (*__ir && isspace(*__ir)) {++__ir; c();}
    while (!isspace(*__ir)) {r.push_back(*__ir); ++__ir; c();}
    ++__ir; return r;
}
char readChar() {
    c(); while (*__ir && isspace(*__ir)) {++__ir; c();} return *__ir++;
}
static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
template<class T>
void writeInt(T x, char endc = '\n') {
    if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
    char* s = __iw;
    while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
    char* f = __iw - 1; while (s < f) {swap(*s, *f); ++s; --f;}
    if (__iw > __ew) {cout.write(__buw, __iw - __buw); __iw = __buw;}
    if (endc) { *__iw++ = endc; }
}
template<class T>
void writeStr(const T& str) {
    int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) {cout.write(__buw, __iw - __buw); __iw = __buw; }}
}
struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
static __FL__ __flushVar__;
 
//STL output *****************************************************************************************************
#define TT1 template<class T>
#define TT1T2 template<class T1, class T2>
#define TT1T2T3 template<class T1, class T2, class T3>
#if __cplusplus >= 201703L
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, const Container& x);
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) {
    bool f = 1;
    os << "[";
    while (!v.empty()) {
        if (!f) os << ", ";
        f = 0; os << v.top();
        v.pop();
    }
    return os << "]";
}

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, const Container& x) {
    if constexpr (std::is_pointer<Container>::value) {
        if constexpr (sizeof(*x) == 1) { return os << (const char*)x; } else { return os << (ptrdiff_t)x; }
    } else {
        os << "["; bool f = 1; for(const auto& y : x) { if (!f) os << ", "; f = 0; os << y; } return os << "]";
    }
}

//STL input *****************************************************************************************************
TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
TT1 inline istream& operator >> (istream& os, vector<T>& v) {
    if (v.size()) for (T& t : v) os >> t; else {
        string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
        stringstream ss(s); while (ss >> obj) v.push_back(obj);
    }
    return os;
}
TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
#endif

//Pair magic *****************************************************************************************************
#define PT1T2 pair<T1, T2>
TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
 
#undef TT1
#undef TT1T2
#undef TT1T2T3
 
#define FREIN(FILE) freopen(FILE, "rt", stdin)
#define FREOUT(FILE) freopen(FILE, "wt", stdout)
#ifdef LOCAL
#define BEGIN_PROFILE(idx, name) int profileIdx = idx; profileName[profileIdx] = name; totalTime[profileIdx] -= rdtsc() / 1e3;
#define END_PROFILE totalTime[profileIdx] += rdtsc() / 1e3; totalCount[profileIdx]++;
#else
#define BEGIN_PROFILE(idx, name)
#define END_PROFILE
#endif
 
const int USUAL_MOD = 1000000007;
template<class T> inline void normmod(T &x, T m = USUAL_MOD) { x %= m; if (x < 0) x += m; }
template<class T1, class T2> inline T2 summodfast(T1 x, T1 y, T2 m = USUAL_MOD) { T2 res = x + y; if (res >= m) res -= m; return res; }
template<class T1, class T2, class T3 = int> inline void addmodfast(T1 &x, T2 y, T3 m = USUAL_MOD) { x += y; if (x >= m) x -= m; }
template<class T1, class T2, class T3 = int> inline void submodfast(T1 &x, T2 y, T3 m = USUAL_MOD) { x -= y; if (x < 0) x += m; }
inline ll mulmod(ll x, ll n, ll m){ x %= m; n %= m; ll r = x * n - ll(ld(x)*ld(n) / ld(m)) * m; while (r < 0) r += m; while (r >= m) r -= m; return r; }
inline ll powmod(ll x, ll n, ll m){ ll r = 1; normmod(x, m); while (n){ if (n & 1) r *= x; x *= x; r %= m; x %= m; n /= 2; }return r; }
inline ll powmulmod(ll x, ll n, ll m) { ll res = 1; normmod(x, m); while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n /= 2; } return res; }
template<class T> inline T gcd(T a, T b) { while (b) { T t = a % b; a = b; b = t; } return a; }
template<class T>
T fast_gcd(T u, T v) {
    int shl = 0; while ( u && v && u != v) { T eu = u & 1; u >>= eu ^ 1; T ev = v & 1; v >>= ev ^ 1;
        shl += (~(eu | ev) & 1); T d = u & v & 1 ? (u + v) >> 1 : 0; T dif = (u - v) >> (sizeof(T) * 8 - 1); u -= d & ~dif; v -= d & dif;
    } return std::max(u, v) << shl;
}
template<class T> inline ll norm(const pair<T, T>& p) {
    return p.first * 1LL * p.first + p.second * 1LL * p.second;
}
inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
ll gcdex(ll a, ll b, ll& x, ll& y) {
    if (!a) { x = 0; y = 1; return b; }
    ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
    return d;
}
 
bool isPrime(long long n) {
    if (n <= (1 << 14)) { int x = (int) n; if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
        for (int i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0; return 1; }
    long long s = n - 1; int t = 0; while (s % 2 == 0) { s /= 2; ++t; }
    for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
        long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
        for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
        return false; nextp:;
    } return true;
}
 
// Useful constants
 
//int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431,
#define T9          1000000000
#define T18         1000000000000000000LL
#define INF         1011111111
#define LLINF       1000111000111000111LL
#define mod         1000000007
#define fftmod      998244353
#define EPS         1e-10
#define PI          3.14159265358979323846264
#define link        hiallisubmitted
#define rank        thatsnoteasytask
//*************************************************************************************

int32_t solve();
int32_t main(int argc, char** argv) {
    ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef LOCAL
    FREIN("Data/input.txt");
//    FREOUT("Data/output.txt");
#endif
    return solve();
}
struct DSU {
    int p[202020];
    DSU() {
        FI(202020) p[i] = i;
    }
    int getp(int cur) {
        if (p[cur] != cur) {
            p[cur] = getp(p[cur]);
        }
        return p[cur];
    }
    bool unite(int x, int y) {
        int px = getp(x);
        int py = getp(y);
        if (px == py) {
            return false;
        }
        if (rand() % 2) {
            p[x] = p[px] = py;
        } else {
            p[y] = p[py] = px;
        }
        return true;
    }
};

struct Point {
    int x, y;
    int id;
    int val;
};
vector<Point> points;
bool used[202020];
Point allPoints[202020];
DSU dsu;
int solve() {
    int n;
    cin >> n;
    FI(n) {
        Point p;
        cin >> p.x >> p.y >> p.val;
        p.val--;
        p.id = i;
        allPoints[i] = p;
        if (p.val != i) {
            points.push_back(p);
        }
    }
    if (points.empty()) {
        cout << 0 << endl;
        return 0;
    }
    sort(all(points), [](const Point& a, const Point& b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    });
    for (int i = 1; i < points.size(); ++i) {
        points[i].x -= points[0].x;
        points[i].y -= points[0].y;
    }
    sort(points.begin() + 1, points.end(), [](const Point& a, const Point& b) {
        return a.x * 1LL * b.y < b.x * 1LL * a.y;
    });
    for (auto& p : points) {
        int cur = p.id;
        while (!used[cur]) {
            used[cur] = true;
            cur = allPoints[cur].val;
            dsu.unite(cur, p.id);
        }
    }
    vector<pii> ans;
    int zero = points[0].id;
    for (int i = 1; i + 1 < points.size(); ++i) {
        int a = points[i].id;
        int b = points[i + 1].id;
        if (dsu.unite(a, b)) {
            ans.push_back({a, b});
            swap(allPoints[a].val, allPoints[b].val);
        }
    }
    for (int i = 1; i < points.size(); ++i) {
        int cur = allPoints[zero].val;
        ans.push_back({zero, cur});
        swap(allPoints[zero].val, allPoints[cur].val);
    }
    cout << ans.size() << endl;
    for (auto p : ans) {
        cout << p.first + 1 << ' ' << p.second + 1 << endl;
    }
    return 0;
}