TLE on #7

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

#define N 50005
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;
int n,q,a[N],b[N];

namespace Qgcd{
  vector<int> factor[N];
  int g[1005][1005], m[N][4], is[N], p[N], cnt = 0, bd;
  void sieve(int maxn){
    memset(is, 1, sizeof is);
    is[1] = 0; m[1][1] = m[1][2] = m[1][3] = 1;
    for(int i = 2; i <= maxn; ++i){
      if(is[i]) p[++cnt] = i, m[i][1] = m[i][2] = 1, m[i][3] = i;
      for(int j = 1; j <= cnt && i * p[j] <= maxn; ++j){
        is[i * p[j]] = 0;
        memcpy(m[i * p[j]], m[i], sizeof(int) * 4);
        m[i * p[j]][1] *= p[j];
        if(m[i * p[j]][1] > m[i * p[j]][2]) std::swap(m[i * p[j]][1], m[i * p[j]][2]);
        if(m[i * p[j]][2] > m[i * p[j]][3]) std::swap(m[i * p[j]][2], m[i * p[j]][3]);
        if(i % p[j] == 0) break;
      }
    }
    return ;
  } 
  inline int gcd(int x, int y){
    int r = 1;
    for(int i = 1; i <= 3; ++i){
      if(m[x][i] > bd){
        if(y % m[x][i] == 0){
          y /= m[x][i];
          r *= m[x][i];
        }
        continue;
      }
      int t = g[m[x][i]][y % m[x][i]];
      r *= t, y /= t;
    }
    return r;
  }
  void init(int maxn){
    sieve(maxn); bd = sqrt(maxn) + 1;
    for(int i = 1; i <= cnt; ++i)
      for(int j = p[i]; j <= maxn; j += p[i])
        factor[j].push_back(p[i]);
    for(int i = 1; i <= sqrt(maxn) + 1; ++i) g[i][0] = g[0][i] = i;
    for(int i = 1; i <= sqrt(maxn) + 1; ++i)
      for(int j = 1; j <= i; ++j)
        g[i][j] = g[j][i] = g[j][i % j];
    return ;
  }
}

int block,bel[N],L[255],R[255],tag[255]; ull mn[255],f[255][N],g[255][N];

void upd(int x,int y,int k) {
    if (bel[x]==bel[y]) {
        if (tag[bel[x]])
            for (int i=L[bel[x]];i<=R[bel[x]];i++) a[i]=tag[bel[x]];
        for (int i=x;i<=y;i++) a[i]=k;
        mn[bel[x]]=INF,tag[bel[x]]=0;
        for (int i=L[bel[x]];i<=R[bel[x]];i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            mn[bel[x]]=min(mn[bel[x]],1ull*a[i]/d*b[i]/d);
        }
    } else {
        if (tag[bel[x]])
            for (int i=L[bel[x]];i<=R[bel[x]];i++) a[i]=tag[bel[x]];
        for (int i=x;i<=R[bel[x]];i++) a[i]=k;
        mn[bel[x]]=INF,tag[bel[x]]=0;
        for (int i=L[bel[x]];i<=R[bel[x]];i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            mn[bel[x]]=min(mn[bel[x]],1ull*a[i]/d*b[i]/d);
        }
        if (tag[bel[y]])
            for (int i=L[bel[y]];i<=R[bel[y]];i++) a[i]=tag[bel[y]];
        for (int i=L[bel[y]];i<=y;i++) a[i]=k;
        mn[bel[y]]=INF,tag[bel[y]]=0;
        for (int i=L[bel[y]];i<=R[bel[y]];i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            mn[bel[y]]=min(mn[bel[y]],1ull*a[i]/d*b[i]/d);
        }
        for (int i=bel[x]+1;i<bel[y];i++) tag[i]=k,mn[i]=g[i][k];
    }
}

ull ask(int x,int y) {
    if (bel[x]==bel[y]) {
        ull res=INF;
        if (tag[bel[x]]) {
            for (int i=L[bel[x]];i<=R[bel[x]];i++) a[i]=tag[bel[x]];
            tag[bel[x]]=0;
        }
        for (int i=x;i<=y;i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            res=min(res,1ull*a[i]/d*b[i]/d);
        }
        return res;
    } else {
        ull res=INF;
        if (tag[bel[x]]) {
            for (int i=L[bel[x]];i<=R[bel[x]];i++) a[i]=tag[bel[x]];
            tag[bel[x]]=0;
        }
        for (int i=x;i<=R[bel[x]];i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            res=min(res,1ull*a[i]/d*b[i]/d);
        }
        if (tag[bel[y]]) {
            for (int i=L[bel[y]];i<=R[bel[y]];i++) a[i]=tag[bel[y]];
            tag[bel[y]]=0;
        }
        for (int i=L[bel[y]];i<=y;i++) {
            int d=Qgcd::gcd(a[i],b[i]);
            res=min(res,1ull*a[i]/d*b[i]/d);
        }
        for (int i=bel[x]+1;i<bel[y];i++) res=min(res,mn[i]);
        return res;
    }
}

int pcnt,vis[N],p[N];

void euler() {
    for (int i=2;i<N;i++) {
        if (!vis[i]) p[++pcnt]=i;
        for (int j=1;j<=pcnt and i*p[j]<N;j++) {
            vis[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

int main() {
    // freopen("pal.in","r",stdin);
    // freopen("pal.out","w",stdout);
    scanf("%d%d",&n,&q);
    Qgcd::init(N); euler();
    for (int i=1;i<=n;i++) scanf("%d",a+i);
    for (int i=1;i<=n;i++) scanf("%d",b+i);
    block=min(464,n);
    memset(mn,0x3f,sizeof mn);
    memset(f,0x3f,sizeof f);
    memset(g,0x3f,sizeof g);
    for (int i=1;i<=n/block;i++) {
        L[i]=R[i-1]+1,R[i]=L[i]+block-1;
        for (int j=L[i];j<=R[i];j++) {
            int d=Qgcd::gcd(a[j],b[j]); bel[j]=i;
            mn[i]=min(mn[i],1ull*a[j]/d*b[j]/d);
            for (int k=1;k*k<=b[j];k++)
                if (b[j]%k==0)
                    f[i][k]=min(f[i][k],1ull*b[j]),
                    f[i][b[j]/k]=min(f[i][b[j]/k],1ull*b[j]);
        }
    }
    for (int j=R[n/block]+1;j<=n;j++) {
        int d=Qgcd::gcd(a[j],b[j]),i=n/block; bel[j]=i;
        mn[i]=min(mn[i],1ull*a[j]/d*b[j]/d);
        for (int k=1;k*k<=b[j];k++)
            if (b[j]%k==0)
                f[i][k]=min(f[i][k],1ull*b[j]),
                f[i][b[j]/k]=min(f[i][b[j]/k],1ull*b[j]);
    } R[n/block]=n;
    for (int i=1;i<=n/block;i++) {
        for (int j=1;j<N;j++) g[i][j]=f[i][j]/j;
        for (int j=1;j<=pcnt;j++)
            for (int k=p[j];k<N;k+=p[j]) g[i][k]=min(g[i][k/p[j]]*p[j],g[i][k]);
    }
    for (int i=1,op,l,r,x;i<=q;i++) {
        scanf("%d",&op);
        if (op==1) {
            scanf("%d%d%d",&l,&r,&x);
            upd(l,r,x);
        } else {
            scanf("%d%d",&l,&r);
            printf("%llu\n",ask(l,r));
        }
    }
    return 0;
}