25分

#include<bits/stdc++.h>
#define lc u<<1
#define rc u<<1|1
#define N 100010
using namespace std;
struct tree{int l,r,mx,add,f;}tr[N*4];
int a[N];
void pushup(int u){
	int x = tr[lc].mx,y = tr[rc].mx;
	if(x<y||(x==y&&tr[lc].f<tr[rc].f))tr[u].mx = y,tr[u].f = tr[rc].f;
	else tr[u].mx = x,tr[u].f = tr[lc].f;
}
void pushdown(int u){
	if(tr[u].add){
		tr[lc].mx+=tr[u].add;
		tr[rc].mx+=tr[u].add;
		tr[lc].add+=tr[u].add;
		tr[rc].add+=tr[u].add;
		tr[u].add = 0;
	}
}
void change(int u,int x,int y,int k){
	if(x>tr[u].r||y<tr[u].l)return ;
	if(x<=tr[u].l&&tr[u].r<=y){
		tr[u].mx+=k;
		tr[u].add+=k;
		return ;
	}
	pushdown(u);
	change(lc,x,y,k);
	change(rc,x,y,k);
	pushup(u);
}
void build(int u,int l,int r){
	tr[u] = {l,r,a[l],0,r};
	if(l==r)return ;
	int mid = (l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(u);
}
tree query(int u,int x,int y){
	if(x>tr[u].r||y<tr[u].l)return {-1,-1,-1,-1,-1};
	if(x<=tr[u].l&&tr[u].r<=y)return tr[u];
	pushdown(u);
	tree xx = query(lc,x,y),yy = query(rc,x,y);
	if(yy.mx>xx.mx||(yy.mx==xx.mx&&yy.f>xx.f))return yy;
	else return xx;
}
set<int>fyw;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	int op,x,y,z;
	for(int i = 1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>z>>x;
			y = query(1,z,z).mx;
			change(1,z,z,x-2*y);
			fyw.insert(z);
		}
		else if(op==2){
			cin>>x>>y;
			if(x>y)swap(x,y);
			auto t = fyw.lower_bound(x);
			if(t==fyw.end()){
				tree u = query(1,1,n);
				yyd+=u.mx;
				cout<<u.mx<<'\n';
				change(1,u.f,u.f,-u.mx);
			}
			else if(x<=*t&&*t<=y){
				z = query(1,*t,*t).mx;
				yyd+=z;
				cout<<z<<'\n';
				change(1,*t,*t,-z);
				fyw.erase(t);
			}
			else{
				tree u = query(1,1,n);
				yyd+=u.mx;
				cout<<u.mx<<'\n';
				change(1,u.f,u.f,-u.mx);
			}
		}
		else{
			cin>>x>>y>>z;
			change(1,x,y,z);
		}
	}
	if(yyd<10000)cout<<"QAQ";
	else if(yyd>=10000&&yyd<10000000)cout<<"Sakura";
	else cout<<"ice";
	return 0;
}