#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1000006 #define MAXM 100005 int tree[400006]; int a[100006]; int fact[1000006]; int prime[1000006]; int max(int a, int b) { return a > b? a : b; } void sieve() { fact[1] = 1;fact[0] = 1; prime[0] = 1;prime[1] = 1; int i; for(i=2;i<1000006;i++) { if(!prime[i]) { fact[i] = i; long long int j = (long long)i*i; while(j < 1000006) { if(!prime[j]) { prime[j] = 1; fact[j] = i; } j+=i; } } } } void build(int node, int l, int r) { if(l==r) { tree[node] = fact[a[l]]; a[l] /= tree[node]; } else { int mid = (l+r)/2; build(2*node,l,mid); build(2*node+1,mid+1,r); tree[node] = max(tree[2*node],tree[2*node +1]); } } int query(int node, int l, int r, int a, int b) { if(tree[node] == 1) return 1; if(l>r || l > b || r < a) return 1; if(a <= l && r <= b) return tree[node]; int mid = (l+r)/2; int left = query(2*node,l,mid,a,b); int right = query(2*node+1,mid+1,r,a,b); return max(left,right); } void update(int node, int l, int r, int x, int y) { if(tree[node] == 1) return; if(l > r || l > y || r < x) return ; if(l == r) { tree[node] = fact[a[l]]; a[l] /= tree[node]; } else { int mid = (l+r)/2; update(2*node,l,mid,x,y); update(2*node+1,mid+1,r,x,y); tree[node] = max(tree[2*node],tree[2*node+1]); } } int main() { int t,i; sieve(); scanf("%d",&t); while(t--) { int n,m; scanf("%d %d",&n,&m); memset(a,1,sizeof(a)); memset(tcnt,0,sizeof(tcnt)); memset(tree,1,sizeof(tree)); for(i=0;i<n;i++) scanf("%d",&a[i]); build(1,0,n-1); while(m--) { int x,st,end; scanf("%d %d %d",&x,&st,&end); st--;end--; if(x==0) update(1,0,n-1,st,end); else printf("%d ",query(1,0,n-1,st,end)); } printf("\n"); } return 0; }