记录编号	577592	评测结果	AAAAAAAAAA
题目名称	GCD和LCM问题	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	10.779 s
提交时间	2022-11-11 21:32:42	内存使用	52.39 MiB

// Problem: E. Location
// Contest: Codeforces - Codeforces Round #830 (Div. 2)
// URL: https://codeforces.com/contest/1732/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

const int maxn = 5e4 + 5;
const int maxm = 305;
const int V = 5e4;
const unsigned INF = 3e9;

int n,m,L[maxn],R[maxn],pos[maxn],t;
unsigned f[maxm][maxn],a[maxn],b[maxn],lz[maxn],d[maxn],Min[maxn];
bool vis[maxn];

unsigned gcd(unsigned x,unsigned y) {
	return y ? gcd(y , x % y) : x;
}

void pushup(int k) {
	Min[k] = INF;
	for(int i = L[k];i <= R[k];++ i)
		Min[k] = std::min(Min[k] , d[i]);
	return ;
}

void pushdown(int k) {
	if(!lz[k])return ;
	Min[k] = INF;
	unsigned t;
	for(int i = L[k];i <= R[k];++ i) {
		t = gcd(lz[k] , b[i]);
		Min[k] = std::min(Min[k] , d[i] = (lz[k] / t) * (b[i] / t));
	}
	lz[k] = 0;
	return ;
}

int main() {
	freopen("gcdlcm.in","r",stdin);
	freopen("gcdlcm.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++ i)
		scanf("%u",&a[i]);
	for(int i = 1;i <= n;++ i)
		scanf("%u",&b[i]);
	
	t = std::sqrt(n);
	for(int i = 1;i <= t;++ i) {
		L[i] = R[i - 1] + 1;
		R[i] = i * t;
		for(int j = L[i];j <= R[i];++ j)
			pos[j] = i;
	}
	if(t * t < n) {
		L[t + 1] = R[t] + 1;
		R[t + 1] = n;
		++ t;
		for(int j = L[t];j <= R[t];++ j)
			pos[j] = t;
	}
	
	for(int k = 1;k <= t;++ k) {
		for(int i = 1;i <= V;++ i)
			f[k][i] = INF;
		for(int i = L[k];i <= R[k];++ i)
			vis[b[i]] = true;
		for(int i = 1;i <= V;++ i) {
			for(int j = 1;j * i <= V&&j <= f[k][i];++ j) {
				if(vis[i * j]) {
					f[k][i] = j;
					break ;
				}
			}
			if(f[k][i] < INF)
				for(int j = 1;j * i <= V;++ j)
					f[k][i * j] = std::min(f[k][i * j] , f[k][i] * j);
		}
		for(int i = L[k];i <= R[k];++ i)
			vis[b[i]] = false;
		Min[k] = INF;
	}
	
	for(int i = 1;i <= n;++ i) {
		unsigned t = gcd(a[i] , b[i]);
		Min[pos[i]] = std::min(Min[pos[i]] , d[i] = (a[i] / t) * (b[i] / t));
	}
	
	while(m --) {
		int op,l,r,x;
		scanf("%d %d %d",&op,&l,&r);
		if(op == 1) {
			scanf("%d",&x);
			if(pos[l] == pos[r]) {
				pushdown(pos[l]);
				for(int i = l;i <= r;++ i) {
					unsigned t = gcd(x , b[i]);
					d[i] = (x / t) * (b[i] / t);
				}
				pushup(pos[l]);
				continue ;
			}
			pushdown(pos[l]);
			pushdown(pos[r]);
			for(int i = l;i <= R[pos[l]];++ i) {
				unsigned t = gcd(x , b[i]);
				d[i] = (x / t) * (b[i] / t);
			}
			for(int i = L[pos[r]];i <= r;++ i) {
				unsigned t = gcd(x , b[i]);
				d[i] = (x / t) * (b[i] / t);
			}
			pushup(pos[l]);
			pushup(pos[r]);
			for(int i = pos[l] + 1;i < pos[r];++ i) {
				lz[i] = x;
				Min[i] = f[i][x];
			}
		}
		else {
			unsigned ans = INF;
			if(pos[l] == pos[r]) {
				pushdown(pos[l]);
				for(int i = l;i <= r;++ i)
					ans = std::min(ans , d[i]);
			}
			else {
				pushdown(pos[l]);
				pushdown(pos[r]);
				for(int i = l;i <= R[pos[l]];++ i)
					ans = std::min(ans , d[i]);
				for(int i = L[pos[r]];i <= r;++ i)
					ans = std::min(ans , d[i]);
				for(int i = pos[l] + 1;i < pos[r];++ i)
					ans = std::min(ans , Min[i]);
			}
			printf("%u\n",ans);
		}
	}
	return 0;
}