1 // File Name: 1006.cpp  2 // Author: darkdream  3 // Created Time: 2014年07月31日 星期四 12时46分19秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24  25 using namespace std; 26 #define maxn 100005  27 struct node{ 28     int l , r ;  29     int is1; 30     int limits; 31 }tree[maxn << 2]; 32 int a[maxn]; 33 int L(int x) 34 { 35     return 2*x;  36 } 37 int gcd(int a, int b) 38 { 39     return b == 0 ?a:gcd(b,a%b); 40 } 41 int R(int x) 42 { 43     return 2 * x + 1;  44 } 45 void pushup(int c) 46 { 47     tree[c].limits = max(tree[L(c)].limits,tree[R(c)].limits); 48 } 49 void pushdown(int c) 50 { 51     if(tree[c].is1) 52     { 53         tree[L(c)].is1 = 1;  54         tree[R(c)].is1 = 1; 55         tree[c].is1 = 0; 56         tree[L(c)].limits = tree[R(c)].limits = tree[c].limits; 57     } 58 } 59 void build(int c , int l ,int r) 60 { 61     tree[c].l = l ;  62     tree[c].r = r; 63     tree[c].is1 = 0 ;  64     if(l == r) 65     { 66         tree[c].limits = a[l]; 67         return ; 68     } 69     int m = (l+r)/2; 70     build(L(c),l,m); 71     build(R(c),m+1,r); 72     pushup(c); 73 } 74 void update1(int c, int l , int r,int x) 75 { 76     if(l <= tree[c].l && r >= tree[c].r) 77     { 78         tree[c].is1 = 1; 79         tree[c].limits = x;  80         return ; 81     } 82     int m = (tree[c].l+ tree[c].r)/2; 83     pushdown(c); 84     if(l <= m) 85         update1(L(c),l,r,x); 86     if( r > m ) 87         update1(R(c),l,r,x); 88     pushup(c); 89 } 90 void update2(int c, int l , int r,int x) 91 { 92     if(tree[c].limits < x) 93     { 94         return ;  95     } 96     if(tree[c].is1 && l <= tree[c].l && r >= tree[c].r) 97     { 98         tree[c].limits = gcd(tree[c].limits,x); 99         return ;100     }101     if(tree[c].l == tree[c].r)102     {103         tree[c].is1 = 0 ; 104         tree[c].limits = gcd(x,tree[c].limits);105         return; 106     }107     int m = (tree[c].l+ tree[c].r)/2;108     pushdown(c);109     if(l <= m)110         update2(L(c),l,r,x);111     if( r > m )112         update2(R(c),l,r,x);113     pushup(c);114 }115 void put(int l , int r , int x)116 {117 //    printf("****%d %d\n",l,r);118     for(int i =l ;i <= r;i ++ )119         a[i] = x;120     return; 121 }122 void get(int c )123 {124     if(tree[c].is1) 125     {126         put(tree[c].l,tree[c].r,tree[c].limits);127         return; 128     }129     if(tree[c].l == tree[c].r)130     {131         a[tree[c].l] = tree[c].limits;132         return; 133     }134     pushdown(c);135     get(L(c));136     get(R(c));137 }138 int main(){139     int t;140     //freopen("input.txt","r",stdin);141     //freopen("output.txt","w",stdout);142     scanf("%d",&t);143     while(t--)144     {145         //memset(tree,0,sizeof(tree));146         int n ,m;147         scanf("%d",&n);148         for(int i = 1;i <= n;i ++)149         {        150             scanf("%d",&a[i]);151          //   printf("%d ",a[i]);152         }153         //printf("\n");154         build(1,1,n);155         scanf("%d",&m);156         int ta,tb,tc,td;157         for(int i = 1;i <= m;i ++)158         {159             scanf("%d %d %d %d",&ta,&tb,&tc,&td);160             if(ta == 1)161             {162                 update1(1,tb,tc,td);163             }else{164                 update2(1,tb,tc,td);165             }166         }167         get(1);168         for(int i =1;i <= n;i ++)169             printf("%d ",a[i]);170         printf("\n");171         //printf("%d\n",t);172     }173     return 0;174 }