Map: Range Search

キーが文字列、値が整数である辞書$M$に対して、以下の操作を行ってください。ただし、辞書$M$はキーの重複を許しません。

• insert($key$, $x$): $M$ にキーが$key$で値が$x$である要素を挿入する。キーが$key$である要素が既に存在する場合は値を$x$に更新する。
• get($key$): キーが$key$ である値を出力する。ただし、そのような要素がない場合は0を出力する。
• delete($key$): キーが$key$である要素を$M$から削除する。
• dump($L$, $R$): キーが辞書式順で$L$以上$R$以下である要素の、キーと値の組を順番に出力する。

Input

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

$q$
$query_1$
$query_2$
:
$query_q$

各クエリ$query_i$は

0 $key$ $x$

または

1 $key$

または

2 $key$

または

3 $L$ $R$

の形式で与えられます。最初の数字0, 1, 2, 3 は操作の種類を示し、それぞれinsert、get、delete、dump を表します。

Output

各get操作ごとに、整数を１行に出力してください。また、各dump操作ごとに、キーと値の組を1行ずつ空白で区切って出力してください。このとき、辞書順でキーが小さいものから出力してください。

Constraints

• $1 \leq q \leq 200,000$
• $1 \leq x \leq 1,000,000,000$
• $1 \leq $ $key$の長さ $ \leq 20$
• $key$は英小文字
• $L$ は辞書式順で$R$より小さいか等しい
• dump操作で出力される要素の総数は $1,000,000$ を超えない

Sample Input 1

9
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z

Sample Output 1

1
4
0
0
white 5

---