#include#include #include #include #include #include #define sqr(x) (x) * (x)#define M 300005using namespace std;const double inf = 1e20, eps = 1e-3, alpha = acos(-1) / 5, cosa = cos(alpha), sina = sin(alpha);int n, root, ans[M], D,lc[M], rc[M], id[M];double maxx[M][2], minn[M][2], deed[M][2], rn[M];int read() { int nm = 0, f =1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f;}struct C { double d[2], r; int id; bool operator < (C b) const { return d[D] < b.d[D]; } double& operator [](int x) { return d[x]; }} note[M];bool cmp(C a, C b) { return a.r == b.r ? a.id < b.id : a.r > b.r;}void updata(int x) { for(int i = 0; i <= 1; i++) { maxx[x][i] = minn[x][i] = deed[x][i]; maxx[x][i] = max(maxx[x][i], max(maxx[lc[x]][i], maxx[rc[x]][i])); minn[x][i] = min(minn[x][i], min(minn[lc[x]][i], minn[rc[x]][i])); }}int build(int l, int r, int kx) { if(l > r) return 0; int mid = (l + r) >> 1; D = kx; nth_element(note + l, note + mid, note + r + 1); deed[mid][0] = note[mid][0], deed[mid][1] = note[mid][1]; id[mid] = note[mid].id; rn[mid] = note[mid].r; lc[mid] = build(l, mid - 1, kx ^ 1), rc[mid] = build(mid + 1, r, kx ^ 1); updata(mid); return mid;}bool check(int x, C a){ double xn = deed[x][0], yn = deed[x][1], xnn = a[0], ynn = a[1], r1 = rn[x], r2 = a.r; return sqr(xn - xnn) + sqr(yn - ynn) - sqr(r1 + r2)<= eps; }bool cut(int x, C a) { double xn = a[0], yn = a[1], r = a.r + a.r; // 位被选中的圆形大小一定比当前小 依据这个来剪枝 if(xn + r + eps < minn[x][0]) return true; if(yn + r + eps < minn[x][1]) return true; if(xn - r - eps > maxx[x][0]) return true; if(yn - r - eps > maxx[x][1]) return true; return false;}void modify(int x, C a) { if(x == 0) return; if(cut(x, a)) return; if(!ans[id[x]] && check(x, a)) ans[id[x]] = a.id; modify(lc[x], a) ,modify(rc[x], a);}int main() { maxx[0][1] = maxx[0][0] = -inf; minn[0][1] = minn[0][0] = inf; n = read(); for(int i = 1; i <= n; i++) { double x = read(), y = read(), z = read(); note[i] = (C) { x * cosa - y * sina, x * sina + y * cosa, z, i }; } root = build(1, n, 0); sort(note + 1, note + n + 1, cmp); for(int i = 1; i <= n; i++) if(!ans[note[i].id]) modify(root, note[i]); for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0;}