This is a simple data structures problem. Your goal is to complete the stack ADT and evaluate its functions.

Input:

• First line will contain $T$, number of testcases. Then the testcases follow.
• Each testcase contains integers N, M, where N is the size of the stack, and M is the number of operations in the test case. Next line will include the size, and next M lines will include series of operations of the following type Character, value, where character indicates the stack operation $P-push, O-pop, T-top, S-size, I-isempty, F-other function specified$. For push, it is followed by a value, others will not be followed by a value. The goal of delMid is to delete the middle element of the stack, while using only the stack push or pop functions. If even, the mid is the left one of the two middle elements. This function is denoted by F.

Output:

For each testcase, output the result of each operation separated by a newline. The output of Push should be the content of the stack (print function given). Pop should output the popped value, top the value on top, size the size of the stack, and isEmpty should return true or false. If stack full when Push, return StackFullException case sensitive. If stack empty when pop or top, return StackEmptyException case sensitive. For delMid, output will be final stack content after the removal of middle element, and will include the content of the stack when stack functions used.

Since intermediate outputs are tracked in the test cases, do not modify the driver code.

Subtasks

Constraints

• 1 \leq T \leq 10
• 10 \leq N \leq 100

Sample Input:

    1
    5
    10
    S
    I
    P 4
    P 2
    T
    P 3
    P 5
    S
    P 9
    P 10

Sample Output:

    0
    True
    4
    4 2
    2
    4 2 3
    4 2 3 5
    4
    4 2 3 5 9
    StackFullException
    4 2 3 5 9

EXPLANATION: