0623 - 文字列ゲーム

問題

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

課題

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

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

入力

N
U
Q
query1
query2
.
.
.
queryQ

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

set x y z

または

comp a b c d

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

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

時間制限

入力に対して、実行時間が６秒を超えてはならない。ただしHOJには問題作成時現在では６秒に設定できないので今回は５秒とする。

出力

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

入出力例

入力例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

出力例1

s
t
e
t
s
e