Problem: For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.
* get($key$): Print the value with the specified $key$. Print 0 if there is no such element.
* delete($key$): Delete the element with the specified $key$.
* dump($L$, $R$): Print all elements formed by a pair of the key and the value such that the key is greater than or equal to $L$ and less than or equal to $R$ in lexicographic order.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consists of lower-case letters
* $L \leq R$ in lexicographic order
* The total number of elements printed by dump operations does not exceed $1,000,000$

Input

The input is given in the following format.


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


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


or


2 $key$


or


3 $L$ $R$


where the first digits 0, 1, 2 and 3 represent insert, get, delete and dump operations.

Output

For each get operation, print the corresponding value.
For each dump operation, print the corresponding elements formed by a pair of the key and the value. For the dump operation, print the elements (a pair of key and value separated by a space character) in ascending order of the keys.

Example

Input

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


Output

1
4
0
0
white 5

Solution (in PYTHON3):

Solution:
from enum import Enum
 
 
class Color(Enum):
    BLACK = 0
    RED = 1
 
    @staticmethod
    def flip(c):
        return [Color.RED, Color.BLACK][c.value]
 
 
class Node:
    __slots__ = ('key', 'left', 'right', 'size', 'color', 'value')
 
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = Leaf
        self.right = Leaf
        self.size = 1
        self.color = Color.RED
 
    def is_red(self):
        return self.color == Color.RED
 
    def is_black(self):
        return self.color == Color.BLACK
 
    def __str__(self):
        if self.color == Color.RED:
            key = '*{}'.format(self.key)
        else:
            key = '{}'.format(self.key)
        return "{}[{}] ({}, {})".format(key, self.size,
                                        self.left, self.right)
 
 
class LeafNode(Node):
    def __init__(self):
        self.key = None
        self.value = None
        self.left = None
        self.right = None
        self.size = 0
        self.color = None
 
    def is_red(self):
        return False
 
    def is_black(self):
        return False
 
    def __str__(self):
        return '-'
 
 
Leaf = LeafNode()
 
 
class RedBlackBinarySearchTree:
    """Red Black Binary Search Tree with range, min, max.
    Originally impremented in the textbook
    Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
    Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
    """
 
    def __init__(self):
        self.root = Leaf
 
    def put(self, key, value=None):
        def _put(node):
            if node is Leaf:
                node = Node(key, value)
            if node.key > key:
                node.left = _put(node.left)
            elif node.key < key:
                node.right = _put(node.right)
            else:
                node.value = value
 
            node = self._restore(node)
 
            node.size = node.left.size + node.right.size + 1
            return node
 
        self.root = _put(self.root)
        self.root.color = Color.BLACK
 
    def _rotate_left(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = Color.RED
        node.size = node.left.size + node.right.size + 1
        return x
 
    def _rotate_right(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = Color.RED
        node.size = node.left.size + node.right.size + 1
        return x
 
    def _flip_colors(self, node):
        node.color = Color.flip(node.color)
        node.left.color = Color.flip(node.left.color)
        node.right.color = Color.flip(node.right.color)
        return node
 
    def __contains__(self, key):
        def _contains(node):
            if node is Leaf:
                return False
            if node.key > key:
                return _contains(node.left)
            elif node.key < key:
                return _contains(node.right)
            else:
                return True
        return _contains(self.root)
 
    def get(self, key):
        def _get(node):
            if node is Leaf:
                return None
            if node.key > key:
                return _get(node.left)
            elif node.key < key:
                return _get(node.right)
            else:
                return node.value
        return _get(self.root)
 
    def delete(self, key):
        def _delete(node):
            if node is Leaf:
                return Leaf
 
            if node.key > key:
                if node.left is Leaf:
                    return self._balance(node)
                if not self._is_red_left(node):
                    node = self._red_left(node)
                node.left = _delete(node.left)
            else:
                if node.left.is_red():
                    node = self._rotate_right(node)
                if node.key == key and node.right is Leaf:
                    return Leaf
                elif node.right is Leaf:
                    return self._balance(node)
                if not self._is_red_right(node):
                    node = self._red_right(node)
                if node.key == key:
                    x = self._find_min(node.right)
                    node.key = x.key
                    node.value = x.value
                    node.right = self._delete_min(node.right)
                else:
                    node.right = _delete(node.right)
 
            return self._balance(node)
 
        if self.is_empty():
            raise ValueError('delete on empty tree')
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = _delete(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def delete_max(self):
        if self.is_empty():
            raise ValueError('delete max on empty tree')
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = self._delete_max(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def _delete_max(self, node):
        if node.left.is_red():
            node = self._rotate_right(node)
        if node.right is Leaf:
            return Leaf
 
        if not self._is_red_right(node):
            node = self._red_right(node)
        node.right = self._delete_max(node.right)
        return self._balance(node)
 
    def _red_right(self, node):
        node = self._flip_colors(node)
        if node.left.left.is_red():
            node = self._rotate_right(node)
        return node
 
    def _is_red_right(self, node):
        return (node.right.is_red() or
                (node.right.is_black() and node.right.left.is_red()))
 
    def delete_min(self):
        if self.is_empty():
            raise ValueError('delete min on empty tree')
 
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = self._delete_min(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def _delete_min(self, node):
        if node.left is Leaf:
            return Leaf
 
        if not self._is_red_left(node):
            node = self._red_left(node)
        node.left = self._delete_min(node.left)
        return self._balance(node)
 
    def _red_left(self, node):
        node = self._flip_colors(node)
        if node.right.left.is_red():
            node.right = self._rotate_right(node.right)
            node = self._rotate_left(node)
        return node
 
    def _is_red_left(self, node):
        return (node.left.is_red() or
                (node.left.is_black() and node.left.left.is_red()))
 
    def _balance(self, node):
        if node.right.is_red():
            node = self._rotate_left(node)
        return self._restore(node)
 
    def _restore(self, node):
        if node.right.is_red() and not node.left.is_red():
            node = self._rotate_left(node)
        if node.left.is_red() and node.left.left.is_red():
            node = self._rotate_right(node)
        if node.left.is_red() and node.right.is_red():
            node = self._flip_colors(node)
 
        node.size = node.left.size + node.right.size + 1
        return node
 
    def is_empty(self):
        return self.root is Leaf
 
    def is_balanced(self):
        if self.is_empty():
            return True
 
        try:
            left = self._depth(self.root.left)
            right = self._depth(self.root.right)
            return left == right
        except Exception:
            return False
 
    @property
    def depth(self):
        return self._depth(self.root)
 
    def _depth(self, node):
        if node is Leaf:
            return 0
        if node.right.is_red():
            raise Exception('right red')
        left = self._depth(node.left)
        right = self._depth(node.right)
        if left != right:
            raise Exception('unbalanced')
        if node.is_red():
            return left
        else:
            return 1 + left
 
    def __len__(self):
        return self.root.size
 
    @property
    def max(self):
        if self.is_empty():
            raise ValueError('max on empty tree')
        return self._max(self.root)
 
    def _max(self, node):
        x = self._find_max(node)
        return x.key
 
    def _find_max(self, node):
        if node.right is Leaf:
            return node
        else:
            return self._find_max(node.right)
 
    @property
    def min(self):
        if self.is_empty():
            raise ValueError('min on empty tree')
        return self._min(self.root)
 
    def _min(self, node):
        x = self._find_min(node)
        return x.key
 
    def _find_min(self, node):
        if node.left is Leaf:
            return node
        else:
            return self._find_min(node.left)
 
    def __iter__(self):
        def inorder(node):
            if node is Leaf:
                return
            yield from inorder(node.left)
            yield node.value
            yield from inorder(node.right)
        yield from inorder(self.root)
 
    def range(self, min_, max_):
        def _range(node):
            if node is Leaf:
                return
 
            if node.key > max_:
                yield from _range(node.left)
            elif node.key < min_:
                yield from _range(node.right)
            else:
                yield from _range(node.left)
                yield (node.key, node.value)
                yield from _range(node.right)
 
        if min_ > max_:
            return
        yield from _range(self.root)
 
 
class Map:
 
    def __init__(self):
        self.tree = RedBlackBinarySearchTree()
 
    def __getitem__(self, key):
        if key in self.tree:
            return self.tree.get(key)
        else:
            raise IndexError('key {} not found in map'.format(key))
 
    def __setitem__(self, key, value):
        self.tree.put(key, value)
 
    def __delitem__(self, key):
        if key in self.tree:
            self.tree.delete(key)
        else:
            raise IndexError('key {} not found in map'.format(key))
 
    def __len__(self):
        return len(self.tree)
 
    def items(self):
        for k, v in self.tree:
            yield (k, v)
 
    def range(self, min_, max_):
        for k, v in self.tree.range(min_, max_):
            yield (k, v)
 
 
def run():
    q = int(input())
    m = Map()
 
    for _ in range(q):
        command, *args = input().split()
        if command == '0':
            key = args[0]
            value = int(args[1])
            m[key] = value
        elif command == '1':
            key = args[0]
            try:
                print(m[key])
            except IndexError:
                print(0)
        elif command == '2':
            key = args[0]
            try:
                del m[key]
            except IndexError:
                pass
        elif command == '3':
            low, hi = args
            for k, v in m.range(low, hi):
                print(k, v)
        else:
            raise ValueError('invalid command')
 
 
if __name__ == '__main__':
    run()