String Game

Time Limit : 3 sec, Memory Limit : 262144 KB

文字列ゲーム

あなたは、双子のアイ君とヅー君に文字列を使ったゲームのプログラムをプレゼントしました。このゲームでは、アイ君とヅー君が文字列の中から部分文字列をそれぞれ選び、それらを比較して小さい方を選んだ人に得点が加算されます。二人は競い合い、何度もゲームを行いました。ところが、同じ文字列に対して何度もゲームをしているうちに飽きてしまいました。そこであなたは、文字列が変化するようにプログラムを修正することにしました。


長さ N の文字列 UQ 個の命令文が与えられたとき、以下の命令を処理するプログラムを作成せよ。

  • 文字列 U の指定された範囲にあるすべての文字を、指定された文字に置き換える。
  • 文字列 U の指定された2つの部分文字列 S, T を辞書順で比較して、それらの大小関係を出力する。

Input

入力は以下の形式で与えられる。

N
U
Q
query1
query2
:
queryQ

1行目に文字列の長さ N (1 ≤ N ≤ 200000)、2行目に文字列 U (英小文字のみを含む文字列)が与えられる。3行目に命令の数 Q (1 ≤ Q ≤ 100000) が与えられる。続く Q 行に i 番目の命令 queryi が与えられる。各 queryi は、以下のいずれかの形式で与えられる。

set x y z

または

comp a b c d

set x y z は文字列 Ux 文字目から y 文字目までを、指定された文字 z に置き換えることを表す。ただし、1 ≤ xyN であり、z は英小文字である。

comp a b c d は文字列 Ua 文字目から b 文字目までの部分文字列を S、文字列 Uc 文字目から d 文字目までの部分文字列を T としたとき、文字列 S と文字列 T を辞書順で比較することを表す。ただし、1 ≤ abN かつ 1 ≤ cdN である。

Output

各 comp 命令について、S の方が小さいならば「s」、T の方が小さいならば「t」、両者が一致しているならば「e」と1行に出力する。

Sample Input 1

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

Sample Output 1

s
t
e
t
s
e 

Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-11-12
http://web-ext.u-aizu.ac.jp/pc-concours/