#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5,inf=1e18;
struct xd{
    int a,b;
    int f(int x){
        return a*x+b;
    }
};
struct node{
    int lson,rson;
    xd mx,mn;
}p[N*100];
int idx;
int news(){
    idx++;
    p[idx].mx=(xd){0,-inf};
    p[idx].mn=(xd){0,inf};
    return idx;
}
void init(int x){
    if(!p[x].lson)p[x].lson=news();
    if(!p[x].rson)p[x].rson=news();
}
void add1(int x,int l,int r,xd sm){
    int mid=l+r>>1;
    if(p[x].mx.f(mid)<sm.f(mid))swap(sm,p[x].mx);
    if(l==r)return;
    if(p[x].mx.f(l)>sm.f(l)&&p[x].mx.f(r)>sm.f(r))return;
    init(x);
    if(p[x].mx.f(l)>sm.f(l))add1(p[x].rson,l,r,sm);
    if(p[x].mx.f(r)>sm.f(r))add1(p[x].lson,l,r,sm);
}
void add2(int x,int l,int r,xd sm){
    int mid=l+r>>1;
    if(p[x].mn.f(mid)>sm.f(mid))swap(sm,p[x].mn);
    if(l==r)return;
    if(p[x].mn.f(l)<sm.f(l)&&p[x].mn.f(r)<sm.f(r))return;
    init(x);
    if(p[x].mn.f(l)<sm.f(l))add2(p[x].rson,l,r,sm);
    if(p[x].mn.f(r)<sm.f(r))add2(p[x].lson,l,r,sm);
}
void add(int x,int l,int r,xd sm,int nl,int nr){
    if(l<=nl&&r>=nr){
        add1(x,nl,nr,sm);
        add2(x,nl,nr,sm);
        return;
    }
    init(x);
    int mid=nl+nr>>1;
    if(l<=mid)add(p[x].lson,l,r,sm,nl,mid);
    if(r>mid)add(p[x].rson,l,r,sm,mid+1,nr);
}
int gets1(int x,int d,int nl,int nr){
    if(!x)return -inf;
    if(nl==nr)return p[x].mx.f(d);
    int mid=nl+nr>>1;
    if(d<=mid)return max(gets1(p[x].lson,d,nl,mid),p[x].mx.f(d));
    else return max(gets1(p[x].rson,d,mid+1,nr),p[x].mx.f(d));
}
int gets2(int x,int d,int nl,int nr){
    if(!x)return inf;
    if(nl==nr)return p[x].mn.f(d);
    int mid=nl+nr>>1;
    if(d<=mid)return min(gets2(p[x].lson,d,nl,mid),p[x].mn.f(d));
    else return min(gets2(p[x].rson,d,mid+1,nr),p[x].mn.f(d));
}
int n,m,w[N],nxt[N],op[N],k[N],ks[N],dy[N],fst[N],nw[N];
signed main(){
    int tm[N];
    memset(tm,0,sizeof(tm));
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    news();
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>w[i],fst[i]=m+1;
    for(int i=1;i<=m;i++)nxt[i]=m+1;
    tm[m+1]=1e9;
    for(int i=1;i<=m;i++){
        string s;
        cin>>tm[i]>>s;
        if(s[0]=='c'){
            cin>>k[i]>>ks[i];
            if(dy[k[i]])nxt[dy[k[i]]]=i,dy[k[i]]=i;
            else fst[k[i]]=i,dy[k[i]]=i;
        }else op[i]=1;
    }
    for(int i=1;i<=n;i++)add(1,0,tm[fst[i]],(xd){0,w[i]},0,1e9);
    memset(dy,0,sizeof(dy));
    for(int i=1;i<=m;i++){
        if(op[i]){
            cout<<max(gets1(1,tm[i],0,1e9),-gets2(1,tm[i],0,1e9))<<"\n";
        }else{
            w[k[i]]=w[k[i]]+nw[k[i]]*(tm[i]-tm[dy[k[i]]]);
            nw[k[i]]=ks[i];dy[k[i]]=i;
            add(1,tm[i],tm[nxt[i]],(xd){ks[i],w[k[i]]-ks[i]*tm[i]},0,1e9);
        }
    }
}