Three in one

Given a sequence of queries of insertion and deletion from 3 stacks, you need to implement three stacks using a single array such that the size of the array doesn’t exceed the number of queries.

In each query, the input is of two types :

Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack.

Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

After each pop operation, you have to print the element which is removed.

Note: If a pop operation is used in an empty stack nothing happens to the stack, but you have to print -1.

Input Format :

The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘Q’ denoting the number of queries.

In the next Q lines input is either of the types :

    Id 0: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 0 means we have to pop a top element from the stack. 

    Id 1 ele: where ‘id’ is the index of the stack ( out of the three ) in which we have to work on, 1 means we have to push ‘ele’ element on top of the stack.

Output Format :

For each query of type 0, If the stack is non-empty print the removed element.

If a stack is empty print -1.

Print each element in the new line.

Constraints :

1 <= T <= 3
0 <= Q, ele  <= 10^5
0 <= id <= 2  , denoting one of the three stack

Time Limit : 1 sec