# 2. 题解

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (50005)
#define MKP make_pair

using namespace std;

typedef pair<int,int> PII;

template <typename _Tp>inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int squ(int a){return a * a;}

int n, ds, D, root, sz, m, k;

priority_queue<PII> pq;

stack<PII> ans;

struct N
{
int d[5], mx[5], mn[5], l, r;
int& operator [] (int a){return d[a];}
bool operator < (N another) const {return d[D] < another[D];}
void print()
{
for (int i = 0; i < ds - 1; i += 1) printf("%d ", d[i]);
printf("%d\n", d[ds-1]);
}
}arr[NS], e[NS], q;

void pup(int a)
{
N& l = e[e[a].l], & r = e[e[a].r];
for (int i = 0; i < ds; i += 1)
{
e[a].mx[i] = e[a].mn[i] = e[a][i];
if (e[a].l)
{
e[a].mx[i] = max(e[a].mx[i], l.mx[i]);
e[a].mn[i] = min(e[a].mn[i], l.mn[i]);
}
if (e[a].r)
{
e[a].mx[i] = max(e[a].mx[i], r.mx[i]);
e[a].mn[i] = min(e[a].mn[i], r.mn[i]);
}
}
}

int dis(N p, int a)
{
int tot = 0;
for (int i = 0; i < ds; i += 1) tot += squ(p[i] - e[a][i]);
return tot;
}

int get_dis(N p, int a)
{
int tot = 0;
for (int i = 0; i < ds; i += 1)
tot += squ(max(e[a].mn[i] - p[i], 0)) + squ(max(p[i] - e[a].mx[i], 0));
return tot;
}

void query(int a = root)
{
if (!a) return;
PII nxt = MKP(dis(q, a), a);
if (pq.size() < k) pq.push(nxt);
else if (nxt < pq.top()) pq.pop(), pq.push(nxt);
int dl = INT_MAX, dr = INT_MAX;
if (e[a].l) dl = get_dis(q, e[a].l);
if (e[a].r) dr = get_dis(q, e[a].r);
if (dl < dr)
{
if (dl < pq.top().first || pq.size() < k) query(e[a].l);
if (dr < pq.top().first || pq.size() < k) query(e[a].r);
}
else
{
if (dr < pq.top().first || pq.size() < k) query(e[a].r);
if (dl < pq.top().first || pq.size() < k) query(e[a].l);
}
}

int Build(int l, int r, int d = 0)
{
if (l > r) return 0;
D = d;
int a = ++sz, mid = (l + r) >> 1;
nth_element(arr + l, arr + mid, arr + r + 1);
e[a] = arr[mid];
e[a].l = Build(l, mid - 1, (d + 1) % ds);
e[a].r = Build(mid + 1, r, (d + 1) % ds);
pup(a); return a;
}

int main (int argc, char const* argv[])
{
while (sz = 0, ~scanf("%d%d", & n, & ds))
{
for (int i = 1; i <= n; i += 1)
for (int j = 0; j < ds; j += 1)
IN(arr[i][j]);
root = Build(1, n), IN(m);
while (m--)
{
for (int i = 0; i < ds; i += 1) IN(q[i]);
IN(k), query();
printf("the closest %d points are:\n", k);
while (!pq.empty()) ans.push(pq.top()), pq.pop();
while (!ans.empty()) e[ans.top().second].print(), ans.pop();
}
}
return 0;
}


3 2
1 1
1 3
3 4
1
3 0
3

已修复，谢谢