#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,m;
vector <int> G[MAXN];
int dep[MAXN],siz[MAXN],hson[MAXN],top[MAXN],fa[MAXN];
int rk[MAXN],dfn[MAXN],dcnt,st[MAXN][20],L[MAXN],R[MAXN];
void dfs0(int u,int fz) {
dep[u]=dep[fz]+1,fa[u]=fz,siz[u]=1;
for(int v:G[u]) if(v^fz) {
dfs0(v,u),siz[u]+=siz[v];
if(siz[v]>siz[hson[u]]) hson[u]=v;
}
}
void dfs1(int u,int rt) {
top[u]=rt,L[u]=dfn[u]=++dcnt,st[dcnt][0]=fa[u],rk[dcnt]=u;
if(hson[u]) dfs1(hson[u],rt);
for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) dfs1(v,v);
R[u]=dcnt;
}
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int bit(int x) { return 1<<x; }
int LCA(int x,int y) {
if(x==y) return x;
int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);
return cmp(st[l][k],st[r-bit(k)+1][k]);
}
ll ans[MAXN];
namespace dfz {
vector <array<int,2>> qy[MAXN];
bool vis[MAXN];
int cur[MAXN],siz[MAXN],d[MAXN],f[MAXN];
void calc(vector<int>&z,int op) {
int K=0;
for(int u:z) K=max(K,d[u]),++f[d[u]];
for(int i=1;i<=K;++i) f[i]+=f[i-1];
for(int u:z) for(auto it:qy[u]) if(it[0]>=d[u]) {
ans[it[1]]+=f[min(K,it[0]-d[u])]*op;
}
memset(f,0,sizeof(int)*(K+1));
}
void solve(int u) {
vector <int> wo{u}; d[u]=0;
for(int v:G[u]) if(!vis[v]) {
vector <int> wi;
function<void(int,int)> dfs3=[&](int x,int fz) {
wi.push_back(x),wo.push_back(x);
d[x]=d[fz]+1,siz[x]=1;
for(int y:G[x]) if(y!=fz&&!vis[y]) {
dfs3(y,x),siz[x]+=siz[y];
}
};
dfs3(v,u),calc(wi,-1);
}
calc(wo,1);
}
void dfs2(int u) {
vis[u]=true,solve(u);
for(int v:G[u]) if(!vis[v]) {
int rt=0;
function<void(int,int)> dfs4=[&](int x,int fz) {
cur[x]=siz[v]-siz[x];
for(int y:G[x]) if(y!=fz&&!vis[y]) {
dfs4(y,x),cur[x]=max(cur[x],siz[y]);
}
if(!rt||cur[rt]>cur[x]) rt=x;
};
dfs4(v,u),dfs2(rt);
}
}
}
vector <array<int,3>> qf[MAXN],qg[MAXN];
void F(int u,int d,int i,int c) {
if(!u||d<0) return ;
ans[i]+=c*siz[u];
if(dep[u]+d>=n) return ;
qf[L[u]-1].push_back({dep[u]+d+1,i,c});
qf[R[u]].push_back({dep[u]+d+1,i,-c});
}
void chi(int x,int rt,int d,int i) {
ans[i]+=dep[x]-dep[rt]+1;
F(hson[x],d-1,i,1);
for(;top[x]^top[rt];x=fa[top[x]]) {
F(top[x],d-1,i,-1);
F(hson[fa[top[x]]],d-1,i,1);
}
}
ll f[MAXN],g[MAXN];
void dfs5(int u,ll S) {
for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) {
S+=siz[v];
for(int i=L[v];i<=R[v];++i) g[dep[rk[i]]-dep[u]]+=siz[rk[i]];
}
for(auto it:qg[u]) {
ans[it[1]]+=it[2]*(S-g[it[0]+1]);
}
for(int v:G[u]) if(v!=fa[u]) dfs5(v,S);
for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) {
S-=siz[v];
for(int i=L[v];i<=R[v];++i) g[dep[rk[i]]-dep[u]]-=siz[rk[i]];
}
}
signed main() {
// freopen("future.in","r",stdin);
// freopen("future.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n;
for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
dfs0(1,0),dfs1(1,1);
for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
}
cin>>m;
for(int i=1,u,v,d;i<=m;++i) {
cin>>u>>v>>d;
int w=LCA(u,v);
F(w,d,i,-2),chi(u,w,d,i),chi(v,w,d,i);
qg[u].push_back({d,i,1});
qg[v].push_back({d,i,1});
qg[fa[w]].push_back({d,i,-2});
dfz::qy[w].push_back({d,i});
}
dfz::dfs2(1);
for(int i=1;i<=n;++i) {
int u=rk[i];
f[dep[u]]+=siz[u];
for(auto it:qf[i]) ans[it[1]]+=it[2]*f[it[0]];
}
dfs5(1,0);
for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";
return 0;
}
/*#include<bits/stdc++.h>
using namespace std;
typedef vector<int> ve;
typedef pair<int,int> pr;
const int inf=1e9,N=100000;
int a[N+5],mus[N+5],pl[N+5],n,f[N+5][2],g[N+5][2],ind[N+5],leadL[N+5],leadR[N+5];
int pos[N+5],D,id[N+5],nd[N+5],dif[N+5],fr[N+5][2],gr[N+5][2],useful[N+5],Pi[N+5];
int has[N+5],pathpre[N+5],pathnxt[N+5],hasdonePQ[N+5];
vector<int> G[N+5],v[N+5];
void updf(int i,int j,int v,int t){
if(v>f[i][j])f[i][j]=v,fr[i][j]=t;
}
void updg(int i,int j,int v,int t){
if(v>g[i][j])g[i][j]=v,gr[i][j]=t;
}
void Add(int x,int y,bool to=1){
if(!to)swap(x,y);
G[x].push_back(y),ind[y]++;
//cout<<"Adding:"<<x<<' '<<y<<'\n';
}
void Clear(){
for(int i=0;i<=n;i++){
useful[i]=has[i]=pathpre[i]=pathnxt[i]=leadL[i]=leadR[i]=mus[i]=ind[i]=0;
hasdonePQ[i]=0;
G[i].clear(),v[i].clear();
}
}
void Toposort(){
queue<int> q;
for(int i=1;i<=n;i++){
if(!ind[i])q.push(i);
pl[i]=0;
}
int tot=0;
while(!q.empty()){
int x=q.front();
q.pop();
pl[x]=++tot;
for(int y:G[x]){
if(!--ind[y]){
q.push(y);
}
}
}
assert(tot==n);
}
int ishi[N+5];
void norm(int x){
if(leadL[x]==x)leadL[x]++;
if(leadR[x]==x)leadR[x]--;
}
int m=0;
void Construct(int _i,int _j,int P,int Q){
//cout<<"Constructing:"<<_i<<' '<<_j<<' '<<pos[P]<<' '<<pos[Q]<<' '<<m<<'\n';
//先把要填的地方填了。
//如果需要的话 优先填最开始
P=id[P],Q=id[Q];
int x=P,y=_i,rem=D-m;
vector<pr> LR1,LR2;
while(x>=1){
if(y==0||y==2)leadL[pos[x]]=pos[x]-1,leadR[pos[x]]=pos[x]+nd[x]-1;
if(y==1||y==3)leadL[pos[x]]=pos[x]+1,leadR[pos[x]]=pos[x]+nd[x];
if(x==1)break;
if(fr[pos[x]][y]<2){
int L=pos[x-1]+1+(fr[pos[x]][y]==1&&nd[x-1]%2==1)+nd[x-1]/2*2;
int R=pos[x]-1-(y==0&&nd[x]%2==1);
if(nd[x-1]>=2||(x==2&&nd[x-1]==1))L--;
if(L<R)LR1.push_back(pr(L,R));
}
y=fr[pos[x]][y]%2,x--;
}
x=Q,y=_j;
while(x<=m){
if(y==0||y==2)leadL[pos[x]]=pos[x]-nd[x],leadR[pos[x]]=pos[x]-1;
if(y==1||y==3)leadL[pos[x]]=pos[x]-nd[x]+1,leadR[pos[x]]=pos[x]+1;
if(x==m)break;
if(gr[pos[x]][y]<2){
int L=pos[x]+1+(y==1&&nd[x]%2==1);
int R=pos[x+1]-1-(gr[pos[x]][y]==0&&nd[x+1]%2==1)-nd[x+1]/2*2;
//cout<<"AT:"<<L<<' '<<R<<' '<<gr[x][y]<<'\n';
if(nd[x+1]>=2||(x==m-1&&nd[x+1]==1))R++;
//cout<<"AT2:"<<L<<' '<<R<<'\n';
if(L<R)LR2.push_back(pr(L,R));
}
y=gr[pos[x]][y]%2,x++;
}
//cout<<"DONE1"<<'\n';
//cout<<leadL[5]<<' '<<leadR[5]<<'\n';
if(2<=P&&a[pos[2]]==D-2){
int x=LR1.back().first+1;
mus[x]=1,rem--;
leadL[x]=leadR[x]=x-1,LR1.back().first+=2;
}
if(3<=P&&a[pos[3]]==D-2&&a[pos[2]]==D-1&&pos[2]!=pos[3]-1){
for(auto &[l,r]:LR1){
if(l+1<=r&&l>pos[2]&&r<pos[3]){
mus[l]=1,rem--,leadL[l]=leadR[l]=l+1;
l+=2;
}
}
}
for(int k=3,i=(int(LR1.size()))-1;k<=P;k++){
if(a[pos[k]]!=D-2||a[pos[k-1]]<=D)continue;
bool ok=0;
while(i>=0){
int &l=LR1[i].first,&r=LR1[i].second;
if(!(l+1<=r)||!(pos[k-1]<l&&r<pos[k])){
i--;
continue;
}
mus[l+1]=1,leadL[l]=leadR[l]=l-1,l+=2,rem--;
ok=1;
break;
}
assert(ok);
}
for(int k=m-2,i=(int(LR2.size()))-1;k>=Q;k--){
if(a[pos[k]]!=D-2||a[pos[k+1]]<=D)continue;
//cout<<"AA:"<<k<<' '<<pos[k]<<' '<<pos[k+1]<<'\n';
bool ok=0;
while(i>=0){
int &l=LR2[i].first,&r=LR2[i].second;
// cout<<"ILR:"<<i<<' '<<l<<' '<<r<<'\n';
if(!(l+1<=r)||!(pos[k]<l&&r<pos[k+1])){
i--;
continue;
}
mus[r-1]=1,leadL[r]=leadR[r]=r+1,r-=2,rem--;
ok=1;
break;
}
assert(ok);
}
if(Q<=m-1&&a[pos[m-1]]==D-2){
int x=LR2.back().second-1;
mus[x]=1,rem--;
leadL[x]=leadR[x]=x+1,LR2.back().second-=2;
}
if(Q<=m-2&&a[pos[m-2]]==D-2&&a[pos[m-1]]==D-1&&pos[m-2]!=pos[m-1]-1){
for(auto &[l,r]:LR2){
if(l+1<=r&&l>pos[m-2]&&r<pos[m-1]){
mus[r]=1,rem--,leadL[r]=leadR[r]=r-1;
r-=2;
}
}
}
assert(rem>=0);
//cout<<"DONE2"<<'\n';
for(auto [l,r]:LR1){
for(int i=l+1;i<=r&&rem;i+=2){
mus[i]=1,rem--;
leadL[i]=leadR[i]=i-1;
}
}
for(auto [l,r]:LR2){
for(int i=r-1;i>=l&&rem;i-=2){
mus[i]=1,rem--;
leadL[i]=leadR[i]=i+1;
}
}
P=pos[P],Q=pos[Q];
//cout<<"MUS:";
//for(int i=1;i<=n;i++){
// cout<<mus[i]<<' ';
//}
//puts("");
for(int i=1;i<=n;i++)if(mus[i])nd[i]=max(a[i]-(D-1),0);else nd[i]=0;
for(int i=2;i<=P;i++){
if(!mus[i])continue;
int j=i-1;
while(!mus[j])j--;
if(nd[j]>=2||(nd[j]==1&&j==1&&i==3)){
norm(i);
leadL[i]+=nd[i]%2,nd[i]-=nd[i]%2,has[i]=1;
norm(i);
}
}
for(int i=Q;i<n;i++){
if(!mus[i])continue;
int j=i+1;
while(!mus[j])j++;
//cout<<"IIIIIIIIIIIIIIIIII:"<<i<<' '<<nd[i]<<' '<<leadL[i]<<'\n';
if(nd[j]>=2||(nd[j]>=1&&j==n&&i==n-2)){
norm(i);
leadR[i]-=nd[i]%2,nd[i]-=nd[i]%2,has[i]=1;
norm(i);
}
}
//接下来开始建图了。
vector<int> path;
for(int i=1,lst=0;i<=n;i++){
if(!mus[i])continue;
pathpre[i]=lst,pathnxt[lst]=i,lst=i;
useful[i]=1,path.push_back(i);
}
pathnxt[0]=0;
assert(pathnxt[path.back()]==0);
assert(pathnxt[0]==0);
while(leadL[P]>P+1)leadL[P]--,leadR[P]--;
while(leadR[Q]<Q-1)leadL[Q]++,leadR[Q]++;
if(nd[P]>=2&&nd[Q]>=2){
hasdonePQ[P]=1;
hasdonePQ[Q]=1;
for(int j=leadL[P];j<=leadR[P];j++){
useful[j]=1;
if(j!=P)v[P].push_back(j);
}
for(int j=leadL[Q];j<=leadR[Q];j++){
useful[j]=1;
if(j!=Q)v[Q].push_back(j);
}
assert(v[P].size()>=2&&v[Q].size()>=2);
int x=v[P][v[P].size()-2];
int y=v[Q][1];
v[P][v[P].size()-1]=y,v[Q][0]=x;
/*int dii=leadR[Q]-leadL[Q];
leadL[Q]=leadR[P]-1;
leadR[Q]=leadL[Q]+dii;*/
}
//下面没有 leadl leadr 的事了
//cout<<"LEAD[l,r]:\n";
//for(int i=1;i<=n;i++){
// cout<<leadL[i]<<' '<<leadR[i]<<'\n';
//}//
//puts("");
//cout<<v[1].size()<<'\n';
for(int i=1;i<=n;i++){
if(hasdonePQ[i])continue;
for(int j=leadL[i];j<=leadR[i];j++){
useful[j]=1;
if(j!=i)v[i].push_back(j);
}
}
for(int i=1;i<=n;i++){
if(!mus[i])continue;
if(i<=P&&has[i]){
if(v[pathpre[i]].size()>=2)v[i].insert(v[i].begin(),v[pathpre[i]][v[pathpre[i]].size()-2]);
else v[i].insert(v[i].begin(),v[pathpre[i]][0]);
}
if(i>=Q&&has[i]){
if(v[pathnxt[i]].size()>=2)v[i].push_back(v[pathnxt[i]][1]);
else v[i].push_back(v[pathnxt[i]][0]);
}
//cout<<"V:"<<i<<' '<<v[i].size()<<' '<<has[i]<<'\n';
//for(int j:v[i])cout<<j<<' ';
//puts("");
}
//P=1 Q=n
int posP=0;
for(int i=0;i<path.size();i++){
if(path[i]==P){
posP=i;
for(int j=i-2;j>=0;j-=2)Add(path[j+2],path[j]);
for(int j=i-1;j>=0;j-=2)Add(path[j],path[j+2]);
for(int j=i+3;j<path.size();j+=2)Add(path[j],path[j-2]);
for(int j=i+2;j<path.size();j+=2)Add(path[j-2],path[j]);
for(int j=0;j+1<path.size();j++){
if(j%2==i%2){
Add(path[j],path[j+1]);
for(int k=path[j]+1;k<path[j+1];k++){
Add(path[j],k),Add(k,path[j+1]);
}
}
else {
Add(path[j+1],path[j]);
for(int k=path[j]+1;k<path[j+1];k++){
Add(k,path[j]),Add(path[j+1],k);
}
}
}
break;
}
}
for(int i=0;i<path.size();i++)ishi[path[i]]=Pi[path[i]]=(i%2!=posP%2);
int posQ=posP+1;
//cout<<"D1:"<<D<<'\n';
for(int i=0;i<path.size();i++){
if(a[path[i]]==D-2)continue;
vector<int> my=v[path[i]];
if(i)my.insert(my.begin(),path[i-1]);
if(i>1)my.insert(my.begin(),path[i-2]);
if(i+1<path.size())my.push_back(path[i+1]);
if(i+2<path.size())my.push_back(path[i+2]);
if(i>1||(i==1&&path[i]!=2)){
for(int j=1;j<my.size();j++)ishi[my[j]]=1-ishi[my[j-1]];
}
else {
for(int j=((int)my.size())-2;j>=0;j--)ishi[my[j]]=1-ishi[my[j+1]];
}
//cout<<"X:"<<path[i]<<' '<<ishi[2]<<' '<<ishi[1]<<'\n';
for(int j=0;j+1<my.size();j++){
if(ishi[my[j]]){
for(int k=my[j]+1;k<my[j+1];k++){
if(k!=path[i])Add(k,my[j]),Add(my[j+1],k);
}
Add(my[j+1],my[j]);
}
else {
for(int k=my[j]+1;k<my[j+1];k++){
if(k!=path[i])Add(my[j],k),Add(k,my[j+1]);
}
Add(my[j],my[j+1]);
}
}
if(i<posP||i>posQ){
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]])Add(my[j],my[j+2],i<posP);
else Add(my[j+2],my[j],i<posP);
}
}
else if(i==posP){
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]])Add(my[j],my[j+2]);
else if(my[j+2]<Q)Add(my[j+2],my[j]);//如果大于 Q，我们不关心！
}
}
else {
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]]){
if(my[j]>P)Add(my[j+2],my[j]);
}
else Add(my[j],my[j+2]);
}
}
for(int j=0;j<my.size();j++)if(mus[j])ishi[j]=Pi[j];
}
//cout<<"D:"<<D<<'\n';
//特殊处理D-2
for(int i=P;i>=1;i=pathpre[pathpre[i]]){
if(a[i]==D-2&&pathpre[pathpre[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(pathpre[pathpre[i]],j),Add(j,pathnxt[i]);
}
}
}
//cout<<"DD\n";
for(int i=pathpre[P];i>=1;i=pathpre[pathpre[i]]){
if(a[i]==D-2&&pathpre[pathpre[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(j,pathpre[pathpre[i]]),Add(pathnxt[i],j);
}
}
}
//cout<<"DD\n";
for(int i=Q;i<=n&&i;i=pathnxt[pathnxt[i]]){
if(a[i]==D-2&&pathnxt[pathnxt[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(pathpre[i],j),Add(j,pathnxt[pathnxt[i]]);
}
}
}
//cout<<"DD\n";
for(int i=pathnxt[Q];i<=n&&i;i=pathnxt[pathnxt[i]]){
if(a[i]==D-2&&pathnxt[pathnxt[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(j,pathpre[i]),Add(pathnxt[pathnxt[i]],j);
}
}
}
//cout<<"DD\n";
//大斜杠，是不是其实不用管？
//for(int i=1;i<=n;i++)cout<<"IN USEFUL:"<<i<<' '<<ind[i]<<' '<<useful[i]<<'\n';
Toposort();
Clear();
}
int premus[N+5],sufmus[N+5];
void Redo(){
m=0;
for(int i=1;i<=n;i++)
if(mus[i]){
pos[++m]=i,id[i]=m,dif[m]=pos[m]-pos[m-1]-1;
nd[m]=max(a[i]-(D-1),0);
}
}
bool Check(int P,int Q){
if(D>=4&&a[Q]==D-1&&!(Q==n-1||Q==n))return 0;
if(D>=4&&a[P]==D-1&&!(P==1||P==2))return 0;
if(D==3&&a[2]==2&&P==1&&Q==2)return 0;
if(D==3&&a[n-1]==2&&P==n-1&&Q==n)return 0;
if(m>D)return 0;
if(premus[P]+sufmus[Q]+m+(!mus[P])+(!mus[Q])>D)return 0;
//cout<<"UU"<<'\n';
int ndP=max(a[P]-(D-1),0);
int ndQ=max(a[Q]-(D-1),0);
//cout<<"PQD: "<<P<<' '<<Q<<' '<<D<<'\n';
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int s=m+f[P][i]+g[Q][j]+(!mus[P])+(!mus[Q]);
//if(P==1&&Q==3)cout<<i<<' '<<j<<' '<<f[P][i]<<' '<<g[Q][j]<<' '<<s<<' '<<D<<'\n';
if(s<D)continue;
int rP=(i==1)*(ndP%2)+ndP/2*2,lQ=(j==0)*(ndQ%2)+ndQ/2*2;
//cout<<"IJ:"<<i<<' '<<j<<' '<<rP<<' '<<lQ<<'\n';
if(rP<=1||lQ<=1){
if(rP==1&&lQ==1&&Q-P-1==1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
if(rP+lQ<=Q-P-1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
}
else {
if(rP+lQ-2<=Q-P-1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
}
}
}
return 0;
}
//f,g,fr,gr,premus,sufmus 都是位置(pos)上的
int Transf(int _i,int lstpos,int curpos,int dif,int lstnd,int curnd,int musnd){
int w=dif-lstnd/2*2;
int save=((lstnd>=2)||(_i==2&&lstnd==1));
int cur=0;
if(_i==2&&a[curpos]==D-2){
musnd++,cur=1;
}
else if(_i==3&&a[curpos]==D-2&&a[lstpos]==D-1&&lstpos!=curpos-1){
musnd++,cur=1;
}
else if(_i>=3&&a[curpos]==D-2&&a[lstpos]>D){
musnd++,cur=1;
}
for(int j=0;j<2;j++){
if(lstnd%2==0&&j==0)continue;
for(int k=0;k<2;k++){
if(curnd%2==0&&k==0)continue;
int nw=w-(j==1&&lstnd%2==1)-(k==0&&curnd%2==1);
if(nw>=0){
if((nw+save)/2>=cur)updf(curpos,k,f[lstpos][j]+(nw+save)/2,j);
}
if(k==0&&save&&!cur){
nw+=(curnd%2==1);//不需要了，但也不能放新东西
if(nw>=0){
updf(curpos,k,f[lstpos][j],j+2);
}
}
}
}
return musnd;
}
int Transg(int _i,int lstpos,int curpos,int dif,int lstnd,int curnd,int musnd){
int w=dif-lstnd/2*2;
int save=(lstnd>=2||(_i==m-1&&lstnd==1));
int cur=0;
if(_i==m-1&&a[curpos]==D-2){
musnd++,cur=1;
}
else if(_i==m-2&&a[curpos]==D-2&&a[lstpos]==D-1&&lstpos!=curpos+1){
musnd++,cur=1;
}
else if(_i<=m-2&&a[curpos]==D-2&&a[lstpos]>D){
musnd++,cur=1;
}
for(int j=0;j<2;j++){
if(lstnd%2==0&&j==1)continue;
for(int k=0;k<2;k++){
if(curnd%2==0&&k==1)continue;
int nw=w-(j==0&&lstnd%2==1)-(k==1&&curnd%2==1);
if(nw>=0){
if((nw+save)/2>=cur)updg(curpos,k,g[lstpos][j]+(nw+save)/2,j);
}
if(k==1&&save&&!cur){
nw+=(curnd%2==1);
if(nw>=0){
updg(curpos,k,g[lstpos][j],j+2);
}
}
}
}
return musnd;
}
bool Try(int d){
D=d;
for(int i=1;i<=n;i++)pl[i]=0,mus[i]=0;
for(int i=1;i<=n;i++)
if(i==1||i==n||a[i]!=D){
mus[i]=1;
if(max(a[i]-(D-1),0)%2==0&&i!=2&&i!=n&&i!=n-1&&i!=1&&a[i]!=D-2)return 0;
}
if(a[n]==D-1)mus[n-1]=1;
if(a[1]==D-1)mus[2]=1;
m=0;
for(int i=1;i<=n;i++)
if(mus[i]){
pos[++m]=i,id[i]=m,dif[m]=pos[m]-pos[m-1]-1;
nd[m]=max(a[i]-(D-1),0);
}
if(m>D)return 0;
for(int i=0;i<=n;i++){
for(int j=0;j<2;j++)f[i][j]=g[i][j]=-inf;
premus[i]=sufmus[i]=0;
}
f[1][1]=0;
int musnd=0;
for(int i=2;i<=m;i++){
for(int j=pos[i-1]+1;j<pos[i];j++){
premus[j]=Transf(i,pos[i-1],j,j-pos[i-1]-1,nd[i-1],1,musnd);
}
premus[pos[i]]=musnd=Transf(i,pos[i-1],pos[i],pos[i]-pos[i-1]-1,nd[i-1],nd[i],musnd);
}
g[n][0]=0,musnd=0;
for(int i=m-1;i>=1;i--){
for(int j=pos[i]+1;j<pos[i+1];j++){
sufmus[j]=Transg(i,pos[i+1],j,pos[i+1]-j-1,nd[i+1],1,musnd);
}
sufmus[pos[i]]=musnd=Transg(i,pos[i+1],pos[i],pos[i+1]-pos[i]-1,nd[i+1],nd[i],musnd);
}
for(int i=1,j;i<n;i=j){
j=i+1;
while(!mus[j])j++;
//cout<<"C:"<<i<<' '<<j<<'\n';
if(Check(i,j))return 1;
for(int p=i+1;p<j;p++)if(Check(i,p)||Check(p,j))return 1;
for(int p=i+1;p<j;p++)for(int q=p+1;q<j&&q-p<=2;q++)if(Check(p,q))return 1;
}
return 0;
}
int Recover(ve _a){
for(int i=1;i<=n;i++)a[i]=_a[i-1]+1;
int mne=*min_element(a+1,a+n+1);
for(int i=mne;i<=mne+2;i++){
if(i<2||i>n)continue;
if(Try(i))return i;
}
assert(0);
return 0;
}
int S;
void Solve(){
scanf("%d",&n);
vector<int> vec(n);
for(int i=0;i<n;i++)scanf("%d",&vec[i]);
if(S==5)for(int i=0;i<=n;i++)scanf("%*s");
if(S==6)scanf("%*s");
assert(Recover(vec));
for(int i=1;i<=n;i++)cout<<pl[i]<<' ';
puts("");
}
int main(){
int t;
scanf("%d%d",&S,&t);
while(t--)Solve();
}#include<bits/stdc++.h>
using namespace std;
typedef vector<int> ve;
typedef pair<int,int> pr;
const int inf=1e9,N=100000;
int a[N+5],mus[N+5],pl[N+5],n,f[N+5][2],g[N+5][2],ind[N+5],leadL[N+5],leadR[N+5];
int pos[N+5],D,id[N+5],nd[N+5],dif[N+5],fr[N+5][2],gr[N+5][2],useful[N+5],Pi[N+5];
int has[N+5],pathpre[N+5],pathnxt[N+5],hasdonePQ[N+5];
vector<int> G[N+5],v[N+5];
void updf(int i,int j,int v,int t){
if(v>f[i][j])f[i][j]=v,fr[i][j]=t;
}
void updg(int i,int j,int v,int t){
if(v>g[i][j])g[i][j]=v,gr[i][j]=t;
}
void Add(int x,int y,bool to=1){
if(!to)swap(x,y);
G[x].push_back(y),ind[y]++;
//cout<<"Adding:"<<x<<' '<<y<<'\n';
}
void Clear(){
for(int i=0;i<=n;i++){
useful[i]=has[i]=pathpre[i]=pathnxt[i]=leadL[i]=leadR[i]=mus[i]=ind[i]=0;
hasdonePQ[i]=0;
G[i].clear(),v[i].clear();
}
}
void Toposort(){
queue<int> q;
for(int i=1;i<=n;i++){
if(!ind[i])q.push(i);
pl[i]=0;
}
int tot=0;
while(!q.empty()){
int x=q.front();
q.pop();
pl[x]=++tot;
for(int y:G[x]){
if(!--ind[y]){
q.push(y);
}
}
}
assert(tot==n);
}
int ishi[N+5];
void norm(int x){
if(leadL[x]==x)leadL[x]++;
if(leadR[x]==x)leadR[x]--;
}
int m=0;
void Construct(int _i,int _j,int P,int Q){
//cout<<"Constructing:"<<_i<<' '<<_j<<' '<<pos[P]<<' '<<pos[Q]<<' '<<m<<'\n';
//先把要填的地方填了。
//如果需要的话 优先填最开始
P=id[P],Q=id[Q];
int x=P,y=_i,rem=D-m;
vector<pr> LR1,LR2;
while(x>=1){
if(y==0||y==2)leadL[pos[x]]=pos[x]-1,leadR[pos[x]]=pos[x]+nd[x]-1;
if(y==1||y==3)leadL[pos[x]]=pos[x]+1,leadR[pos[x]]=pos[x]+nd[x];
if(x==1)break;
if(fr[pos[x]][y]<2){
int L=pos[x-1]+1+(fr[pos[x]][y]==1&&nd[x-1]%2==1)+nd[x-1]/2*2;
int R=pos[x]-1-(y==0&&nd[x]%2==1);
if(nd[x-1]>=2||(x==2&&nd[x-1]==1))L--;
if(L<R)LR1.push_back(pr(L,R));
}
y=fr[pos[x]][y]%2,x--;
}
x=Q,y=_j;
while(x<=m){
if(y==0||y==2)leadL[pos[x]]=pos[x]-nd[x],leadR[pos[x]]=pos[x]-1;
if(y==1||y==3)leadL[pos[x]]=pos[x]-nd[x]+1,leadR[pos[x]]=pos[x]+1;
if(x==m)break;
if(gr[pos[x]][y]<2){
int L=pos[x]+1+(y==1&&nd[x]%2==1);
int R=pos[x+1]-1-(gr[pos[x]][y]==0&&nd[x+1]%2==1)-nd[x+1]/2*2;
//cout<<"AT:"<<L<<' '<<R<<' '<<gr[x][y]<<'\n';
if(nd[x+1]>=2||(x==m-1&&nd[x+1]==1))R++;
//cout<<"AT2:"<<L<<' '<<R<<'\n';
if(L<R)LR2.push_back(pr(L,R));
}
y=gr[pos[x]][y]%2,x++;
}
//cout<<"DONE1"<<'\n';
//cout<<leadL[5]<<' '<<leadR[5]<<'\n';
if(2<=P&&a[pos[2]]==D-2){
int x=LR1.back().first+1;
mus[x]=1,rem--;
leadL[x]=leadR[x]=x-1,LR1.back().first+=2;
}
if(3<=P&&a[pos[3]]==D-2&&a[pos[2]]==D-1&&pos[2]!=pos[3]-1){
for(auto &[l,r]:LR1){
if(l+1<=r&&l>pos[2]&&r<pos[3]){
mus[l]=1,rem--,leadL[l]=leadR[l]=l+1;
l+=2;
}
}
}
for(int k=3,i=(int(LR1.size()))-1;k<=P;k++){
if(a[pos[k]]!=D-2||a[pos[k-1]]<=D)continue;
bool ok=0;
while(i>=0){
int &l=LR1[i].first,&r=LR1[i].second;
if(!(l+1<=r)||!(pos[k-1]<l&&r<pos[k])){
i--;
continue;
}
mus[l+1]=1,leadL[l]=leadR[l]=l-1,l+=2,rem--;
ok=1;
break;
}
assert(ok);
}
for(int k=m-2,i=(int(LR2.size()))-1;k>=Q;k--){
if(a[pos[k]]!=D-2||a[pos[k+1]]<=D)continue;
//cout<<"AA:"<<k<<' '<<pos[k]<<' '<<pos[k+1]<<'\n';
bool ok=0;
while(i>=0){
int &l=LR2[i].first,&r=LR2[i].second;
// cout<<"ILR:"<<i<<' '<<l<<' '<<r<<'\n';
if(!(l+1<=r)||!(pos[k]<l&&r<pos[k+1])){
i--;
continue;
}
mus[r-1]=1,leadL[r]=leadR[r]=r+1,r-=2,rem--;
ok=1;
break;
}
assert(ok);
}
if(Q<=m-1&&a[pos[m-1]]==D-2){
int x=LR2.back().second-1;
mus[x]=1,rem--;
leadL[x]=leadR[x]=x+1,LR2.back().second-=2;
}
if(Q<=m-2&&a[pos[m-2]]==D-2&&a[pos[m-1]]==D-1&&pos[m-2]!=pos[m-1]-1){
for(auto &[l,r]:LR2){
if(l+1<=r&&l>pos[m-2]&&r<pos[m-1]){
mus[r]=1,rem--,leadL[r]=leadR[r]=r-1;
r-=2;
}
}
}
assert(rem>=0);
//cout<<"DONE2"<<'\n';
for(auto [l,r]:LR1){
for(int i=l+1;i<=r&&rem;i+=2){
mus[i]=1,rem--;
leadL[i]=leadR[i]=i-1;
}
}
for(auto [l,r]:LR2){
for(int i=r-1;i>=l&&rem;i-=2){
mus[i]=1,rem--;
leadL[i]=leadR[i]=i+1;
}
}
P=pos[P],Q=pos[Q];
//cout<<"MUS:";
//for(int i=1;i<=n;i++){
// cout<<mus[i]<<' ';
//}
//puts("");
for(int i=1;i<=n;i++)if(mus[i])nd[i]=max(a[i]-(D-1),0);else nd[i]=0;
for(int i=2;i<=P;i++){
if(!mus[i])continue;
int j=i-1;
while(!mus[j])j--;
if(nd[j]>=2||(nd[j]==1&&j==1&&i==3)){
norm(i);
leadL[i]+=nd[i]%2,nd[i]-=nd[i]%2,has[i]=1;
norm(i);
}
}
for(int i=Q;i<n;i++){
if(!mus[i])continue;
int j=i+1;
while(!mus[j])j++;
//cout<<"IIIIIIIIIIIIIIIIII:"<<i<<' '<<nd[i]<<' '<<leadL[i]<<'\n';
if(nd[j]>=2||(nd[j]>=1&&j==n&&i==n-2)){
norm(i);
leadR[i]-=nd[i]%2,nd[i]-=nd[i]%2,has[i]=1;
norm(i);
}
}
//接下来开始建图了。
vector<int> path;
for(int i=1,lst=0;i<=n;i++){
if(!mus[i])continue;
pathpre[i]=lst,pathnxt[lst]=i,lst=i;
useful[i]=1,path.push_back(i);
}
pathnxt[0]=0;
assert(pathnxt[path.back()]==0);
assert(pathnxt[0]==0);
while(leadL[P]>P+1)leadL[P]--,leadR[P]--;
while(leadR[Q]<Q-1)leadL[Q]++,leadR[Q]++;
if(nd[P]>=2&&nd[Q]>=2){
hasdonePQ[P]=1;
hasdonePQ[Q]=1;
for(int j=leadL[P];j<=leadR[P];j++){
useful[j]=1;
if(j!=P)v[P].push_back(j);
}
for(int j=leadL[Q];j<=leadR[Q];j++){
useful[j]=1;
if(j!=Q)v[Q].push_back(j);
}
assert(v[P].size()>=2&&v[Q].size()>=2);
int x=v[P][v[P].size()-2];
int y=v[Q][1];
v[P][v[P].size()-1]=y,v[Q][0]=x;
/*int dii=leadR[Q]-leadL[Q];
leadL[Q]=leadR[P]-1;
leadR[Q]=leadL[Q]+dii;*/
}
//下面没有 leadl leadr 的事了
//cout<<"LEAD[l,r]:\n";
//for(int i=1;i<=n;i++){
// cout<<leadL[i]<<' '<<leadR[i]<<'\n';
//}//
//puts("");
//cout<<v[1].size()<<'\n';
for(int i=1;i<=n;i++){
if(hasdonePQ[i])continue;
for(int j=leadL[i];j<=leadR[i];j++){
useful[j]=1;
if(j!=i)v[i].push_back(j);
}
}
for(int i=1;i<=n;i++){
if(!mus[i])continue;
if(i<=P&&has[i]){
if(v[pathpre[i]].size()>=2)v[i].insert(v[i].begin(),v[pathpre[i]][v[pathpre[i]].size()-2]);
else v[i].insert(v[i].begin(),v[pathpre[i]][0]);
}
if(i>=Q&&has[i]){
if(v[pathnxt[i]].size()>=2)v[i].push_back(v[pathnxt[i]][1]);
else v[i].push_back(v[pathnxt[i]][0]);
}
//cout<<"V:"<<i<<' '<<v[i].size()<<' '<<has[i]<<'\n';
//for(int j:v[i])cout<<j<<' ';
//puts("");
}
//P=1 Q=n
int posP=0;
for(int i=0;i<path.size();i++){
if(path[i]==P){
posP=i;
for(int j=i-2;j>=0;j-=2)Add(path[j+2],path[j]);
for(int j=i-1;j>=0;j-=2)Add(path[j],path[j+2]);
for(int j=i+3;j<path.size();j+=2)Add(path[j],path[j-2]);
for(int j=i+2;j<path.size();j+=2)Add(path[j-2],path[j]);
for(int j=0;j+1<path.size();j++){
if(j%2==i%2){
Add(path[j],path[j+1]);
for(int k=path[j]+1;k<path[j+1];k++){
Add(path[j],k),Add(k,path[j+1]);
}
}
else {
Add(path[j+1],path[j]);
for(int k=path[j]+1;k<path[j+1];k++){
Add(k,path[j]),Add(path[j+1],k);
}
}
}
break;
}
}
for(int i=0;i<path.size();i++)ishi[path[i]]=Pi[path[i]]=(i%2!=posP%2);
int posQ=posP+1;
//cout<<"D1:"<<D<<'\n';
for(int i=0;i<path.size();i++){
if(a[path[i]]==D-2)continue;
vector<int> my=v[path[i]];
if(i)my.insert(my.begin(),path[i-1]);
if(i>1)my.insert(my.begin(),path[i-2]);
if(i+1<path.size())my.push_back(path[i+1]);
if(i+2<path.size())my.push_back(path[i+2]);
if(i>1||(i==1&&path[i]!=2)){
for(int j=1;j<my.size();j++)ishi[my[j]]=1-ishi[my[j-1]];
}
else {
for(int j=((int)my.size())-2;j>=0;j--)ishi[my[j]]=1-ishi[my[j+1]];
}
//cout<<"X:"<<path[i]<<' '<<ishi[2]<<' '<<ishi[1]<<'\n';
for(int j=0;j+1<my.size();j++){
if(ishi[my[j]]){
for(int k=my[j]+1;k<my[j+1];k++){
if(k!=path[i])Add(k,my[j]),Add(my[j+1],k);
}
Add(my[j+1],my[j]);
}
else {
for(int k=my[j]+1;k<my[j+1];k++){
if(k!=path[i])Add(my[j],k),Add(k,my[j+1]);
}
Add(my[j],my[j+1]);
}
}
if(i<posP||i>posQ){
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]])Add(my[j],my[j+2],i<posP);
else Add(my[j+2],my[j],i<posP);
}
}
else if(i==posP){
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]])Add(my[j],my[j+2]);
else if(my[j+2]<Q)Add(my[j+2],my[j]);//如果大于 Q，我们不关心！
}
}
else {
for(int j=0;j+2<my.size();j++){
if(ishi[my[j]]){
if(my[j]>P)Add(my[j+2],my[j]);
}
else Add(my[j],my[j+2]);
}
}
for(int j=0;j<my.size();j++)if(mus[j])ishi[j]=Pi[j];
}
//cout<<"D:"<<D<<'\n';
//特殊处理D-2
for(int i=P;i>=1;i=pathpre[pathpre[i]]){
if(a[i]==D-2&&pathpre[pathpre[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(pathpre[pathpre[i]],j),Add(j,pathnxt[i]);
}
}
}
//cout<<"DD\n";
for(int i=pathpre[P];i>=1;i=pathpre[pathpre[i]]){
if(a[i]==D-2&&pathpre[pathpre[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(j,pathpre[pathpre[i]]),Add(pathnxt[i],j);
}
}
}
//cout<<"DD\n";
for(int i=Q;i<=n&&i;i=pathnxt[pathnxt[i]]){
if(a[i]==D-2&&pathnxt[pathnxt[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(pathpre[i],j),Add(j,pathnxt[pathnxt[i]]);
}
}
}
//cout<<"DD\n";
for(int i=pathnxt[Q];i<=n&&i;i=pathnxt[pathnxt[i]]){
if(a[i]==D-2&&pathnxt[pathnxt[i]]){
for(int j=pathpre[i]+1;j<pathnxt[i];j++){
if(j!=i)Add(j,pathpre[i]),Add(pathnxt[pathnxt[i]],j);
}
}
}
//cout<<"DD\n";
//大斜杠，是不是其实不用管？
//for(int i=1;i<=n;i++)cout<<"IN USEFUL:"<<i<<' '<<ind[i]<<' '<<useful[i]<<'\n';
Toposort();
Clear();
}
int premus[N+5],sufmus[N+5];
void Redo(){
m=0;
for(int i=1;i<=n;i++)
if(mus[i]){
pos[++m]=i,id[i]=m,dif[m]=pos[m]-pos[m-1]-1;
nd[m]=max(a[i]-(D-1),0);
}
}
bool Check(int P,int Q){
if(D>=4&&a[Q]==D-1&&!(Q==n-1||Q==n))return 0;
if(D>=4&&a[P]==D-1&&!(P==1||P==2))return 0;
if(D==3&&a[2]==2&&P==1&&Q==2)return 0;
if(D==3&&a[n-1]==2&&P==n-1&&Q==n)return 0;
if(m>D)return 0;
if(premus[P]+sufmus[Q]+m+(!mus[P])+(!mus[Q])>D)return 0;
//cout<<"UU"<<'\n';
int ndP=max(a[P]-(D-1),0);
int ndQ=max(a[Q]-(D-1),0);
//cout<<"PQD: "<<P<<' '<<Q<<' '<<D<<'\n';
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int s=m+f[P][i]+g[Q][j]+(!mus[P])+(!mus[Q]);
//if(P==1&&Q==3)cout<<i<<' '<<j<<' '<<f[P][i]<<' '<<g[Q][j]<<' '<<s<<' '<<D<<'\n';
if(s<D)continue;
int rP=(i==1)*(ndP%2)+ndP/2*2,lQ=(j==0)*(ndQ%2)+ndQ/2*2;
//cout<<"IJ:"<<i<<' '<<j<<' '<<rP<<' '<<lQ<<'\n';
if(rP<=1||lQ<=1){
if(rP==1&&lQ==1&&Q-P-1==1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
if(rP+lQ<=Q-P-1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
}
else {
if(rP+lQ-2<=Q-P-1){
mus[P]=mus[Q]=1,Redo();
Construct(i,j,P,Q);
return 1;
}
}
}
}
return 0;
}
//f,g,fr,gr,premus,sufmus 都是位置(pos)上的
int Transf(int _i,int lstpos,int curpos,int dif,int lstnd,int curnd,int musnd){
int w=dif-lstnd/2*2;
int save=((lstnd>=2)||(_i==2&&lstnd==1));
int cur=0;
if(_i==2&&a[curpos]==D-2){
musnd++,cur=1;
}
else if(_i==3&&a[curpos]==D-2&&a[lstpos]==D-1&&lstpos!=curpos-1){
musnd++,cur=1;
}
else if(_i>=3&&a[curpos]==D-2&&a[lstpos]>D){
musnd++,cur=1;
}
for(int j=0;j<2;j++){
if(lstnd%2==0&&j==0)continue;
for(int k=0;k<2;k++){
if(curnd%2==0&&k==0)continue;
int nw=w-(j==1&&lstnd%2==1)-(k==0&&curnd%2==1);
if(nw>=0){
if((nw+save)/2>=cur)updf(curpos,k,f[lstpos][j]+(nw+save)/2,j);
}
if(k==0&&save&&!cur){
nw+=(curnd%2==1);//不需要了，但也不能放新东西
if(nw>=0){
updf(curpos,k,f[lstpos][j],j+2);
}
}
}
}
return musnd;
}
int Transg(int _i,int lstpos,int curpos,int dif,int lstnd,int curnd,int musnd){
int w=dif-lstnd/2*2;
int save=(lstnd>=2||(_i==m-1&&lstnd==1));
int cur=0;
if(_i==m-1&&a[curpos]==D-2){
musnd++,cur=1;
}
else if(_i==m-2&&a[curpos]==D-2&&a[lstpos]==D-1&&lstpos!=curpos+1){
musnd++,cur=1;
}
else if(_i<=m-2&&a[curpos]==D-2&&a[lstpos]>D){
musnd++,cur=1;
}
for(int j=0;j<2;j++){
if(lstnd%2==0&&j==1)continue;
for(int k=0;k<2;k++){
if(curnd%2==0&&k==1)continue;
int nw=w-(j==0&&lstnd%2==1)-(k==1&&curnd%2==1);
if(nw>=0){
if((nw+save)/2>=cur)updg(curpos,k,g[lstpos][j]+(nw+save)/2,j);
}
if(k==1&&save&&!cur){
nw+=(curnd%2==1);
if(nw>=0){
updg(curpos,k,g[lstpos][j],j+2);
}
}
}
}
return musnd;
}
bool Try(int d){
D=d;
for(int i=1;i<=n;i++)pl[i]=0,mus[i]=0;
for(int i=1;i<=n;i++)
if(i==1||i==n||a[i]!=D){
mus[i]=1;
if(max(a[i]-(D-1),0)%2==0&&i!=2&&i!=n&&i!=n-1&&i!=1&&a[i]!=D-2)return 0;
}
if(a[n]==D-1)mus[n-1]=1;
if(a[1]==D-1)mus[2]=1;
m=0;
for(int i=1;i<=n;i++)
if(mus[i]){
pos[++m]=i,id[i]=m,dif[m]=pos[m]-pos[m-1]-1;
nd[m]=max(a[i]-(D-1),0);
}
if(m>D)return 0;
for(int i=0;i<=n;i++){
for(int j=0;j<2;j++)f[i][j]=g[i][j]=-inf;
premus[i]=sufmus[i]=0;
}
f[1][1]=0;
int musnd=0;
for(int i=2;i<=m;i++){
for(int j=pos[i-1]+1;j<pos[i];j++){
premus[j]=Transf(i,pos[i-1],j,j-pos[i-1]-1,nd[i-1],1,musnd);
}
premus[pos[i]]=musnd=Transf(i,pos[i-1],pos[i],pos[i]-pos[i-1]-1,nd[i-1],nd[i],musnd);
}
g[n][0]=0,musnd=0;
for(int i=m-1;i>=1;i--){
for(int j=pos[i]+1;j<pos[i+1];j++){
sufmus[j]=Transg(i,pos[i+1],j,pos[i+1]-j-1,nd[i+1],1,musnd);
}
sufmus[pos[i]]=musnd=Transg(i,pos[i+1],pos[i],pos[i+1]-pos[i]-1,nd[i+1],nd[i],musnd);
}
for(int i=1,j;i<n;i=j){
j=i+1;
while(!mus[j])j++;
//cout<<"C:"<<i<<' '<<j<<'\n';
if(Check(i,j))return 1;
for(int p=i+1;p<j;p++)if(Check(i,p)||Check(p,j))return 1;
for(int p=i+1;p<j;p++)for(int q=p+1;q<j&&q-p<=2;q++)if(Check(p,q))return 1;
}
return 0;
}
int Recover(ve _a){
for(int i=1;i<=n;i++)a[i]=_a[i-1]+1;
int mne=*min_element(a+1,a+n+1);
for(int i=mne;i<=mne+2;i++){
if(i<2||i>n)continue;
if(Try(i))return i;
}
assert(0);
return 0;
}
int S;
void Solve(){
scanf("%d",&n);
vector<int> vec(n);
for(int i=0;i<n;i++)scanf("%d",&vec[i]);
if(S==5)for(int i=0;i<=n;i++)scanf("%*s");
if(S==6)scanf("%*s");
assert(Recover(vec));
for(int i=1;i<=n;i++)cout<<pl[i]<<' ';
puts("");
}
int main(){
int t;
scanf("%d%d",&S,&t);
while(t--)Solve();
}*/