KD tree

#include <bits/stdc++.h>
#define sz(x) (static_cast<int>((x).size()))

using namespace std;

typedef long long ll;
typedef long double ld;

mt19937 rnd(239);

const int N = 312345;

int DIM = 0;

struct Point {
    int x = 0, y = 0, c = 0, ind = 0;

    Point(const Point& other) {
        x = other.x;
        y = other.y;
        c = other.c;
        ind = other.ind;
    }

    Point(int _x = 0, int _y = 0, int _c = 0, int _ind = 0) {
        x = _x;
        y = _y;
        c = _c;
        ind = _ind;
    }

    bool operator<(const Point& other) const {
        if (DIM == 0) {
            return make_pair(x, ind) < make_pair(other.x, other.ind);
        } else {
            return make_pair(y, ind) < make_pair(other.y, other.ind);
        }
    }
};

ll dist(Point a, Point b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

bool cmpx(const Point& a, const Point &b) {
    return make_pair(a.x, a.ind) < make_pair(b.x, b.ind);
}

bool cmpy(const Point& a, const Point &b) {
    return make_pair(a.y, a.ind) < make_pair(b.y, b.ind);
}

const ll INF = 1e18;

struct KDTree
{
    Point tree[4 * N];
    int siz[4 * N];

    void build(vector<Point>& vec, int v, int l, int r, int depth) {
        //cout << v << ' ' << l << ' ' << r << endl;
        siz[v] = max(0, r - l);
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        DIM = (depth % 2);
        //sort(vec.begin() + l, vec.begin() + r);
        nth_element(vec.begin() + l, vec.begin() + mid, vec.begin() + r);
        tree[v] = vec[mid];
        build(vec, 2 * v, l, mid, depth + 1);
        build(vec, 2 * v + 1, mid + 1, r, depth + 1);
    }

    void build(vector<Point>& vec) {
        build(vec, 1, 0, sz(vec), 0);
    }

    void query(Point p, int v, int depth, Point& ans, ll& curdist) {
        ll thisdist = dist(tree[v], p);

        bool go_left = (depth % 2 == 1 ? cmpy : cmpx)(p, tree[v]);
        int first_call = 2 * v + (go_left ? 0 : 1);
        int second_call = 2 * v + (go_left ? 1 : 0);
        if (siz[first_call]) {
            query(p, first_call, depth + 1, ans, curdist);
        }
        bool need_second_son = false;
        if (curdist == INF) {
            if (tree[v].c <= p.c) {
                ans = tree[v];
                curdist = thisdist;
            }
            need_second_son = true;
        }
        else {
            if(make_pair(curdist, ans.ind) > make_pair(thisdist, tree[v].ind) && tree[v].c <= p.c) {
                ans = tree[v];
                curdist = thisdist;
            }
            ll dst = (depth % 2 == 1 ? tree[v].y - p.y : tree[v].x - p.x);
            if (dst * dst < curdist) {
                need_second_son = true;
            }
        }
        if (siz[second_call] && need_second_son) {
            query(p, second_call, depth + 1, ans, curdist);
        }
    }

    Point query(Point p) {
        Point ans;
        ll curdist = INF;
        query(p, 1, 0, ans, curdist);
        return ans;
    }
} myKDTree;

int main()
{
   // freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<Point> vec;
        for (int i = 0; i < n; i++) {
                int x, y, c;
                cin >> x >> y >> c;
                Point p{x, y, c, i};
                vec.push_back(p);
        }
        myKDTree.build(vec);
        for (int i = 0; i < m; i++) {
            int x, y, c;
            cin >> x >> y >> c;
            Point p{x, y, c, -1};
            Point ans = myKDTree.query(p);
            cout << ans.x << ' ' << ans.y << ' ' << ans.c << '\n';
        }
    }
    return 0;
}