Design Front Middle Back Queue

Design a data structure called `FrontMiddleBackQueue`. It supports the following operations, where all indices are 0-based and the "middle" is defined as follows: - For a list of length `n`, the middle is at index `n//2` (integer division). For example: if `n=1`, middle index is 0; `n=2`, middle index is 1; `n=3`, middle index is 1; `n=4`, middle index is 2; `n=5`, middle index is 2. Implement the class with the following methods: - `__init__(self)` – initializes the queue as empty. - `push_front(self, val: int) -> None` – adds `val` to the front (index 0). - `push_middle(self, val: int) -> None` – adds `val` at the middle index (as defined above). Elements currently at that index and after shift right. - `push_back(self, val: int) -> None` – adds `val` to the back (end). - `pop_front(self) -> int` – removes and returns the front element. If the queue is empty, return `-1`. - `pop_middle(self) -> int` – removes and returns the middle element (the element at the middle index). If the queue is empty, return `-1`. - `pop_back(self) -> int` – removes and returns the back element. If the queue is empty, return `-1`. You may assume all values are integers. The method signatures must exactly match the descriptions above. Implement the class in Python using any approach you like (e.g., list, deque, or linked list). The operations will be called at most 1000 times in a single test run. **Constraints:** - At most 1000 calls total. - `val` is an integer between 0 and 10^9. **Complexity:** Aim for O(n) worst-case per operation (if using a list, shifting is O(n)). A more efficient O(1) per operation is possible with two deques or a linked list with a pointer to the middle, but not required. Your solution will be tested with a helper function `test_sequence(ops, vals)` that creates an instance and applies the operations in order, returning the results as a list. For example, given `ops = ["push_front", "push_back", "pop_front"]` and `vals = [1, 2, None]`, the helper should return `[None, None, 1]`. You must implement the class exactly as specified so this helper works.

```python
q = FrontMiddleBackQueue()
q.push_front(1)   # [1]
q.push_back(2)    # [1,2]
q.push_middle(3)  # [1,3,2]
q.push_middle(4)  # [1,4,3,2]
q.pop_front()     # returns 1, queue becomes [4,3,2]
q.pop_middle()    # returns 3, queue becomes [4,2]
q.pop_middle()    # returns 4, queue becomes [2]
q.pop_back()      # returns 2, queue becomes []
q.pop_front()     # returns -1
```