1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 inline int read()

 5 {

 6     int x=0,f=1;

 7     char ch=getchar();

 8     while(ch<'0'||ch>'9')

 9     {

10         if(ch=='-') f=-1;

11         ch=getchar();

12     }

13     while(ch>='0'&&ch<='9')

14     {

15         x=(x<<1)+(x<<3)+(ch^48);

16         ch=getchar();

17     }

18     return x*f;

19 }

20 int n,m;

21 const int maxn=2e5;

22 struct matrix{

23     int a,b,id;

24 }jx[maxn],aa[maxn],bb[maxn];

25 bool cmp1(matrix a,matrix b)

26 {

27     if(a.b!=b.b)

28     return a.b<b.b;

29     return b.a<b.a;

30 }

31 bool cmp2(matrix a,matrix b)

32 {

33     if(a.a!=b.a)

34     return a.a<b.a;

35     return b.b<b.b;

36 }

37 int tonga[maxn],tongb[maxn];

38 bool vis[maxn];

39 signed main()

40 {

41     int t=read();

42     while(t--)

43     {

44         memset(tonga,0,sizeof(tonga));

45         memset(tongb,0,sizeof(tongb));

46         memset(vis,0,sizeof(vis));

47         n=read(),m=read();

48         for(int i=1;i<=n;i++)

49         {

50             aa[i].a=bb[i].a=jx[i].a=read();

51             tonga[jx[i].a]++;

52             aa[i].b=bb[i].b=jx[i].b=read();

53             tongb[jx[i].b]++;

54             aa[i].id=i,bb[i].id=i;

55         }

56         sort(aa+1,aa+1+n,cmp2);

57         sort(bb+1,bb+1+n,cmp1);

58         for(int i=1;i<=m;i++)

59         tonga[aa[i].a]--,tongb[aa[i].b]--,vis[aa[i].id]=1;

60         int tempa=0,tempb=0,tmp=1,ans=0;

61         while(!tonga[tempa]) tempa++;

62         while(!tongb[tempb]) tempb++;

63         ans=max(ans,tempb*tempa);

64         for(int i=1;i<=m;i++)

65         {

66             if(aa[m-i+1].b<=tempb) continue;

67             vis[aa[m-i+1].id]=0;

68             ++tonga[aa[m-i+1].a];

69             ++tongb[aa[m-i+1].b];

70             if(aa[m-i+1].a<tempa) tempa=aa[m-i+1].a;

71             while(vis[bb[tmp].id]) tmp++;

72             vis[bb[tmp].id]=1,tongb[bb[tmp].b]--,tonga[bb[tmp].a]--;

73             while(!tonga[tempa]) tempa++;

74             while(!tongb[tempb]) tempb++;

75             ans=max(ans,tempb*tempa);

76         }

77         cout<<ans<<endl;

78     }

79 }

  1 #include<bits/stdc++.h>

  2 #define inf 2e9

  3 #define lid id<<1

  4 #define rid id<<1|1

  5 using namespace std;

  6 inline int read()

  7 {

  8     int x=0,f=1;

  9     char ch=getchar();

 10     while(ch<'0'||ch>'9')

 11     {

 12         if(ch=='-') f=-1;

 13         ch=getchar();

 14     }

 15     while(ch>='0'&&ch<='9')

 16     {

 17         x=(x<<1)+(x<<3)+(ch^48);

 18         ch=getchar();

 19     }

 20     return x*f;

 21 }

 22 const int maxn=2e6+1;

 23 struct treap{

 24     int l,r,size,cnt,dat,val;

 25 }a[maxn];

 26 struct seg_tree{

 27     int l,r,root,lazy;

 28 }tr[maxn<<2];

 29 int n,q,type,tot;

 30 struct node{

 31     int to,nxt;

 32 }e[maxn*2];

 33 int head[maxn];

 34 bool flag=1;

 35 int val[maxn];

 36 bool vis[100001];

 37 int w[maxn],num;

 38 int dfn[maxn],size[maxn],son[maxn],fa[maxn],top[maxn];

 39 int dep[maxn],cnt;

 40 int cz[maxn],rr,k;

 41 inline void add(int x,int y)

 42 {

 43     e[++num].to=y;

 44     e[num].nxt=head[x];

 45     head[x]=num;

 46     if(x!=y+1&&y!=x+1) flag=0;

 47     swap(x,y);

 48     e[++num].to=y;

 49     e[num].nxt=head[x];

 50     head[x]=num;

 51 }

 52 inline int New(int val)

 53 {

 54     a[++tot].val=val;

 55     a[tot].dat=rand();

 56     a[tot].cnt=a[tot].size=1;

 57     return tot;

 58 }

 59 inline void pushup(int p)

 60 {

 61     a[p].size=a[a[p].l].size+a[a[p].r].size+1;

 62 }

 63 inline int merge(int x,int y)

 64 {

 65     if(!x||!y)

 66     return x|y;

 67     if(a[x].dat<a[y].dat)

 68     {

 69         a[x].r=merge(a[x].r,y);

 70         pushup(x);

 71         return x;

 72     }

 73     else

 74     {

 75         a[y].l=merge(x,a[y].l);

 76         pushup(y);

 77         return y;

 78     }

 79 }

 80 inline void split(int now,int kk,int &x,int &y)

 81 {

 82     if(!now)

 83     {

 84         x=y=0;

 85         return ;

 86     }

 87     if(kk>=a[now].val)

 88     {

 89         x=now;

 90         split(a[now].r,kk,a[now].r,y);

 91     }

 92     else

 93     {

 94         y=now;

 95         split(a[now].l,kk,x,a[now].l);

 96     }

 97     pushup(now);

 98 }

 99 inline void insert(int &root,int val)

100 {

101     int x,y;

102     split(root,val,x,y);

103     root=merge(merge(x,New(val)),y);

104 }

105 void build(int id,int l,int r)

106 {

107     tr[id].l=l; tr[id].r=r;

108     if(l==r)

109     {

110         tr[id].root=New(w[l]);

111         return ;

112     }

113     for(int j=l;j<=r;j++)

114     insert(tr[id].root,w[j]);

115     int mid=(l+r)>>1;

116     build(lid,l,mid);

117     build(rid,mid+1,r);

118 }

119 inline int pre(int &root,int val)

120 {

121     int x,y,ans;

122     split(root,val-1,x,y);

123     if(!x) return -inf;

124     int kk=x;

125     while(a[kk].r)

126     kk=a[kk].r;

127     ans=a[kk].val;

128     root=merge(x,y);

129     return ans;

130 }

131 inline int nxt(int &root,int val)

132 {

133     int x,y,ans;

134     split(root,val,x,y);

135     if(!y) return inf;

136     int kk=y;

137     while(a[kk].l)

138     kk=a[kk].l;

139     ans=a[kk].val;

140     root=merge(x,y);

141     return ans;

142 }

143 inline int askpre(int id,int l,int r,int d)

144 {

145     if(tr[id].l>=l&&tr[id].r<=r)

146     return pre(tr[id].root,d);

147     int mid=(tr[id].l+tr[id].r)>>1;

148     int ans=-inf;

149     if(l<=mid)

150     ans=max(ans,askpre(lid,l,r,d));

151     if(r>mid)

152     ans=max(ans,askpre(rid,l,r,d));

153     return ans;

154 }

155 inline int asknxt(int id,int l,int r,int d)

156 {

157     if(tr[id].l>=l&&tr[id].r<=r)

158     return nxt(tr[id].root,d);

159     int mid=(tr[id].l+tr[id].r)>>1;

160     int ans=inf;

161     if(l<=mid)

162     ans=min(ans,asknxt(lid,l,r,d));

163     if(r>mid)

164     ans=min(ans,asknxt(rid,l,r,d));

165     return ans;

166 }

167 void dfs1(int x,int f)

168 {

169     size[x]=1;

170     for(int i=head[x];i;i=e[i].nxt)

171     {

172         int y=e[i].to;

173         if(y==f) continue;

174         dep[y]=dep[x]+1;

175         fa[y]=x;

176         dfs1(y,x);

177         size[x]+=size[y];

178         if(size[son[x]]<size[y])

179         son[x]=y;

180     }

181 }

182 void dfs2(int x,int f)

183 {

184     top[x]=f;

185     dfn[x]=++cnt;

186     w[cnt]=val[x];

187     if(!son[x]) return ;

188     dfs2(son[x],f);

189     for(int i=head[x];i;i=e[i].nxt)

190     {

191         int y=e[i].to;

192         if(y!=fa[x]&&y!=son[x])

193         dfs2(y,y);

194     }

195 }

196 inline int treepre(int x,int y,int jb)

197 {

198     int ans=-inf;

199     while(top[x]!=top[y])

200     {

201         if(dep[top[x]]<dep[top[y]])

202         swap(x,y);

203         ans=max(ans,askpre(1,dfn[top[x]],dfn[x],jb));

204         x=fa[top[x]];

205     }

206     if(dep[x]>dep[y])

207     swap(x,y);

208     ans=max(ans,askpre(1,dfn[x],dfn[y],jb));

209     return ans;

210 }

211 inline int treenxt(int x,int y,int jb)

212 {

213     int ans=inf;

214     while(top[x]!=top[y])

215     {

216         if(dep[top[x]]<dep[top[y]])

217         swap(x,y);

218         ans=min(ans,asknxt(1,dfn[top[x]],dfn[x],jb));

219         x=fa[top[x]];

220     }

221     if(dep[x]>dep[y])

222     swap(x,y);

223     ans=min(ans,asknxt(1,dfn[x],dfn[y],jb));

224     return ans;

225 }

226 inline int LCA(int x, int y)

227 {

228         while(top[x]!=top[y])

229         {

230              if(dep[top[x]]<dep[top[y]])

231             swap(x,y);

232             x=fa[top[x]];

233         }

234         return dep[x]<dep[y]?x:y;

235 }

236 inline void dfs3(int x,int goal,int &sum)

237 {

238     if(!x) return ;

239     if(vis[x])  return ;

240     vis[x]=1;

241     sum=min(sum,abs(val[x]-rr));

242     if(x==goal) return ;

243     dfs3(fa[x],goal,sum);

244 }

245 signed main()

246 {

247     //freopen("e7.in","r",stdin);

248     //freopen("out","w",stdout);

249     srand(time(0));

250     n=read(),q=read(),type=read();

251     for(int i=1;i<=n;i++) val[i]=read();

252     for(int i=1;i<n;i++) add(read(),read());

253     dfs1(1,0);

254     dfs2(1,1);

255     if(flag==1)

256     {

257         for(int i=1;i<=q;i++)

258         {

259             memset(vis,0,sizeof(vis));

260             rr=read(),k=read();

261             for(int j=1;j<=k;j++) cz[j]=read();

262             int ans=inf;

263             int lca=cz[1];

264             for(int j=2;j<=k;j++)

265             lca=LCA(lca,cz[j]);

266             for(int j=1;j<=k;j++)

267             dfs3(cz[j],lca,ans);

268             printf("%d\n",ans);

269         }

270         return 0;

271     }

272     else

273     {

274         build(1,1,n);

275         int ans=0;

276         for(int i=1;i<=q;i++)

277         {

278             rr=read(),k=read();

279             for(int j=1;j<=k;j++) cz[j]=((read()-1+type*ans)%n)+1;

280             ans=inf;

281             int lca=cz[1];

282             for(int j=2;j<=k;j++)

283             lca=LCA(lca,cz[j]);

284             for(int j=1,tmp;j<=k;j++)

285             {

286                 tmp=treepre(lca,cz[j],rr+1);

287                 if(ans>abs(tmp-rr)) ans=abs(tmp-rr);

288                 tmp=treenxt(lca,cz[j],rr-1);

289                 if(ans>abs(tmp-rr)) ans=abs(tmp-rr);

290             }

291             printf("%d\n",ans);

292         }

293     }

294 }