Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the `FreqStack` class:

*   `FreqStack()` constructs an empty frequency stack.
*   `void push(int val)` pushes an integer `val` onto the top of the stack.
*   `int pop()` removes and returns the most frequent element in the stack.
    *   If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

**Example 1:**

**Input**
\[ "FreqStack ",  "push ",  "push ",  "push ",  "push ",  "push ",  "push ",  "pop ",  "pop ",  "pop ",  "pop "\]
\[\[\], \[5\], \[7\], \[5\], \[7\], \[4\], \[5\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, null, null, null, null, null, null, 5, 7, 5, 4\]

**Explanation**
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is \[5\]
freqStack.push(7); // The stack is \[5,7\]
freqStack.push(5); // The stack is \[5,7,5\]
freqStack.push(7); // The stack is \[5,7,5,7\]
freqStack.push(4); // The stack is \[5,7,5,7,4\]
freqStack.push(5); // The stack is \[5,7,5,7,4,5\]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes \[5,7,5,7,4\].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes \[5,7,5,4\].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes \[5,7,4\].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes \[5,7\].

**Constraints:**

*   `0 <= val <= 109`
*   At most `2 * 104` calls will be made to `push` and `pop`.
*   It is guaranteed that there will be at least one element in the stack before calling `pop`.


from collections import deque


def shortestPathAllKeys(grid):
    m, n, steps, k, x, y, mask = len(grid), len(grid[0]), 0, 0, -1, -1, 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '@':
                x, y = i, j
            elif 'a' <= grid[i][j] <= 'f':
                k = max(k, ord(grid[i][j]) - ord('a') + 1)

    q = deque([(x, y, 0)])
    visited = {(x, y, mask)}

    dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    while q:
        qs = len(q)
        for sz in range(qs):
            x, y, mask = q.popleft()

            if mask == (1 << k) - 1:
                return steps

            for dx, dy in dirs:
                nx, ny, nmask = x + dx, y + dy, mask

                if 0 <= nx < m and 0 <= ny < n:
                    c = grid[nx][ny]
                    if 'A' <= c <= 'F' and not nmask & (1 << (ord(c) - ord('A'))):
                        continue
                    if 'a' <= c <= 'f':
                        nmask |= (1 << (ord(c) - ord('a')))

                    if (nx, ny, nmask) in visited:
                        continue

                    visited.add((nx, ny, nmask))
                    q.append((nx, ny, nmask))

        steps += 1

    return -1
