#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<list>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint moA=1e9+7;
const llint moB=1e9+9;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
//segtree
//hash値,埋めるの発生有無
//長さは262144固定?
//Qlog^2 n
llint zyA[20],zyB[20];
llint ruA[20],ruB[20];
class rori{public:
	llint hA,hB;
	char ume;
	rori(void){hA=0;hB=0;ume=0;}
	rori(int inA,int inB,int dumy){hA=inA,hB=inB,ume=0;}
	rori(int in,int naga){ume=in;hA=(in*ruA[naga])%moA,hB=(in*ruB[naga])%moB;}
};
rori tna(rori me,rori us,int an){return rori((me.hA*zyA[an]+us.hA)%moA,(me.hB*zyB[an]+us.hB)%moB,0);}
rori tna(rori me,rori us,llint Ak,llint Bk){return rori((me.hA*Ak+us.hA)%moA,(me.hB*Bk+us.hB)%moB,0);}

void bun(rori&per,rori&kox,rori&koy,int an){//anは子のを入れる
	if(per.ume){kox=rori(per.ume,an);koy=kox;per.ume=0;}
}
int main(void){
	llint n,h,i,j;cin>>n;
	zyA[0]=101,zyB[0]=101;
	for(i=1;i<20;i++){zyA[i]=(zyA[i-1]*zyA[i-1])%moA;zyB[i]=(zyB[i-1]*zyB[i-1])%moB;}
	for(i=0;i<20;i++){
		llint AA=1,BB=1;
		ruA[i]=0;ruB[i]=0;
		for(j=0;j<(1<<i);j++){ruB[i]+=BB;ruB[i]%=moB;BB*=101;BB%=moB;ruA[i]+=AA;ruA[i]%=moA;AA*=101;AA%=moA;}
	}
	string U;cin>>U;
	static rori seg[524288];
	for(i=1;i<=n;i++){seg[i+262144]=rori(U[i-1],0);}
	for(i=n+1;i<262144;i++){seg[i+262144]=rori(0,0);}
	h=0;
	for(i=262143;i>0;i--){
		seg[i]=tna(seg[i+i],seg[i+i+1],h);
		if((i&(-i))==i){h++;}
	}
	int Q;cin>>Q;
	while(Q--){
		string mei;cin>>mei;
		if(mei=="set"){
			int x,y;char z;cin>>x>>y>>z;
			x+=262143;y+=262145;int xx=x,yy=y;
			for(h=18;h>0;h--){int G=x>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=y>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			h=0;
			while(x+1<y){
				if(x%2==0){seg[x+1]=rori(z,h);}
				if(y%2==1){seg[y-1]=rori(z,h);}
				x>>=1;y>>=1;h++;
			}
			x=xx;y=yy;
			h=0;
			while(x>1){
				x>>=1;y>>=1;
				seg[x]=tna(seg[x<<1],seg[(x<<1)+1],h);
				seg[y]=tna(seg[y<<1],seg[(y<<1)+1],h);
				h++;
			}
		}else{
			int a,b,c,d;cin>>a>>b>>c>>d;
			int bmin=0,bmax=min(b-a+1,d-c+1)+1;
			//普通に二分探索! セグ木上の二分探索テクは使用不可
			//最大何文字が一致しているか調べる
			//bmin文字一致している
			int Sa=a+262143,Ta=c+262143;
			for(h=18;h>0;h--){int G=Sa>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=Ta>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			while(bmax-bmin>1){
				
				Sa=a+262143;Ta=c+262143;
				int bgen=(bmin+bmax)>>1;
				int Se=a+bgen+262144,Te=c+bgen+262144;
				for(h=18;h>0;h--){int G=Se>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=Te>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
				rori Sans,Tans;
				{
					llint Auk=1,Buk=1;
					rori nowM,nowU;
					int h=0;
					while(Sa+1<Se){
						if(Sa%2==0){nowM=tna(nowM,seg[Sa+1],h);}
						if(Se%2==1){nowU=tna(seg[Se-1],nowU,Auk,Buk);Auk*=zyA[h];Auk%=moA;Buk*=zyB[h];Buk%=moB;}
						Sa>>=1;Se>>=1;h++;
					}
					//cerr<<"M,U="<<nowM.hA<<" "<<nowU.hA<<" ";
					Sans=tna(nowM,nowU,Auk,Buk);
					//cerr<<Sans.hA<<endl;
				}
				{
					llint Auk=1,Buk=1;
					rori nowM,nowU;
					int h=0;
					while(Ta+1<Te){
						if(Ta%2==0){nowM=tna(nowM,seg[Ta+1],h);}
						if(Te%2==1){nowU=tna(seg[Te-1],nowU,Auk,Buk);Auk*=zyA[h];Auk%=moA;Buk*=zyB[h];Buk%=moB;}
						Ta>>=1;Te>>=1;h++;
					}
					//cerr<<"M,U="<<nowM.hA<<" "<<nowU.hA<<" ";
					Tans=tna(nowM,nowU,Auk,Buk);
					//cerr<<Tans.hA<<endl;
				}
				if(Sans.hA==Tans.hA&&Sans.hB==Tans.hB){bmin=bgen;}else{bmax=bgen;}
				//cerr<<"bmin="<<bmin<<endl;
			}
			char kota;
			int aaa=262144+a+bmin,ccc=262144+c+bmin;
			for(h=18;h>0;h--){int G=aaa>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=ccc>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			//cerr<<seg[262144+a+bmin].ume<<endl;
			if(b-a+1==d-c+1&&d-c+1==bmin){kota='e';}
			else if(b-a+1>d-c+1&&d-c+1==bmin){kota='t';}
			else if(b-a+1<d-c+1&&b-a+1==bmin){kota='s';}
			else if(seg[262144+a+bmin].ume<seg[262144+c+bmin].ume){kota='s';}
			else{kota='t';}
			cout<<kota<<endl;
		}
	}
	return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

You gave the twins Ai and Zu a program of games using strings. In this game, Ai and Zu each select a substring from the character string, compare them, and the person who chooses the smaller one will get points. The two competed and played the game many times. However, I got tired of playing games for the same string many times. So you decided to modify the program so that the strings change.




Given a string U of length N and Q statements, write a program that processes the following instructions.

* Replaces all characters in the specified range of string U with the specified characters.
* Compares the two specified substrings S and T of the string U in lexicographical order and outputs their magnitude relations.



Input

The input is given in the following format.


N
U
Q
query1
query2
::
queryQ


The string length N (1 ≤ N ≤ 200000) is given on the first line, and the string U (string containing only lowercase letters) is given on the second line. The number of instructions Q (1 ≤ Q ≤ 100000) is given on the third line. The following Q line is given the i-th instruction queryi. Each queryi is given in one of the following formats:


set x y z


Or


comp a b c d


set x y z means to replace the xth to yth characters of the string U with the specified character z. Where 1 ≤ x ≤ y ≤ N and z is lowercase.

comp abcd is a string S and a string, where S is the substring from the a to b of the string U and T is the substring of the string U from the c to the d. Represents comparing T in lexical order. Where 1 ≤ a ≤ b ≤ N and 1 ≤ c ≤ d ≤ N.

Output

For each comp instruction, if S is smaller, "s" is output, if T is smaller, "t" is output, and if both match, "e" is output on one line.

Example

Input

13
aizualgorithm
9
comp 1 1 4 5
comp 2 6 1 5
set 9 12 b
comp 9 9 10 10
comp 5 8 1 4
set 1 10 z
set 11 13 x
comp 8 10 1 5
comp 1 5 1 5


Output

s
t
e
t
s
e

### Response

```cpp
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<list>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint moA=1e9+7;
const llint moB=1e9+9;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
//segtree
//hash値,埋めるの発生有無
//長さは262144固定?
//Qlog^2 n
llint zyA[20],zyB[20];
llint ruA[20],ruB[20];
class rori{public:
	llint hA,hB;
	char ume;
	rori(void){hA=0;hB=0;ume=0;}
	rori(int inA,int inB,int dumy){hA=inA,hB=inB,ume=0;}
	rori(int in,int naga){ume=in;hA=(in*ruA[naga])%moA,hB=(in*ruB[naga])%moB;}
};
rori tna(rori me,rori us,int an){return rori((me.hA*zyA[an]+us.hA)%moA,(me.hB*zyB[an]+us.hB)%moB,0);}
rori tna(rori me,rori us,llint Ak,llint Bk){return rori((me.hA*Ak+us.hA)%moA,(me.hB*Bk+us.hB)%moB,0);}

void bun(rori&per,rori&kox,rori&koy,int an){//anは子のを入れる
	if(per.ume){kox=rori(per.ume,an);koy=kox;per.ume=0;}
}
int main(void){
	llint n,h,i,j;cin>>n;
	zyA[0]=101,zyB[0]=101;
	for(i=1;i<20;i++){zyA[i]=(zyA[i-1]*zyA[i-1])%moA;zyB[i]=(zyB[i-1]*zyB[i-1])%moB;}
	for(i=0;i<20;i++){
		llint AA=1,BB=1;
		ruA[i]=0;ruB[i]=0;
		for(j=0;j<(1<<i);j++){ruB[i]+=BB;ruB[i]%=moB;BB*=101;BB%=moB;ruA[i]+=AA;ruA[i]%=moA;AA*=101;AA%=moA;}
	}
	string U;cin>>U;
	static rori seg[524288];
	for(i=1;i<=n;i++){seg[i+262144]=rori(U[i-1],0);}
	for(i=n+1;i<262144;i++){seg[i+262144]=rori(0,0);}
	h=0;
	for(i=262143;i>0;i--){
		seg[i]=tna(seg[i+i],seg[i+i+1],h);
		if((i&(-i))==i){h++;}
	}
	int Q;cin>>Q;
	while(Q--){
		string mei;cin>>mei;
		if(mei=="set"){
			int x,y;char z;cin>>x>>y>>z;
			x+=262143;y+=262145;int xx=x,yy=y;
			for(h=18;h>0;h--){int G=x>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=y>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			h=0;
			while(x+1<y){
				if(x%2==0){seg[x+1]=rori(z,h);}
				if(y%2==1){seg[y-1]=rori(z,h);}
				x>>=1;y>>=1;h++;
			}
			x=xx;y=yy;
			h=0;
			while(x>1){
				x>>=1;y>>=1;
				seg[x]=tna(seg[x<<1],seg[(x<<1)+1],h);
				seg[y]=tna(seg[y<<1],seg[(y<<1)+1],h);
				h++;
			}
		}else{
			int a,b,c,d;cin>>a>>b>>c>>d;
			int bmin=0,bmax=min(b-a+1,d-c+1)+1;
			//普通に二分探索! セグ木上の二分探索テクは使用不可
			//最大何文字が一致しているか調べる
			//bmin文字一致している
			int Sa=a+262143,Ta=c+262143;
			for(h=18;h>0;h--){int G=Sa>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=Ta>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			while(bmax-bmin>1){
				
				Sa=a+262143;Ta=c+262143;
				int bgen=(bmin+bmax)>>1;
				int Se=a+bgen+262144,Te=c+bgen+262144;
				for(h=18;h>0;h--){int G=Se>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=Te>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
				rori Sans,Tans;
				{
					llint Auk=1,Buk=1;
					rori nowM,nowU;
					int h=0;
					while(Sa+1<Se){
						if(Sa%2==0){nowM=tna(nowM,seg[Sa+1],h);}
						if(Se%2==1){nowU=tna(seg[Se-1],nowU,Auk,Buk);Auk*=zyA[h];Auk%=moA;Buk*=zyB[h];Buk%=moB;}
						Sa>>=1;Se>>=1;h++;
					}
					//cerr<<"M,U="<<nowM.hA<<" "<<nowU.hA<<" ";
					Sans=tna(nowM,nowU,Auk,Buk);
					//cerr<<Sans.hA<<endl;
				}
				{
					llint Auk=1,Buk=1;
					rori nowM,nowU;
					int h=0;
					while(Ta+1<Te){
						if(Ta%2==0){nowM=tna(nowM,seg[Ta+1],h);}
						if(Te%2==1){nowU=tna(seg[Te-1],nowU,Auk,Buk);Auk*=zyA[h];Auk%=moA;Buk*=zyB[h];Buk%=moB;}
						Ta>>=1;Te>>=1;h++;
					}
					//cerr<<"M,U="<<nowM.hA<<" "<<nowU.hA<<" ";
					Tans=tna(nowM,nowU,Auk,Buk);
					//cerr<<Tans.hA<<endl;
				}
				if(Sans.hA==Tans.hA&&Sans.hB==Tans.hB){bmin=bgen;}else{bmax=bgen;}
				//cerr<<"bmin="<<bmin<<endl;
			}
			char kota;
			int aaa=262144+a+bmin,ccc=262144+c+bmin;
			for(h=18;h>0;h--){int G=aaa>>h;bun(seg[G],seg[(G<<1)],seg[(G<<1)+1],h-1);int F=ccc>>h;bun(seg[F],seg[(F<<1)],seg[(F<<1)+1],h-1);}
			//cerr<<seg[262144+a+bmin].ume<<endl;
			if(b-a+1==d-c+1&&d-c+1==bmin){kota='e';}
			else if(b-a+1>d-c+1&&d-c+1==bmin){kota='t';}
			else if(b-a+1<d-c+1&&b-a+1==bmin){kota='s';}
			else if(seg[262144+a+bmin].ume<seg[262144+c+bmin].ume){kota='s';}
			else{kota='t';}
			cout<<kota<<endl;
		}
	}
	return 0;
}

```