Multi-Map

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

• insert($key$, $x$): $M$にキーが$key$で値が$x$である要素を挿入する。
• get($key$): キーが$key$ である値を全て出力する。
• 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$ より小さいか等しい
• get操作で出力される要素の総数は $500,000$ を超えない
• dump操作で出力される要素の総数は $500,000$ を超えない

Sample Input 1

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

Sample Output 1

1
6
4
white 5

---