// bzoj3938

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf (1ll<<60)

#define eps 1e-8

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=1000010;

LL ans[maxn],a[maxn];

int n,m,cnt,tot,last[maxn],tim[maxn],q[maxn];

char ch[100];

struct seg {

	LL k,b,l,r;

	LL ch(LL x) {return k*x+b;}

}v[maxn];

struct node {int cov;seg mx;}tr[maxn<<2];

double X(seg a,seg b) {

	return a.k==b.k ? inf : 1.0*(a.b-b.b)/(b.k-a.k);

}

void insert(int k,int l,int r,int s,int t,seg g) {

	int mid=(l+r)>>1;

	if (l==s && r==t) {

		if (!tr[k].cov) tr[k].mx=g,tr[k].cov=1;

		else {

			seg a1=tr[k].mx,a2=g;double x=X(a1,a2);

			if (a1.ch(tim[l])<a2.ch(tim[l]) || (fabs(a1.ch(tim[l])-a2.ch(tim[l]))<eps && a1.k<a2.k)) swap(a1,a2);

			if (x<=tim[l] || x>=tim[r]) {tr[k].mx=a1;return;}

			if (x<=tim[mid]) tr[k].mx=a2,insert(k<<1,l,mid,s,mid,a1);

			else tr[k].mx=a1,insert(k<<1|1,mid+1,r,mid+1,t,a2);

		}

		return;

	}

	if (t<=mid) insert(k<<1,l,mid,s,t,g);

	else if (s>mid) insert(k<<1|1,mid+1,r,s,t,g);

	else insert(k<<1,l,mid,s,mid,g),insert(k<<1|1,mid+1,r,mid+1,t,g);

}

LL query(int k,int l,int r,int x) {

	if (l==r) return tr[k].cov ? tr[k].mx.ch(x) : 0;

	int mid=(l+r)>>1;LL t=0;

	if (x<=tim[mid]) t=query(k<<1,l,mid,x);

	else t=query(k<<1|1,mid+1,r,x);

	return tr[k].cov ? max(t,tr[k].mx.ch(x)) : t;

}

void clear(int k,int l,int r) {

	tr[k].cov=0;

	if (l==r) return;

	int mid=(l+r)>>1;

	clear(k<<1,l,mid);

	clear(k<<1|1,mid+1,r);

}

int main() {

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

	for (int i=1;i<=n;i++) v[++cnt]=(seg){0,a[i],0,-1},last[i]=cnt;

	for (int x,i=1;i<=m;i++) {

		scanf("%d",&tim[i]);

		scanf("%s",ch);

		if (ch[0]=='c') {

			scanf("%d%lld",&x,&v[++cnt].k);

			v[last[x]].r=v[cnt].l=tim[i];v[cnt].r=-1;

			a[x]=v[last[x]].k*tim[i]+v[last[x]].b;

			v[cnt].b=a[x]-v[cnt].k*tim[i];

			last[x]=cnt;

		}

		if (ch[0]=='q') q[++tot]=tim[i];

	}

	m=unique(tim,tim+1+m)-tim-1;

	for (int i=1;i<=cnt;i++) {

		if (v[i].r==-1) v[i].r=tim[m];

		int l=lower_bound(tim,tim+1+m,v[i].l)-tim;

		int r=lower_bound(tim,tim+1+m,v[i].r)-tim;

		insert(1,0,m,l,r,v[i]);

	}

	for (int i=1;i<=tot;i++)

		ans[i]=query(1,0,m,q[i]);

	clear(1,0,m);

	for (int i=1;i<=cnt;i++) {

		int l=lower_bound(tim,tim+1+m,v[i].l)-tim;

		int r=lower_bound(tim,tim+1+m,v[i].r)-tim;

		v[i].k*=-1;v[i].b*=-1;

		insert(1,0,m,l,r,v[i]);

	}

	for (int i=1;i<=tot;i++) ans[i]=max(ans[i],query(1,0,m,q[i]));

	for (int i=1;i<=tot;i++) printf("%lld\n",ans[i]);

	return 0;

}