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

Input: First line will contain $T$, number of testcases. Then the testcases follow. Each testcase contains an integers M. M is the number of operations to be performed 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 and I-isempty. 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 s empty when pop or top, return StackEmptyException case sensitive.

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

Subtasks

Constraints

1<=M<=10

Sample Input:

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

Sample Output:

    0
    True
    4
    2 4
    2
    3 2 4
    5 3 2 4
    4
    9 5 3 2 4
    10 9 5 3 2 4