class ScopedMapNode:
    def __init__(self, key, value, level, previous, shadowed):
        self.key = key
        self.value = value
        self.level = level
        self.previous = previous
        self.shadowed = shadowed

class  AnotherScopedMap:
    """An AnotherScopedMap maps keys to values, much like a dictionary.
        A value put in at an inner scope shadows any outer value for the key.
        The outer value becomes active again when the inner scope is exited."""

    ## representation:
    ##   self.level is the current nesting level
    ##   self.newest is the head of a linked list of ScopedMapNodes;
    ##      this list continues for each node by following node.previous
    ##      and ends when None is reached (perhaps immediately)
    ##   self.nodes is a dictionary which stores for each key the head
    ##      of a linked list of ScopedMapNodes, each containing the key;
    ##      this list continue for each node by following node.shadowed
    ##      and ends when None is reached (perhaps immediately)
    ##   a key can also be missing from self.nodes, which is equivalent
    ##      to self.nodes[key] being None
    ##   the nodes reachable in the self.newest list are the same ones
    ##      as are reachable through the various self.nodes lists
    ##   along any of the linked lists, node.level is nonincreasing

    def __init__(self):
        """Initialize a new AnotherScopedMap"""
        self.nodes = {}
        self.newest = None
        self.level = 0

    def isLocal(self, key):
        """Return True if key was put into the map at the innermost scope"""
        node = self.nodes.get(key, None)
        return node != None and node.level == self.level

    def enterScope(self):
        """Set the map to a new scope nested inside the previous one"""
        self.level += 1

    def exitScope(self):
        """Exit from the current scope to the containing one"""
        while self.newest != None and self.newest.level == self.level:
            self.nodes[self.newest.key] = self.newest.shadowed
            self.newest = self.newest.previous
        self.level -= 1

    def retrieve(self, key):
        """Return the value currently corresponding to key, or None"""
        node = self.nodes.get(key, None)
        if node==None:
            return None
        return node.value

    def getNestingLevel(self):
        """Return the excess of enterScope over exitScope operations"""
        return self.level

    def put(self, key, value):
        """Put the key/value pair in the map at the current scope"""
        shadowed = self.nodes.get(key, None)
        node = ScopedMapNode(key, value, self.level, self.newest, shadowed)
        self.nodes[key] = node
        self.newest = node