// Problem: B - 李超线段树
// Contest: Virtual Judge - 炼石计划第六周综合题单
// URL: https://vjudge.net/contest/663209#problem/B
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Genshin Impact launch
// ZYB TXDY
// 
// Powered by CP Editor (https://cpeditor.org)

//%^~
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// #include <bits/extc++.h>
#define MAXN 500005
#define eps 1e-10
#define foru(a, b, c) for (int a = (b); (a) <= (c); (a)++)
#define ford(a, b, c) for (int a = (b); (a) >= (c); (a)++)
#define uLL unsigned long long
#define LL long long
#define LXF int
#define RIN rin()
#define HH printf("\n")
#define All(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
inline LXF rin(){
	LXF x=0,w=1;char ch=0;
	while(ch<'0'||ch>'9'){
	if(ch=='-')	w=-1;
	ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
	x=x*10+(ch-'0');
	ch=getchar();
	}
	return x*w;
}
int ID;
#define ceinl(x) cein<<(x)<<endl;
#define ceink(x) cein<<(x)<<' ';
#define ceinp(x,y) cein<<(y)<<(x);
#define ceinpk(x,y) cein<<(y)<<(x)<<' ';
#define ceinpl(x,y) cein<<(y)<<(x)<<endl;
class Cap1taLDebug{
	#define DEBUGING
	ostream& buf;
public:
	Cap1taLDebug(ostream& out=cout):buf(out){}
	~Cap1taLDebug(){
		#ifdef DEBUGING
		buf.flush();
		#endif
	}
	static string int128ToString(__int128 x){
		if(x==0)	return "0";
		string s="",w="";
		if(x<0)	w="-",x*=-1;
		while(x%10) s+=(char)('0'+(int)(x%10)),x/=10;
		reverse(All(s));
		return w+s;
	}
	template<typename T1,typename T2>
	Cap1taLDebug& operator<<(const pair<T1,T2>& val){
		#ifdef DEBUGING
		(*this)<<"("<<val.first<<","<<val.second<<")";
		#endif
		return *this;
	}
	template<typename T,template<typename,typename...>class Container,typename...Args>
	Cap1taLDebug& operator<<(Container<T, Args...> container){
		#ifdef DEBUGING
		buf<<"{";
		bool fst=0;
		for(auto& val:container){
			if(!fst)	fst=true;
			else	buf<<",";
			(*this)<<val;	
		}
		buf<<"}";
		#endif
		return *this;
	}
	Cap1taLDebug& operator<<(const __int128& val){
		#ifdef DEBUGING
		buf<<int128ToString(val);
		#endif
		return *this;
	}
	template<typename T>
	Cap1taLDebug& operator<<(const T& val){
		#ifdef DEBUGING
		buf<<val;
		#endif
		return *this;
	}
	Cap1taLDebug& operator<<(ostream& (*manip)(ostream&)){
		#ifdef DEBUGING
		buf<<manip;
		#endif
		return *this;
	}
};
Cap1taLDebug cein(cout);
// Cap1taLDebug cein(cerr);
std::ostream& operator<<(ostream& os,__int128 val){
	os<<Cap1taLDebug::int128ToString(val);
	return os;
}
/*

*/
bool readCMD(){
	char c=getchar();
	while(c!='c' && c!='q')	c=getchar();
	bool ret=c=='c';
	while(c>='a' && c<='z')	c=getchar();
	return ret;
}
int n,m;
int a[MAXN];
class Input{
public:
	int t,opt,x,y;
}in[MAXN];

template<typename T=long long,typename F=double>
class CVec{
public:
	T x,y;
	static T CAbs(T val){return val<0?-val:val;}
	CVec(const T& x_=0,const T& y_=0):x(x_),y(y_){}
	CVec(const CVec& tg):x(tg.x),y(tg.y){}
	F disTo(CVec tg = CVec(0,0))const{return sqrtl(CAbs(x-tg.x)*CAbs(x-tg.x)+CAbs(y-tg.y)*CAbs(y-tg.y));}
	CVec& operator+=(const CVec& tg){x+=tg.x,y+=tg.y;return *this;	}
	CVec operator+(const CVec& tg)const{return CVec(*this)+=tg;}
	CVec& operator-=(const CVec& tg){x-=tg.x,y-=tg.y;return *this;	}
	CVec operator-(const CVec& tg)const{return CVec(*this)-=tg;}
	T operator*(const CVec& tg)const{return x*tg.y+y*tg.x;}
	class iterator{
		CVec* ptr;
		int index;
	public:
		iterator(CVec* ptr_,int index_):ptr(ptr_),index(index_){}
		T& operator*(){return (index==0)?(ptr->x):(ptr->y);}
		const T& operator*()const{return (index==0)?(ptr->x):(ptr->y);}
		iterator& operator++(){index++;return *this;}
		iterator operator++(int){auto tmp=*this;index++;return tmp;}
		bool operator!=(const iterator& other)const{return index!=other.index || ptr!=other.ptr;}
	};
	iterator begin(){return iterator(this,0);}
	iterator end(){return iterator(this,2);}
	#define CVec(...) CVec<>(__VA_ARGS__)
};
template<typename T=long long,typename F=double>
class CLine{
protected:
	typedef CVec<T,F> Point;
	Point xp,yp;
public:
	void fit(){if(xp.x>yp.x || (xp.x==yp.x && xp.y>yp.y))swap(xp,yp);}
	CLine(const T& xl=0,const T& yl=0,const T& xr=0,const T& yr=0):xp(xl,yl),yp(xr,yr){fit();}
	CLine(const T& xl,const T& yl,const Point& R=Point(0,0)):xp(xl,yl),yp(R){fit();}
	CLine(const Point& L,const T& xr=0,const T& yr=0):xp(L),yp(xr,yr){fit();}
	CLine(const Point& L,const Point& R):xp(L),yp(R){fit();}
	CLine(const CLine& val):xp(val.xp),yp(val.yp){fit();}
	static CLine asFunction(F k,F b){return CLine(0,b,1,k+b);}
	static CLine asFunction(Point p,F xr,F k){return CLine(p,xr,(F)p.y+(F)(xr-p.x)*k);}
	F length(){return (yp-xp).disTo();}
	F getVal(const F& pos)const{
		if(xp.x==yp.x)	return max(xp.y,yp.y);
		return (F)xp.y+(F)(yp.y-xp.y)*(F)((F)(pos-xp.x)/(F)(yp.x-xp.x));
	}
	Point getPoint(F pos){
		return Point(pos,getVal(pos));
	}
	const Point& x(){return xp;}
	const T& xl(){return xp.x;}
	const T& xr(){return yp.x;}
	const Point& y(){return yp;}
	void setX(const Point& x_){xp=x_;fit();}
	void setY(const Point& y_){yp=y_;fit();}
	void setX1(const T& val){xp.x=val;fit();}
	void setY1(const T& val){xp.y=val;fit();}
	void setX2(const T& val){yp.x=val;fit();}
	void setY2(const T& val){yp.y=val;fit();}
	CLine& operator+=(const Point& tg){xp+=tg,yp+=tg;return *this;}
	CLine operator+(const Point& tg){return CLine(*this)+=tg;}
	CLine& operator-=(const Point& tg){xp-=tg,yp-=tg;return *this;}
	CLine operator-(const Point& tg){return CLine(*this)-=tg;}
	class iterator{
		CLine* ptr;
		int index;
	public:
		iterator(CLine* ptr_,int index_):ptr(ptr_),index(index_){}
		Point& operator*(){return (index==0)?(ptr->xp):(ptr->yp);}
		const Point& operator*()const{return (index==0)?(ptr->xp):(ptr->yp);}
		iterator& operator++(){index++;return *this;}
		iterator operator++(int){auto tmp=*this;index++;return tmp;}
		bool operator!=(const iterator& other)const{return index!=other.index || ptr!=other.ptr;}
	};
	iterator begin(){return iterator(this,0);}
	iterator end(){return iterator(this,2);}
	bool inRange(const F& pos)const{return (F)xp.x<=pos && pos<=(F)yp.x;}
	bool lessAt(const CLine& y,const F& pos)const{return getVal(pos)<y.getVal(pos);}
	bool greaterAt(const CLine& y,const F& pos)const{return getVal(pos)>y.getVal(pos);}
	#define CLine(...) CLine<>(__VA_ARGS__)
};
class SegTree{
public:
	int lc,rc;
	CLine<>* L;
}tr[MAXN*30];
int pnum;
int newNode(){
	pnum++;
	tr[pnum].L=new CLine<>(0,-1e15,2e9,-1e15);
	return pnum;
}
int rt;
void Insert(int &p,LL l,LL r,CLine<> k){
	if(!p)	p=newNode();
	if(k.xl()<=l && r<=k.xr()){
		LL mid=(l+r)>>1ll;
		if(k.greaterAt(*tr[p].L,mid)){
			swap(k,*tr[p].L);
		}
		bool gl=k.greaterAt(*tr[p].L,l);
		bool gr=k.greaterAt(*tr[p].L,r);
		if(!gl && !gr)	return ;//FW
		if(gl)	Insert(tr[p].lc,l,mid,k);
		if(gr)	Insert(tr[p].rc,mid+1,r,k);
		return ;
	}
	LL mid=(l+r)>>1ll;
	if(k.xl()<=mid){
		Insert(tr[p].lc,l,mid,k);
	}
	if(k.xr()>mid){
		Insert(tr[p].rc,mid+1,r,k);
	}
	return ;
}
LL Query(int p,LL l,LL r,LL pos){
	if(!p)	return LLONG_MIN;
	if(l==r)	return tr[p].L->getVal(pos);
	LL mid=(l+r)>>1ll;
	if(pos<=mid)	return max(Query(tr[p].lc,l,mid,pos),(LL)tr[p].L->getVal(pos));
	else	return max(Query(tr[p].rc,mid+1,r,pos),(LL)tr[p].L->getVal(pos));
}
CLine<> lst[MAXN];
void PushSeg(CLine<> x){
	Insert(rt,0,2e9,x);
	if((x.x().y<0)||(x.y().y<0)){
		x.setY1(-x.x().y);
		x.setY2(-x.y().y);
		Insert(rt,0,2e9,x);
	}
}
void solve(bool SPE){ 
	n=RIN,m=RIN;
	foru(i,1,n){
		a[i]=RIN;
	}
	#ifdef DEBUGING
	if(SPE){
		
	}
	#endif
	foru(i,1,m){
		in[i].t=RIN;
		in[i].opt=readCMD();
		if(in[i].opt){
			in[i].x=RIN,in[i].y=RIN;
		}
	}
	foru(i,1,n){
		lst[i]=CLine(0,a[i],2e9,a[i]);
	}
	foru(i,1,m){
		if(in[i].opt!=1)	continue;
		// auto [t,opt,x,y]=in[i];
		auto t=in[i].t;
		auto opt=in[i].opt;
		auto x=in[i].x;
		auto y=in[i].y;
		if(lst[x].x().x<t){
			//Add
			auto add=CLine(lst[x].x(),lst[x].getPoint(t));
			// cein<<add<<endl;
			PushSeg(add);
		}
		lst[x]=CLine<>::asFunction(lst[x].getPoint(t),2e9,y);
	}
	foru(i,1,n){
		auto add=lst[i];
		// cein<<add<<endl;
		PushSeg(add);
	}
	foru(i,1,m){
		if(in[i].opt==1)	continue;
		auto t=in[i].t;
		auto opt=in[i].opt;
		auto x=in[i].x;
		auto y=in[i].y;
		printf("%lld\n",Query(rt,0,2e9,t));
	}
	
	return ;
}
/*
检查文件读写
检查多测清空
检查数组大小
*/
signed main()
{
	// #define RFILE
	// #define MULTITEST
	// #define TESTCASEID
	
	#ifdef RFILE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	
	#ifdef MULTITEST
	int T=RIN;
	#else
	int T=1;
	#endif
	
	#ifdef TESTCASEID
	ID=RIN;
	#endif
	
	for(int i=1;i<=T;i++) solve(i==0);
	return 0;
}