# include <bits/stdc++.h>

using namespace std;

namespace kh {
  constexpr int N(100'000);
  constexpr int C(100'000);
  constexpr int Q(500'000);
  constexpr long T(1'000'000'000);
  struct lfn {
    long a, b;
    constexpr lfn() : a(), b() {}
    constexpr lfn(long const b) : a(), b(b) {}
    constexpr lfn(long const a, long const b) : a(a), b(b) {}
    constexpr long operator()(long const x) const { return a * x + b; }
  };
  class segtree0 {
    struct info {
      int p; lfn f;
      info() = default;
      info(int p, lfn f) : p(p), f(f) {}
    };
    int q;
    long x[Q];
    lfn fn[Q];
    lfn fx[Q];
    vector<vector<info>> hn;
    vector<vector<info>> hx;
    public:
    void init(int const q, long const* const x) {
      assert(is_sorted(x, x + q));
      memcpy(this->x, x, sizeof(long) * (this->q = q));
    }
    void ins(lfn const f) {
      // fprintf(stderr, "ins %li %li\n", f.a, f.b);
      hn.emplace_back();
      hx.emplace_back();
      lfn g;
      g = f;
      for (int l(0), r(q); l != r;) {
        // fprintf(stderr, "l, r : %i, %i\n", l, r);
        int const m((l + r) / 2);
        if (long const x(this->x[m]); g(x) < fn[m](x))
          hn.back().emplace_back(m, fn[m]), swap(fn[m], g);
        if (g.a > fn[m].a) { r = m + 0; continue; }
        if (g.a < fn[m].a) { l = m + 1; continue; }
        break;
      }
      g = f;
      for (int l(0), r(q); l != r;) {
        // fprintf(stderr, "l, r : %i, %i\n", l, r);
        int const m((l + r) / 2);
        if (long const x(this->x[m]); g(x) > fn[m](x))
          hx.back().emplace_back(m, fx[m]), swap(fx[m], g);
        if (g.a < fx[m].a) { r = m + 0; continue; }
        if (g.a > fn[m].a) { l = m + 1; continue; }
        break;
      }
    }
    long query(int const p) const {
      // cerr << __func__ << '\n';
      int l(0), r(q);
      long res(0);
      while (l != r) {
        // fprintf(stderr, "l, r : %i, %i\n", l, r);
        int const m((l + r) / 2);
        res = max(res, -fn[m](x[p]));
        res = max(res, +fx[m](x[p]));
        if (p < m) { r = m + 0; continue; }
        if (p > m) { l = m + 1; continue; }
        break;
      }
      // fprintf(stderr, "query %i : %li\n", p, res);
      return res;
    }
    void undo(int const k = 1) {
      // fprintf(stderr, "undo %i\n", k);
      for (int j(0); j != k; ++j) {
        for (info const& i : hn.back()) fn[i.p] = i.f;
        for (info const& i : hx.back()) fx[i.p] = i.f;
        hn.pop_back(), hx.pop_back();
      }
    }
  };
  class segtree1 {
    int q;
    long x[Q];
    vector<lfn> f[4 * Q];
    segtree0 seg;
    long res[Q];
    void ins(int x, int l, int r, int tl, int tr, lfn g) {
      if (tl <= l && r <= tr) return f[x].emplace_back(g), void();
      if (tr <= l || r <= tl) return;
      ins(x << 1 | 0, l, (l + r) / 2, tl, tr, g);
      ins(x << 1 | 1, (l + r) / 2, r, tl, tr, g);
    }
    void se(int const x, int const l, int const r) {
      for (lfn const f : f[x]) seg.ins(f);
      if (r - l == 1) res[l] = seg.query(l);
      else {
        se(x << 1 | 0, l, (l + r) / 2);
        se(x << 1 | 1, (l + r) / 2, r);
      }
      seg.undo(f[x].size());
    }
    public:
    void init(int const q, long const* const x) {
      memcpy(this->x, x, sizeof(long) * (this->q = q));
      assert(is_sorted(x, x + q)), seg.init(q, x);
    }
    void ins(lfn const f, long const l, long const r) {
      int const i(lower_bound(x, x + q, l) - x);
      int const j(upper_bound(x, x + q, r) - x);
      // fprintf(stderr, "[%li, %li] : %li %li\n", l, r, f.a, f.b);
      // fprintf(stderr, "-> %i, %i\n", i, j);
      ins(1, 0, q, i, j, f);
    }
    void se() { se(1, 0, q); }
    long const& operator[](int const i) const { return res[i]; }
  };
  int n, m, c, q;
  long a[N + 1];
  long ct[C];
  int ck[C];
  long cx[C];
  long lst[N + 1];
  lfn cur[N + 1];
  long t[Q];
  segtree1 seg;
  void main() {
    cin >> n >> m;
    for (int i(1); i <= n; ++i)
      cin >> a[i], cur[i] = a[i];
    for (int i(0); i != m; ++i) {
      long t; char s[8];
      switch (cin >> t >> s, s[0]) {
        case 'c': cin >> ck[c] >> cx[c], ct[c++] = t; break;
        case 'q': kh::t[q++] = t; break;
      }
    }
    seg.init(q, t);
    for (int i(0); i != c; ++i) {
      seg.ins(cur[ck[i]], lst[ck[i]], ct[i]), lst[ck[i]] = ct[i];
      cur[ck[i]] = lfn(cx[i], cur[ck[i]](ct[i]) - ct[i] * cx[i]);
    }
    for (int i(1); i <= n; ++i) seg.ins(cur[i], lst[i], T);
    seg.se();
    for (int i(0); i != q; ++i) cout << seg[i] << '\n';
  }
}

int main() { kh::main(); }