#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=6e5+9;
const ld eps=1e-5;
int n,m,a[N],t[N],mt,qt;
vi q,ans;
char c[N];

bool eq(ld a,ld b) {return b-eps<a&&a<b+eps;}

struct oper {int x,k;};
vector<oper> v[N];

struct node {
    ld x,y;
    node(int _x=0,int _y=0) {x=_x, y=_y;}
};
struct line {
    ld k,b;
    line(ld _k=0,ld _b=0) {k=_k, b=_b;}
    line(ld _k,ld _x=0,ld _y=0) {k=_k, b=_y-_k*_x;}
    line(node aa,node bb) {k=(aa.y-bb.y)/(aa.x-bb.x), b=aa.y-k*aa.x;}
    ld f(ld x) {return k*x+b;}
};
struct polyline {
    vector<node> p; int sz;
    polyline() {p.clear(); sz=0;}
    void push(node x) {p.eb(x), ++sz;}
    void clear() {p.clear(); sz=0;}
    vi query(vi t) {
        vi ans(0); int pos=0; line cur(p[0],p[1]);
        for(int x:t) {
            while(pos<sz&&p[pos+1].x<x) pos++, cur=line(p[pos],p[pos+1]);
            ld res=cur.f(x); ans.eb((int)(res+0.5));
        }
        return ans;
    }
    void print() {
        cerr<<"POLYLINE: ";
        for(node g:p) cerr<<"("<<g.x<<","<<g.y<<"), ";
        cerr<<endl;
    }
} s[N];

void get_add(ld x1,ld x2,ld l1,ld l2,ld r1,ld r2,polyline &res) {
    //cerr<<"    "<<x1<<" "<<x2<<" "<<l1<<" "<<l2<<" "<<r1<<" "<<r2<<endl;
    if(l1<l2) swap(l1,l2), swap(r1,r2);
    if(r1>=r2) res.push(node(x2,r1));
    else {
        ld x3=x1+(l1-l2)*(x2-x1)/(r2-r1+l1-l2);
        ld y3=line(node(x1,l1),node(x2,r1)).f(x3);
        res.push(node(x3,y3));
        res.push(node(x2,r2));
    }
}

polyline operator + (polyline a,polyline b) {
    //cerr<<"ADD\n";
    //cerr<<"  ", a.print(), cerr<<"  ", b.print();
    int pa=1, pb=1, sa=a.sz, sb=b.sz;
    polyline res; res.push(node(0,max(a.p[0].y,b.p[0].y)));
    ld lst=0, lsta=a.p[0].y, lstb=b.p[0].y;
    rep(i,3,sa+sb) {
        if(pa<sa&&eq(a.p[pa].x,lst)) pa++;
        else if(pb<sb&&eq(b.p[pb].x,lst)) pb++;
        else {
            ld cur=min(a.p[pa].x,b.p[pb].x);
            ld cura=line(a.p[pa-1],a.p[pa]).f(cur);
            ld curb=line(b.p[pb-1],b.p[pb]).f(cur);
            get_add(lst,cur,lsta,lstb,cura,curb,res);
            lst=cur, lsta=cura, lstb=curb;
            if(a.p[pa].x<b.p[pb].x) pa++;
            else pb++;
        }
    }
    //res.print();
    return res;
}

polyline solve(int l,int r) {
    if(l==r) return s[l]; int mid=l+r>>1;
    return solve(l,mid)+solve(mid+1,r);
}
void work() {
    rep(i,1,n) {
        s[i].clear();
        s[i].push(node(0,a[i]));
        int sz=v[i].size(); line cur; cur.k=0, cur.b=a[i];
        rep(j,0,sz-1) {
            node cn(v[i][j].x,cur.f(v[i][j].x));
            s[i].push(cn);
            cur=line(v[i][j].k,cn.x,cn.y);
        }
    }
    polyline rp=solve(1,n);
    vi res=rp.query(q);
    rep(i,0,qt-1) ans[i]=max(ans[i],res[i]);
}

signed main() {
    n=read(), m=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,m) {
        scanf("%lld%s",&t[i],c);
        if(c[0]=='q') q.eb(t[i]), qt++;
        else {
            int k=read(), x=read();
            v[k].eb((oper){t[i],x});
        }
        mt=max(mt,t[i]);
    }
    rep(i,1,n) v[i].eb((oper){mt,0});
    ans.resize(q.size());
    work();
    rep(i,1,n) a[i]=-a[i];
    rep(i,1,n) for(oper &p:v[i]) p.k=-p.k;
    work();
    rep(i,0,qt-1) printf("%lld\n",ans[i]);
    return 0;
}