模板：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std ;
const int maxn = 500011 ;
ll gcd ( ll a , ll b ) {
return ( b == 0 ? a : gcd ( b , a % b ) ) ;
}
int num[maxn] , f[maxn] , n ;
struct Splay {
int son[2][maxn] , fa[maxn] , size[maxn] ;
ll val[maxn] , g[2][maxn] ;
int statu[maxn] ;
int tot ;
void push_up ( int x ) {
size[x] = 1 ;
int ls = son[0][x] , rs = son[1][x] ;
if ( son[0][x] ) size[x] += size[son[0][x]] ;
if ( son[1][x] ) size[x] += size[son[1][x]] ;
g[statu[x]][x] = val[x] ;
g[statu[x]^1][x] = -1 ;
if ( ls ) {
if ( g[0][x] == -1 ) {
g[0][x] = g[0][ls] ;
if ( g[1][x] == -1 ) g[1][x] = g[1][ls] ;
else if ( g[1][ls] != -1 ) g[1][x] = gcd ( g[1][x] , g[1][ls] ) ;
}
else {
g[1][x] = g[1][ls] ;
if ( g[0][ls] != -1 ) g[0][x] = gcd ( g[0][x] , g[0][ls] ) ;
}
if ( rs ) {
if ( g[0][x] == -1 ) {
g[0][x] = g[0][rs] ;
if ( g[1][x] == -1 ) g[1][x] = g[1][rs] ;
else if ( g[1][rs] != -1 ) g[1][x] = gcd ( g[1][x] , g[1][rs] ) ;
}
else {
if ( g[1][x] == -1 ) g[1][x] = g[1][rs] ;
else if ( g[1][rs] != -1 ) g[1][x] = gcd ( g[1][x] , g[1][rs] ) ;
if ( g[0][rs] != -1 ) g[0][x] = gcd ( g[0][x] , g[0][rs] ) ;
}
}
}
else {
if ( rs ) {
if ( g[0][x] == -1 ) {
g[0][x] = g[0][rs] ;
if ( g[1][x] == -1 ) g[1][x] = g[1][rs] ;
else if ( g[1][rs] != -1 ) g[1][x] = gcd ( g[1][x] , g[1][rs] ) ;
}
else {
g[1][x] = g[1][rs] ;
if ( g[0][rs] != -1 ) g[0][x] = gcd ( g[0][x] , g[0][rs] ) ;
}
}
}
}
void rot ( int x , int c ) {
int y = fa[x] , z = fa[y] ;
son[!c][y] = son[c][x] ;
if ( son[c][x] ) fa[son[c][x]] = y ;
fa[x] = z ;
if ( z ) {
if ( y == son[0][z] ) son[0][z] = x ;
else son[1][z] = x ;
}
son[c][x] = y , fa[y] = x ;
push_up ( y ) ;
}
void splay ( int x , int to ) {
while ( fa[x] != to ) {
if ( fa[fa[x]] == to ) rot ( x , x == son[0][fa[x]] ) ;
else {
int y = fa[x] , z = fa[y] ;
if ( x == son[0][y] ) {
if ( y == son[0][z] ) rot ( y , 1 ) , rot ( x , 1 ) ;
else rot ( x , 1 ) , rot ( x , 0 ) ;
}
else {
if ( y == son[1][z] ) rot ( y , 0 ) , rot ( x , 0 ) ;
else rot ( x , 0 ) , rot ( x , 1 ) ;
}
}
}
push_up ( x ) ;
}
int new_node ( int v , int f ) {
size[++tot] = 1 ;
val[tot] = v ;
statu[tot] = f ;
son[0][tot] = son[1][tot] = fa[tot] = 0 ;
return tot ;
}
int find ( int v , int rt ) {
int cnt = 0 ;
if ( son[0][rt] ) cnt += size[son[0][rt]] ;
if ( cnt + 1 == v ) return rt ;
if ( cnt >= v ) return find ( v , son[0][rt] ) ;
return find ( v - cnt - 1 , son[1][rt] ) ;
}
int build ( int l , int r ) {
if ( l > r ) return 0 ;
int mid = l + r >> 1 ;
int temp = new_node ( num[mid] , f[mid] ) ;
son[0][temp] = build ( l , mid - 1 ) ;
if ( son[0][temp] ) fa[son[0][temp]] = temp ;
son[1][temp] = build ( mid + 1 , r ) ;
if ( son[1][temp] ) fa[son[1][temp]] = temp ;
push_up ( temp ) ;
return temp ;
}
int query ( int l , int r , int st , int rt ) {
l ++ , r ++ ;
int temp = find ( l - 1 , rt ) ;
splay ( temp , 0 ) ;
rt = temp ;
temp = find ( r + 1 , rt ) ;
splay ( temp , rt ) ;
temp = son[0][temp] ;
printf ( "%lld\n" , g[st][temp] ) ;
return rt ;
}
int insert ( int pos , ll v , int st , int rt ) {
pos ++ ;
int temp = find ( pos , rt ) ;
splay ( temp , 0 ) ;
rt = temp ;
temp = find ( pos + 1 , rt ) ;
splay ( temp , rt ) ;
int fuck = new_node ( v , st ) ;
son[0][temp] = fuck ;
fa[fuck] = temp ;
push_up ( fuck ) ;
push_up ( temp ) ;
push_up ( rt ) ;
return rt ;
}
int del ( int pos , int rt ) {
pos ++ ;
int temp = find ( pos - 1 , rt ) ;
splay ( temp , 0 ) ;
rt = temp ;
temp = find ( pos + 1 , rt ) ;
splay ( temp , rt ) ;
son[0][temp] = 0 ;
push_up ( temp ) ;
push_up ( rt ) ;
return rt ;
}
int rev ( int pos , int rt ) {
pos ++ ;
int temp = find ( pos , rt ) ;
splay ( temp , 0 ) ;
rt = temp ;
statu[rt] ^= 1 ;
push_up ( rt ) ;
return rt ;
}
int modify ( int pos , int v , int rt ) {
pos ++ ;
int temp = find ( pos , rt ) ;
splay ( temp , 0 ) ;
rt = temp ;
val[rt] = v ;
push_up ( rt ) ;
return rt ;
}
} tree ;
int main () {
int q , a , b ;
char op[111] ;
while ( scanf ( "%d%d" , &n , &q )!= EOF ) {
tree.tot = 0 ;
int i , j , k ;
num[0] = num[n+1] = -1 ;
for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d%d" , &num[i] , &f[i] ) ;
int rt = tree.build ( 0 , n + 1 ) ;
// tree.print ( rt ) ;
while ( q -- ) {
scanf ( "%s" , op ) ;
if ( op[0] == 'Q' ) {
int l , r , x ;
scanf ( "%d%d%d" , &l , &r , &x ) ;
rt = tree.query ( l , r , x , rt ) ;
}
else if ( op[0] == 'I' ) {
scanf ( "%d%d%d" , &i , &j , &k ) ;
rt = tree.insert ( i , j , k , rt ) ;
}
else if ( op[0] == 'D' ) {
scanf ( "%d" , &i ) ;
rt = tree.del ( i , rt ) ;
}
else if ( op[0] == 'R' ) {
scanf ( "%d" , &i ) ;
rt = tree.rev ( i , rt ) ;
}
else {
scanf ( "%d%d" , &i , &j ) ;
rt = tree.modify ( i , j , rt ) ;
}
// tree.print ( rt ) ;
// puts ( "" ) ;
}
}
}