记录编号	425132	评测结果	AAAAAAWAAAAAAAAAATTTTTTTT
题目名称	2594.[Keller战纪·正传·妖姬篇][HZOI 2015]Keller非.a.t.e	最终得分	64
用户昵称	rewine	是否通过	未通过
代码语言	C++	运行时间	112.579 s
提交时间	2017-07-14 18:32:47	内存使用	27.02 MiB

//http://blog.sina.cn/dpool/blog/s/blog_6f611c300101bysf.html
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef long double LB;


void read(LL &x) {static char c; static bool flag;for (flag = 0; (c=getchar())<'0'||c>'9'; flag |= c=='-');for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=x*10+c-'0');if(flag) x = -x;}

inline LL F(LL x) {return x*x*x*x;}
#define N 200000 

LL D;
struct Data {
  int l,r; LL t,v[5],ma[5],mi[5];
  bool flag;
  void in() {
    read(t);
    for (int i = 0; i < t; i++) read(v[i]),ma[i] = mi[i] = v[i];
    for (int i = t; i < 5; i++) ma[i] = mi[i] = v[i] = 0;
  }
  bool operator < (const Data &lhs) const {
  	return v[D] < lhs.v[D];   
  }
}t[N],q;

priority_queue<LB> ans;

LL C,n,Q;

LB Dis(const Data &a,const Data &b) {
   LB t = 0;
   for (int i = 0; i < 5; i++) 
     t += F(a.v[i]-b.v[i]);
   return t;
}

void Push(LB v) {
   ans.push(v);
   if(ans.size()>C) ans.pop();
}

void Out() {
	static vector<LB> t;
	t.clear();
	while(ans.size()) {
	   t.push_back(ans.top()); ans.pop();
	}
	for (int i = t.size()-1; i >= 0; i--)
  	  printf("%lld\n",(LL)(t[i]+0.5));
}
///////////

#define L t[o].l
#define R t[o].r
int rt;

inline void up(int o) {
    for (int i = 0; i < 5; i++) {
        t[o].ma[i] = max(t[o].v[i],max(t[L].ma[i],t[R].ma[i]));
        t[o].mi[i] = min(t[o].v[i],min(t[L].mi[i],t[R].mi[i]));
    }
} 
 
void build(int l,int r,int &o,int cas) {
    if(l>r) return; D = cas;
    int &mid = o; mid = (l+r)>>1;
    nth_element(t+l,t+mid,t+r+1);
    cas = (cas+1)%5;
    build(l,mid-1,L,cas); build(mid+1,r,R,cas);
    up(o);
}

inline LL _Val(LL l,LL r,LL m) {
	if(m < l) return F(m-l);
	if(m > r) return F(m-r);
	return 0;
}

LB Mi(const Data &t) {
	LB d = 0;
	for (int i = 0; i < 5; i++) d += _Val(t.mi[i],t.ma[i],q.v[i]);
	return d;
} 
 
void query(int o) {
    if(!o) return;
	LB tt = Dis(t[o],q); Push(tt); 
 	tt = ans.top(); 
    LB miL = Mi(t[L]),miR = Mi(t[R]);
    if(miL < miR) {
        if(miL < tt || ans.size() < C) query(L);
        if(miR < tt || ans.size() < C) query(R);
    } else {
        if(miR < tt || ans.size() < C) query(R);
        if(miL < tt || ans.size() < C) query(L);
    }
}

int main() {
  freopen("Keller_Deal.in","r",stdin);freopen("Keller_Deal.out","w",stdout);
  read(n); read(Q);
  for (int i = 1; i <= n; i++) t[i].in();
  build(1,n,rt,0);
  for (int i = 1; i <= Q; i++) {
    read(q.t); read(C);
    for (int i = 0; i < q.t; i++) read(q.v[i]);
    for (int i = q.t; i < 5; i++) q.v[i] = 0;
    printf("the closest %lld strings' distance are:\n",C);
    //for (int i = 1; i <= n; i++) Push(Dis(q,t[i]));
    query(rt);
    Out(); 
  }
  return 0;
}