\(T1\)旅行计划

不\(sb\)的题

比较显然转化成求一个点到所有点的最短路和

考虑我们非树边很少,那么可以把非树边连接的点看做是关键点,那么我们可以预处理每个关键点之间的最短路

我们每次询问,对询问点看做关键点,我们的路径肯定是关键点之间路径\(+\)树上路径,我们对于每个关键点的管控范围可以求出,那么我们最后求的是,一个点到所有关键点的权值\(+\)每个关键点对应联通块的子树贡献,可以把每个联通快统一处理,每次跑一遍类似虚树的东西,然后建立虚树时候顺便统计子树贡献即可,本质上大概也是个类似换根\(dp\)的东西,在每个关键点往外扩张的过程

\(T2\)搬砖

\(sb\)题,上午把式子推对了硬是没看出差分

//考虑这个维护的是什么
//我们维护区间连续的一段取模同余的最大模数
//假设只有两个数,我们的数字是abs(x-y)[x!=y]
//对于一个序列.我们的数字是一段区间所有相邻的gcd
//在这里,我已经得到了正解,tmd这是差分??????
//我没意识到...
//那么就很简单了,我们线段树维护区间差分gcd
//我们第二个修改时区间加,那么只需要改变两个位置
//第一个操作是区间变化直接打一个区间标记即可
//k=2a,m=a^2+b 区间gcd为gcd(kl+m,k)
#include<bits/stdc++.h>
#define int __int128
#define MAXN 200005
using namespace std;
int h[MAXN],n,q;
__int128 gcd(__int128 a,__int128 b)
{
    if(a==0) return b;
    if(b==0) return a;
    return gcd(b,a%b);
}
int Abs(int a)
{
    if(a>0) return a;
    return -a;
}
namespace Seg1
{
    #define ls (now<<1)
    #define rs ((now<<1)|1)
    struct Tr
    {
        int l,r,add,lza,lzb,lzc;
        __int128 num;
        bool lz;
    }tr[MAXN<<2];
    void build(int now,int l,int r)
    {
         tr[now].l=l;
         tr[now].r=r;
         if(l==r)
         {
            tr[now].num=h[l];
            return ;
         }
         int mid=(l+r)>>1;
         build(ls,l,mid);
         build(rs,mid+1,r);
    }
    void pd(int now)
    {
         if(tr[now].lz)
         {
            int a=tr[now].lza;
            int b=tr[now].lzb;
            int c=tr[now].lzc;
            tr[ls].lza=a; tr[ls].lzb=b; tr[ls].lzc=c; tr[ls].lz=true; tr[ls].add=0;
            tr[ls].num=tr[ls].l*tr[ls].l*a+tr[ls].l*b+c;
            tr[rs].lza=a; tr[rs].lzb=b; tr[rs].lzc=c; tr[rs].lz=true; tr[rs].add=0;
            tr[rs].num=tr[rs].l*tr[rs].l*a+tr[rs].l*b+c;
            tr[now].lza=tr[now].lzb=tr[now].lzc=0;
            tr[now].lz=false;
         }
         if(tr[now].add)
         {
            int add=tr[now].add;
            tr[ls].num+=add;
            tr[ls].add+=add;
            tr[rs].num+=add;
            tr[rs].add+=add;
            tr[now].add=0;
         }
    }
    void Cover(int now,int l,int r,int a,int b,int c)
    {
         pd(now);
         if(tr[now].l>=l&&tr[now].r<=r)
         {
            tr[now].lz=true;
            tr[now].lza=a;
            tr[now].lzb=b;
            tr[now].lzc=c;
            tr[now].add=0;
            tr[now].num=tr[now].l*tr[now].l*a+tr[now].l*b+c;
            pd(now);
            return ;
         }
         int mid=(tr[now].l+tr[now].r)>>1;
         if(l<=mid) Cover(ls,l,r,a,b,c);
         if(r>mid)  Cover(rs,l,r,a,b,c);
    }
    void change(int now,int l,int r,int c)
    {
         pd(now);
         if(tr[now].l>=l&&tr[now].r<=r)
         {
            tr[now].add+=c;
            tr[now].num+=c;
            pd(now);
            return ;
         }
         int mid=(tr[now].l+tr[now].r)>>1;
         if(l<=mid) change(ls,l,r,c);
         if(r>mid)  change(rs,l,r,c);
    }
    int query(int now,int poz)
    {
        pd(now);
        if(tr[now].l==poz&&tr[now].r==poz)
        {
            return tr[now].num;
        }
        int mid=(tr[now].l+tr[now].r)>>1;
        if(poz<=mid) return query(ls,poz);
        else return query(rs,poz);
    }
}
namespace Seg2
{
    #define ls (now<<1)
    #define rs ((now<<1)|1)
    struct Tr
    {
        int l,r,lza,lzb,lzc;
        __int128 G;
        bool lz;
    }tr[MAXN<<2];
    int GCD(int l,int r,int a,int b,int c)
    {
        return __gcd(2*a,2*a*l-a+b);
    }
    int val(int p,int a,int b,int c)
    {
        return p*p*a+p*b+c;
    }
    void upd(int now)
    {
         tr[now].G=gcd(tr[ls].G,tr[rs].G);
    }
    void build(int now,int l,int r)
    {
        tr[now].l=l;
        tr[now].r=r;
        if(l==r)
        {
            tr[now].G=Abs(h[l]-h[l+1]);
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        upd(now);
    }
     void pd(int now)
     {
          if(tr[now].lz)
          {
             int a=tr[now].lza;
             int b=tr[now].lzb;
             int c=tr[now].lzc;
             int k=2*a;
             int m=a*a+b;
             tr[ls].lza=a; tr[ls].lzb=b; tr[ls].lzc=c; tr[ls].lz=true;
             if(tr[ls].l!=tr[ls].r)tr[ls].G=GCD(tr[ls].l,tr[ls].r,a,b,c);
             else tr[ls].G=Abs(val(tr[ls].l+1,a,b,c)-val(tr[ls].l,a,b,c));

             tr[rs].lza=a; tr[rs].lzb=b; tr[rs].lzc=c; tr[rs].lz=true;
             if(tr[rs].l!=tr[rs].r)tr[rs].G=GCD(tr[rs].l,tr[rs].r,a,b,c);
             else tr[rs].G=Abs(val(tr[rs].l+1,a,b,c)-val(tr[rs].l,a,b,c));
             tr[now].lz=false;
             tr[now].lza=0; tr[now].lzb=0; tr[now].lzc=0;
          }
     }
     /*
     */
    void Cover(int now,int l,int r,int a,int b,int c)
    {
//       cout<<"Tr: "<<(long long)tr[now].l<<" "<<(long long)tr[now].r<<"\n";
         if(tr[now].l>=l&&tr[now].r<=r)
         {
//             cout<<tr[now].l<<" tott "<<tr[now].r<<" "<<endl;
             int k=2*a;
             int m=a*a+b;
             if(tr[now].l==tr[now].r)
             {
                tr[now].G=Abs(val(tr[now].r+1,a,b,c)-val(tr[now].l,a,b,c));

//                 cout<<"change  "<<"   "<<(long long)now<<" "<<(long long)tr[now].l+1<<"    "<<(long long)tr[now].r+1<<" "<<(long long)tr[now].G<<endl;
//                 cout<<a<<" "<<b<<" "<<c<<endl;
//              cout<<"kok: "<<tr[now].l<<" "<<tr[now].r<<"\n";
                return ;
             }
             tr[now].lz=true;
             tr[now].lza=a;
             tr[now].lzb=b;
             tr[now].lzc=c;
             tr[now].G=GCD(tr[now].l,tr[now].r,a,b,c);
//             cout<<"here "<<tr[now].l<<" "<<tr[now].r<<" "<<(long long )tr[now].G<<endl;
             return ;
         }
         pd(now);
         int mid=(tr[now].l+tr[now].r)>>1;
         if(l<=mid) Cover(ls,l,r,a,b,c);
         if(r>mid) Cover(rs,l,r,a,b,c);
         upd(now);
    }
    void change(int now,int poz,int k)
    {
         if(tr[now].l==poz&&tr[now].r==poz)
         {
            tr[now].G=k;
            return ;
         }
         pd(now);
         int mid=(tr[now].l+tr[now].r)>>1;
         if(poz<=mid) change(ls,poz,k);
         else change(rs,poz,k);
         upd(now);
    }
    void debug(int now)
    {
         pd(now);
         cout<<(long long)now<<" "<<(long long)tr[now].l<<" "<<(long long)tr[now].r<<" "<<((long long)tr[now].G)<<"\n";
         if(tr[now].l!=tr[now].r)debug(ls),debug(rs);
    }
}
void print(__int128 x)
{
     int cnt=0;
     signed Mid[100];
     if(x==0)
     {
        cout<<0<<"\n";
        return;
     }
     while(x)
     {
         Mid[++cnt]=x%10;
         x/=10;
     }
     for(int i=cnt;i>=1;i--) cout<<Mid[i];
     cout<<"\n";
}
int Read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
signed main()
{
    n=Read(),q=Read();
//    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++)
    {
        h[i]=Read();
//        scanf("%lld",&h[i]);
    }
    Seg1::build(1,1,n);
    Seg2::build(1,1,n-1);
    for(long long i=1,op,l,r,a,b,c;i<=q;i++)
    {
//        cin>>op>>l>>r>>a>>b>>c;
        op=Read(),l=Read(),r=Read(),a=Read(),b=Read(),c=Read();
//        scanf("%lld%lld%lld%lld%lld%lld",&op,&l,&r,&a,&b,&c);
        if(op==1)
        {
            Seg1::Cover(1,l,r,a,b,c);
//            if(l-1)
            if(r!=1) Seg2::Cover(1,l,max(r-1,1ll),a,b,c);
            int res1,res2;
            if(l-1>=1)
            {
                res1=Seg1::query(1,l-1);
                res2=Seg1::query(1,l);
                Seg2::change(1,l-1,Abs(res1-res2));
            }
            if(r+1<=n)
            {
                res1=Seg1::query(1,r);
                res2=Seg1::query(1,r+1);
                Seg2::change(1,r,Abs(res1-res2));
            }
        }
        if(op==2)
        {
            Seg1::change(1,l,r,c);
            int res1,res2;
            if(l-1>=1)
            {
                res1=Seg1::query(1,l-1);
                res2=Seg1::query(1,l);
                Seg2::change(1,l-1,Abs(res1-res2));
            }
            if(r+1<=n)
            {
                res1=Seg1::query(1,r);
                res2=Seg1::query(1,r+1);
                Seg2::change(1,r,Abs(res1-res2));
            }
        }
        print(Seg2::tr[1].G);
    }
}

\(T3\)寻觅

\(sb\)题,暴力能水过去

//说句人话就是
//一个区间除了都是零否则至少有一个数只出现一次
//考虑最后的序列至少有一个数只能出现一次
//那么填满之后的序列必须有一个数出现一次
//贪心维护?
//反正最终序列必须有一个出现一次,不妨设第一个是1
//我们肯定是按顺序插入?
//或者是每一段区间至少被覆盖一次
//一段区间要不被左端点覆盖,要不被右端点覆盖,要不被中间点覆盖(废话)
//直接构造就行吧,为什么要有顺序?这样貌似限制更强
//那考虑顺序,我们要保证每时每刻都要被覆盖
//那么我们新增一个点
//那么我们和他相等的点的覆盖范围就要被截断
//我们要实时保证有的地方可以被覆盖
//而且0的位置可以忽略
//我们维护一个每个数字维护一个set
//然后实时更新覆盖范围,最多n^2个我们每次至多n^2,n^3上限达不到
//乘个24的小常数
//盲猜正解直接转化成二维区间加减了,询问区间和是否等于0
#include<bits/stdc++.h>
#define MAXN 8505
using namespace std;
int cov[MAXN][MAXN],Fin[MAXN],p[MAXN],T;
set<int>Num[25];
void solve(int poz)
{
     for(int i=1;i<=24;i++)
     {
         int l=*(--lower_bound(Num[i].begin(),Num[i].end(),poz));
         int r=(*upper_bound(Num[i].begin(),Num[i].end(),poz));
         int ll=*(--lower_bound(Num[i].begin(),Num[i].end(),l));
         int rr=*(upper_bound(Num[i].begin(),Num[i].end(),r));
         bool flag=true;
         for(int j=l;j>ll;j--)
         {
             for(int k=poz;k<r;k++)
             {
                 if(cov[j][k]<=1)
                 {
                    flag=false;
                    goto EB;
                 }
             }
         }
         for(int j=poz;j>l;j--)
         {
             for(int k=r;k<rr;k++)
             {
                 if(cov[j][k]<=1)
                 {
                    flag=false;
                    goto EB;
                 }
             }
         }
         EB:
         if(flag)
         {
             Fin[poz]=i;
             Num[i].insert(poz);
             for(int j=l;j>ll;j--)
             {
                 for(int k=poz;k<r;k++)
                 {
                     cov[j][k]--;
                 }
             }
             for(int j=poz;j>l;j--)
             {
                 for(int k=r;k<rr;k++)
                 {
                     cov[j][k]--;
                 }
             }
             for(int j=l+1;j<=poz;j++)
             {
                 for(int k=poz;k<r;k++)
                 {
                     cov[j][k]++;
                 }
             }
             break;
         }
     }
}
int n;
int A[MAXN]={0,22,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,16,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,17,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,19,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,16,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,17,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,20,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,16,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,17,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,19,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,16,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,17,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,14,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,16,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,10,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,11,1,2,4,1,2,5,1,2,7,1,2,4,1,2,5,1,2,8,1,2,4,1,2,5,1,2,13,1,2};
void sub2()
{
     for(int i=1;i<=n;i++)
     {
         cout<<A[i]<<" ";
     }
     cout<<"\n";
}
void sol()
{
     scanf("%d",&n);
     memset(cov,0,sizeof(cov));
     for(int i=1;i<=24;i++)
     {
         while(Num[i].size()) Num[i].erase(Num[i].begin());
         Num[i].insert(0);
         Num[i].insert(n+1);
     }
     bool flag=true;
     for(int i=1;i<=n;i++)
     {
         scanf("%d",&p[i]);
         if(p[i]!=i) flag=false;
     }
     if(flag)
     {
        sub2();
        return ;
     }
     for(int i=1;i<=n;i++)
     {
         solve(p[i]);
     }
     for(int i=1;i<=n;i++)
     {
         cout<<Fin[i]<<" ";
     }
     cout<<"\n";
}
int main()
{
    scanf("%d",&T);
    while(T--) sol();
}