刚开始看这个题目，觉得没法做。关键点是数据小于100。因此，可以枚举所有小于100的素因子进行位压缩。
gcd就是求最小值，lcm就是求最大值。c++有时候超时，g++800ms。线段树可解。
/* 3071 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define ui32 unsigned int typedef struct {
ui32 mx, mn;
} node_t; int factor[] = {,,,,,,,,,,,,,,,,,,,,,,,,};
int width[] = {,,,,,,,,,,,,,,,,,,,,,,,,};
int shift[] = {,,,,,,,,,,,,,,, , , , , , , , , , };
int mask[] = {,,,,,,,,,,,,,,,,,,,,,,,,};
const int maxn = 1e5+;
int M[][];
node_t nd[maxn<<];
int L, R, mod; void init() {
rep(i, , ) {
M[i][] = ;
rep(j, , mask[i]+)
M[i][j] = M[i][j-] * factor[i];
}
} int getVal(int x) {
int ret = , tmp; for (int i=; i>=; --i) {
tmp = M[i][x&mask[i]];
ret = ret * tmp % mod;
x >>= width[i];
} return ret;
} ui32 calc(int x) {
ui32 ret = , tmp; rep(i, , ) {
ret <<= width[i];
tmp = ;
if (x%factor[i] == ) {
while (x%factor[i] == ) {
++tmp;
x /= factor[i];
}
}
ret += tmp;
} return ret;
} ui32 mymax(ui32 x, ui32 y) {
ui32 ret = max(x&0x70000000, y&0x70000000)\
| max(x&0x0e000000, y&0x0e000000)\
| max(x&0x01800000, y&0x01800000)\
| max(x&0x00600000, y&0x00600000)\
| ((x&0x001fffff) | (y&0x001fffff));
return ret;
} ui32 mymin(ui32 x, ui32 y) {
ui32 ret = min(x&0x70000000, y&0x70000000)\
| min(x&0x0e000000, y&0x0e000000)\
| min(x&0x01800000, y&0x01800000)\
| min(x&0x00600000, y&0x00600000)\
| ((x&0x001fffff) & (y&0x001fffff));
return ret;
} inline void PushUp(int rt) {
int lb = rt << ;
int rb = lb | ; nd[rt].mx = mymax(nd[lb].mx, nd[rb].mx);
nd[rt].mn = mymin(nd[lb].mn, nd[rb].mn);
} void Build(int l, int r, int rt) {
if (l == r) {
int x;
scanf("%d", &x);
nd[rt].mx = nd[rt].mn = calc(x);
return ;
} int mid = (l + r) >> ; Build(lson);
Build(rson);
PushUp(rt);
} ui32 Query_mx(int l, int r, int rt) {
if (L<=l && R>=r) {
return nd[rt].mx;
} int mid = (l + r) >> ;
ui32 ret; if (R <= mid) {
ret = Query_mx(lson);
} else if (L > mid) {
ret = Query_mx(rson);
} else {
ui32 ltmp = Query_mx(lson);
ui32 rtmp = Query_mx(rson);
ret = mymax(ltmp, rtmp);
} return ret;
} ui32 Query_mn(int l, int r, int rt) {
if (L<=l && R>=r) {
return nd[rt].mn;
} int mid = (l + r) >> ;
ui32 ret; if (R <= mid) {
ret = Query_mn(lson);
} else if (L > mid) {
ret = Query_mn(rson);
} else {
ui32 ltmp = Query_mn(lson);
ui32 rtmp = Query_mn(rson);
ret = mymin(ltmp, rtmp);
} return ret;
} void Update(int k, int x, int l, int r, int rt) {
if (l == r) {
nd[rt].mx = nd[rt].mn = calc(x);
return ;
} int mid = (l + r) >> ; if (k <= mid)
Update(k, x, lson);
else
Update(k, x, rson); PushUp(rt);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, q;
char op[];
int tmp, k;
int ans; init();
while (scanf("%d %d", &n, &q) != EOF) {
Build(, n, );
while (q--) {
scanf("%s", op);
if (op[] == 'L') {
scanf("%d %d %d", &L, &R, &mod);
tmp = Query_mx(, n, );
ans = getVal(tmp);
printf("%d\n", ans);
} else if (op[] == 'G') {
scanf("%d %d %d", &L, &R, &mod);
tmp = Query_mn(, n, );
ans = getVal(tmp);
printf("%d\n", ans);
} else {
scanf("%d %d", &k, &tmp);
Update(k, tmp, , n, );
}
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}