#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 200005
#define NUM1 1000000007
#define NUM2 99999883


struct Data{
	Data(){

		hash_1 = 0;
		hash_2 = 0;
		length = 0;
	}
	Data(ull arg_hash_1,ull arg_hash_2,ull arg_length){
		hash_1 = arg_hash_1;
		hash_2 = arg_hash_2;
		length = arg_length;
	}

	ull hash_1,hash_2;
	ull length;
};

int N;
int LENGTH;
char buf[SIZE];
int data[8*SIZE]; //文字を持つ
ull HASH[8*SIZE][2];
ull POW[SIZE][2],TABLE[26][SIZE][2];

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right){
	if(update_right < node_left || update_left > node_right)return; //区間に重なりがなければreturn
	else if(update_left <= node_left && update_right >= node_right){ //このノードがカバーしている区間が、更新区間の部分区間である場合

		data[node_id] = new_value; //文字('a'からの差)
		HASH[node_id][0] = TABLE[new_value][node_right-node_left+1][0];
		HASH[node_id][1] = TABLE[new_value][node_right-node_left+1][1];

	}else{ //一部に重なりがある場合
		//データを左右の子に引き継ぐ
		if(data[node_id] >= 0){
			update(node_left,node_right,data[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
			update(node_left,node_right,data[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
			data[node_id] = -1; //値を持っていないことを表す
		}
		update(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2);
		update(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right);

		ull right_len = node_right-(node_left+node_right)/2;

		HASH[node_id][0] = HASH[2*node_id+1][0]*POW[right_len][0]+HASH[2*node_id+2][0];
		HASH[node_id][1] = HASH[2*node_id+1][1]*POW[right_len][1]+HASH[2*node_id+2][1];
	}
}

//ハッシュ値および区間の長さを返却する
Data query(int search_left,int search_right,int node_id,int node_left,int node_right){

	if(search_right < node_left || search_left > node_right){
		return Data(0,0,0);
	}else if(node_left >= search_left && node_right <= search_right){
		return Data(HASH[node_id][0],HASH[node_id][1],(ull)(node_right-node_left+1));
	}else{

		if(data[node_id] >= 0){
			update(node_left,node_right,data[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
			update(node_left,node_right,data[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
			data[node_id] = -1; //値を持っていないことを表す
			ull right_len = node_right-(node_left+node_right)/2;

			HASH[node_id][0] = HASH[2*node_id+1][0]*POW[right_len][0]+HASH[2*node_id+2][0];
			HASH[node_id][1] = HASH[2*node_id+1][1]*POW[right_len][1]+HASH[2*node_id+2][1];
		}

		Data left = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
		Data right = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

		return Data(left.hash_1*POW[right.length][0]+right.hash_1,left.hash_2*POW[right.length][1]+right.hash_2,left.length+right.length);
	}
}

int find_word(Data info){

	for(int i = 0; i < 26; i++){

		if(info.hash_1 == TABLE[i][1][0] && info.hash_2 == TABLE[i][1][1]){
			return i;
		}
	}
	return -1;
}

int main(){

	scanf("%d",&LENGTH);

	//POWテーブル作成
	POW[0][0] = 1;
	POW[0][1] = 1;

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

		POW[i][0] = POW[i-1][0]*NUM1;
		POW[i][1] = POW[i-1][1]*NUM2;
	}

	//文字のハッシュ値をあらかじめ作っておく
	for(int i = 0; i < 26; i++){
		TABLE[i][0][0] = 0;
		TABLE[i][0][1] = 0;
		for(int k = 1; k <= LENGTH; k++){
			TABLE[i][k][0] = ('a'+i) + TABLE[i][k-1][0]*NUM1;
			TABLE[i][k][1] = ('a'+i) + TABLE[i][k-1][1]*NUM2;
		}
	}

	N = 1;
	init(LENGTH);
	for(int i = 0; i <= 2*N-2; i++)data[i] = -1;

	scanf("%s",buf);
	for(int i = 0; i < LENGTH; i++){
		update(i,i,buf[i]-'a',0,0,N-1);
	}

	int num_query;
	scanf("%d",&num_query);

	char order[6],z[2];
	int x,y,a,b,c,d;
	int L,R,mid,match_len;

	Data A,B;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%s",order);

		if(order[0] == 's'){

			scanf("%d %d %s",&x,&y,z);
			update(x-1,y-1,z[0]-'a',0,0,N-1);

		}else{ //比較命令

			scanf("%d %d %d %d",&a,&b,&c,&d);

			a--;
			b--;
			c--;
			d--;

			L = 0,R = min(b-a+1,d-c+1),mid = (L+R)/2;
			match_len = 0;

			while(L <= R){

				A = query(a,a+mid-1,0,0,N-1);
				B = query(c,c+mid-1,0,0,N-1);

				if(A.hash_1==B.hash_1 && A.hash_2 == B.hash_2){

					match_len = mid;
					L = mid+1;

				}else{

					R = mid-1;
				}
				mid = (L+R)/2;
			}

			if(match_len == b-a+1 && match_len == d-c+1){

				printf("e\n");
			}else{
				if(match_len == b-a+1 || (match_len != d-c+1 && find_word(query(a+match_len,a+match_len,0,0,N-1)) < find_word(query(c+match_len,c+match_len,0,0,N-1)))){

					printf("s\n");
				}else{
					printf("t\n");
				}
			}
		}
	}

	return 0;
}



### Prompt

Construct a Cpp code solution to the problem outlined:

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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 200005
#define NUM1 1000000007
#define NUM2 99999883


struct Data{
	Data(){

		hash_1 = 0;
		hash_2 = 0;
		length = 0;
	}
	Data(ull arg_hash_1,ull arg_hash_2,ull arg_length){
		hash_1 = arg_hash_1;
		hash_2 = arg_hash_2;
		length = arg_length;
	}

	ull hash_1,hash_2;
	ull length;
};

int N;
int LENGTH;
char buf[SIZE];
int data[8*SIZE]; //文字を持つ
ull HASH[8*SIZE][2];
ull POW[SIZE][2],TABLE[26][SIZE][2];

void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int update_left,int update_right,int new_value,int node_id,int node_left,int node_right){
	if(update_right < node_left || update_left > node_right)return; //区間に重なりがなければreturn
	else if(update_left <= node_left && update_right >= node_right){ //このノードがカバーしている区間が、更新区間の部分区間である場合

		data[node_id] = new_value; //文字('a'からの差)
		HASH[node_id][0] = TABLE[new_value][node_right-node_left+1][0];
		HASH[node_id][1] = TABLE[new_value][node_right-node_left+1][1];

	}else{ //一部に重なりがある場合
		//データを左右の子に引き継ぐ
		if(data[node_id] >= 0){
			update(node_left,node_right,data[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
			update(node_left,node_right,data[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
			data[node_id] = -1; //値を持っていないことを表す
		}
		update(update_left,update_right,new_value,2*node_id+1,node_left,(node_left+node_right)/2);
		update(update_left,update_right,new_value,2*node_id+2,(node_left+node_right)/2+1,node_right);

		ull right_len = node_right-(node_left+node_right)/2;

		HASH[node_id][0] = HASH[2*node_id+1][0]*POW[right_len][0]+HASH[2*node_id+2][0];
		HASH[node_id][1] = HASH[2*node_id+1][1]*POW[right_len][1]+HASH[2*node_id+2][1];
	}
}

//ハッシュ値および区間の長さを返却する
Data query(int search_left,int search_right,int node_id,int node_left,int node_right){

	if(search_right < node_left || search_left > node_right){
		return Data(0,0,0);
	}else if(node_left >= search_left && node_right <= search_right){
		return Data(HASH[node_id][0],HASH[node_id][1],(ull)(node_right-node_left+1));
	}else{

		if(data[node_id] >= 0){
			update(node_left,node_right,data[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
			update(node_left,node_right,data[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
			data[node_id] = -1; //値を持っていないことを表す
			ull right_len = node_right-(node_left+node_right)/2;

			HASH[node_id][0] = HASH[2*node_id+1][0]*POW[right_len][0]+HASH[2*node_id+2][0];
			HASH[node_id][1] = HASH[2*node_id+1][1]*POW[right_len][1]+HASH[2*node_id+2][1];
		}

		Data left = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
		Data right = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

		return Data(left.hash_1*POW[right.length][0]+right.hash_1,left.hash_2*POW[right.length][1]+right.hash_2,left.length+right.length);
	}
}

int find_word(Data info){

	for(int i = 0; i < 26; i++){

		if(info.hash_1 == TABLE[i][1][0] && info.hash_2 == TABLE[i][1][1]){
			return i;
		}
	}
	return -1;
}

int main(){

	scanf("%d",&LENGTH);

	//POWテーブル作成
	POW[0][0] = 1;
	POW[0][1] = 1;

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

		POW[i][0] = POW[i-1][0]*NUM1;
		POW[i][1] = POW[i-1][1]*NUM2;
	}

	//文字のハッシュ値をあらかじめ作っておく
	for(int i = 0; i < 26; i++){
		TABLE[i][0][0] = 0;
		TABLE[i][0][1] = 0;
		for(int k = 1; k <= LENGTH; k++){
			TABLE[i][k][0] = ('a'+i) + TABLE[i][k-1][0]*NUM1;
			TABLE[i][k][1] = ('a'+i) + TABLE[i][k-1][1]*NUM2;
		}
	}

	N = 1;
	init(LENGTH);
	for(int i = 0; i <= 2*N-2; i++)data[i] = -1;

	scanf("%s",buf);
	for(int i = 0; i < LENGTH; i++){
		update(i,i,buf[i]-'a',0,0,N-1);
	}

	int num_query;
	scanf("%d",&num_query);

	char order[6],z[2];
	int x,y,a,b,c,d;
	int L,R,mid,match_len;

	Data A,B;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%s",order);

		if(order[0] == 's'){

			scanf("%d %d %s",&x,&y,z);
			update(x-1,y-1,z[0]-'a',0,0,N-1);

		}else{ //比較命令

			scanf("%d %d %d %d",&a,&b,&c,&d);

			a--;
			b--;
			c--;
			d--;

			L = 0,R = min(b-a+1,d-c+1),mid = (L+R)/2;
			match_len = 0;

			while(L <= R){

				A = query(a,a+mid-1,0,0,N-1);
				B = query(c,c+mid-1,0,0,N-1);

				if(A.hash_1==B.hash_1 && A.hash_2 == B.hash_2){

					match_len = mid;
					L = mid+1;

				}else{

					R = mid-1;
				}
				mid = (L+R)/2;
			}

			if(match_len == b-a+1 && match_len == d-c+1){

				printf("e\n");
			}else{
				if(match_len == b-a+1 || (match_len != d-c+1 && find_word(query(a+match_len,a+match_len,0,0,N-1)) < find_word(query(c+match_len,c+match_len,0,0,N-1)))){

					printf("s\n");
				}else{
					printf("t\n");
				}
			}
		}
	}

	return 0;
}



```