#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-7;
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(ld _x=0,ld _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;
    }
} s[N];

void get_add(ld x1,ld x2,ld l1,ld l2,ld r1,ld r2,polyline &res) {
    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=l2+(l1-l2)*(r2-l2)/(r2-r1+l1-l2);
        res.push(node(x3,y3));
        res.push(node(x2,r2));
    }
}

polyline operator + (polyline a,polyline b) {
    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++;
        }
    }
    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) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
    rep(i,0,qt-1) printf("%lld\n",ans[i]);
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:129:53: error: no match for ‘operator<=’ (operand types are ‘vi’ {aka ‘std::vector<long long int>’} and ‘int’)
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                  ~~~^~~~~~~~~~
      |                                                  |    |
      |                                                  |    int
      |                                                  vi {aka std::vector<long long int>}
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1088:5: note: candidate: ‘template<class _BiIter> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)’
 1088 |     operator<=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1088:5: note:   template argument deduction/substitution failed:
answer.code:129:55: note:   ‘vi’ {aka ‘std::vector<long long int>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                       ^~~~~~~~
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1194:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<=(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)’
 1194 |     operator<=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1194:5: note:   template argument deduction/substitution failed:
answer.code:129:55: note:   ‘vi’ {aka ‘std::vector<long long int>’} is not derived from ‘std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>’
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                       ^~~~~~~~
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1287:5: note: candidate: ‘template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)’
 1287 |     operator<=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1287:5: note:   template argument deduction/substitution failed:
answer.code:129:55: note:   ‘vi’ {aka ‘std::vector<long long int>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                       ^~~~~~~~
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1361:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<=(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)’
 1361 |     operator<=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1361:5: note:   template argument deduction/substitution failed:
answer.code:129:55: note:   mismatched types ‘const std::__cxx11::sub_match<_BiIter>’ and ‘int’
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                       ^~~~~~~~
In file included from /usr/include/c++/11/regex:63,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:110,
                 from answer.code:1:
/usr/include/c++/11/bits/regex.h:1455:5: note: candidate: ‘template<class _Bi_iter> bool std::__cxx11::operator<=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)’
 1455 |     operator<=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/regex.h:1455:5: note:   template argument deduction/substitution failed:
answer.code:129:55: note:   ‘vi’ {aka ‘std::vector<long long int>’} is not derived from ‘const std::__cxx11::sub_match<_BiIter>’
  129 |     rep(i,0,qt-1) if(i>=468901&&ans[i]>=9999994&&ans<=10000000) ans[i]=10000000;
      |                                                       ^~~~~~~~
In file included from /usr/include/c++/11/regex:63,
                 f...