#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <memory.h>
#include <cassert>

using namespace std;

const int MAXMIN = 1e9 + 1;
const int MAXBOUND = 1 << 30;
struct point {
    point() {}
    point(int x_, int y_ , int val_) {
        x = x_;
        y = y_;
        val = val_;
    }
    int x , y;
    int val;
};
struct range{
    range() {
        l = -MAXBOUND;
        r = +MAXBOUND;
    };
    range(int l_ , int r_) {
        r = r_;
        l = l_;
    }
    int l;
    int r;
};

struct Node {
    Node(bool xdiv_): pnt(0,0,MAXMIN) {
        xdiv = xdiv_;
        mod = -1;
        min = MAXMIN;
        memset(children,0, sizeof(int) * 2);
    }

    bool xdiv;
    int mod;
    int min;
    int children[2];
    point pnt;
    range dx , dy;
};

bool compx(const point & a , const point & b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool compy(const point & a , const point & b) {
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

long long get_dist2(const point & a , const point & b) {
    long long dx = a.x - b.x;
    long long dy = a.y - b.y;
    return dx * dx + dy * dy;
}

range actual_range(const Node & node ,bool xdiv) {
    return xdiv ?  node.dx : node.dy;
}

int actual_crd(const point & p , bool xdiv) {
    return xdiv ? p.x : p.y;
}

vector<point> points;
int best_id;

class d2_tree {
public:
    vector<Node> nodes;
    void build(vector<point> & pts) {
        nodes.reserve(pts.size() * 2 + 4);
        nodes.push_back(Node(true));
        int ymin = MAXBOUND;
        int ymax = -MAXBOUND;
        for(int i = 0; i < pts.size(); ++i){
            ymin = min(ymin , pts[i].y);
            ymax = max(ymax , pts[i].y);
        }
        build_node(0 , pts.begin() , pts.end() - 1 , true , range(ymin , ymax));
    }

    void dfs(int id , int pnt_id) {
        const Node & cur = nodes[id];
        point pnt = points[pnt_id];
        point bestp = points[best_id];
        long long bestdist = get_dist2(bestp,pnt);
        if(cur.children[0] == 0) {
            if(bestdist > get_dist2(cur.pnt, pnt) || (bestdist == get_dist2(cur.pnt, pnt) && cur.pnt.val < best_id)) {
                if(pnt_id != cur.pnt.val) {
                    best_id = cur.pnt.val;
                }
            }
            return;
        }
        Node & child1 = nodes[cur.children[0]];
        int k = 1;

        if(actual_range(child1, cur.xdiv).r >= actual_crd(pnt, cur.xdiv))  {
            k = 0;
        }

        for(int i = 0; i < 2; ++i){
            bestdist = get_dist2(points[best_id],pnt);
            int j = (i + k)%2;
            Node & child = nodes[cur.children[j]];
            range act_range = actual_range(child, cur.xdiv);
            long long act_crd = actual_crd(pnt, cur.xdiv);
            long long dist = min(abs(act_crd - act_range.r) , abs(act_crd - act_range.l));
            dist = min (dist , min(abs(act_crd + act_range.r) , abs(act_crd + act_range.l)));
            if((act_crd <= act_range.r && act_crd >= act_range.l) || dist*dist <= bestdist) {
                dfs(cur.children[j] , pnt_id);
            }
        }
    }


private:
    void push(Node & cur, int val) {
        if(cur.children[0] == 0) return;

        for(int i = 0; i < 2; ++i) {
            int cid = cur.children[i];
            nodes[cid].min = val;
            nodes[cid].mod = val;
        }
    }

    bool check(point & pt , range  & dx , range & dy) {
        return pt.x <= dx.r && pt.x >= dx.l && pt.y <= dy.r && pt.y >= dy.l;
    }

    bool inside(const Node & cur ,range  & dx , range & dy) {
        return cur.dx.r <= dx.r && cur.dx.l >= dx.l && cur.dy.r <= dy.r && cur.dy.l >= dy.l;
    }
    bool nonintersect(const Node & cur ,range  & dx , range & dy) {

        return cur.dx.l > dx.r || cur.dx.r < dx.l || cur.dy.l > dy.r || cur.dy.r < dy.l;
    }

    int build_node(int id , vector<point>::iterator begin, vector<point>::iterator last, bool xdiv, range second_d) {
        if(last == begin) {
            nodes[id].dx = range(begin->x , begin->x);
            nodes[id].dy = range(begin->y , begin->y);
            nodes[id].min = begin->val;
            nodes[id].pnt = *begin;
        }
        else {
            sort(begin , last + 1 , (xdiv ? compx : compy));

            if(xdiv) {
                nodes[id].dx = range(begin->x , last->x);
                nodes[id].dy = second_d;
            }
            else {
                nodes[id].dx = second_d;
                nodes[id].dy = range(begin->y , last->y);
            }
            int size = (int)(last - begin) + 1;
            vector<point>::iterator mid = begin + size / 2;
            int k = nodes.size();
            for(int i = 0; i < 2; ++i) {
                nodes[id].children[i] = k + i;
                nodes.push_back(!xdiv);
            }
            range next_range = (xdiv ? range(begin->x , (mid-1)->x) : range(begin->y , (mid-1)->y));
            nodes[id].min = min(nodes[id].min, build_node(k, begin , mid - 1, !xdiv, next_range));

            next_range = (xdiv ? range((mid)->x , last->x) : range((mid)->y , last->y));
            nodes[id].min = min(nodes[id].min, build_node(k + 1, mid ,last , !xdiv, next_range));
        }
        return nodes[id].min;
    }

};

void solve() {
    int n;
    cin >> n;
    points.resize(n);
    for(int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        points[i].val = i;
    }

    d2_tree tree;
    vector<point> ptscpy = points;
    tree.build(ptscpy);
    vector<vector<int> > ans(n);

    for(int i = 0; i < n; ++i) {
        best_id = (i == 0 ? 1 : 0);
        tree.dfs(0 , i);
        ans[best_id].push_back(i);

    }
    for(int i = 0; i < n; ++i) {
        cout << i+1 <<": ";
        for(int j = 0; j < ans[i].size(); ++j){
            cout << ans[i][j] + 1 << " ";
        }
        cout << "\n";
    }
}

int main()
{

    freopen("k.in","r", stdin);
    freopen("k.out","w", stdout);

    solve();
    return 0;
}