New update is available. Click here to update.

Implement A PlatesStack

Posted: 23 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an infinite number of stacks which are arranged in a row. All the stacks have the same maximum capacity.

You are supposed to implement the PlatesStack class that can perform the following operations efficiently:

PlatesStack(int N) - Constructor to initialize the object where N denotes the maximum capacity of each stack.

push(int value) - This function inserts the integer "value" in the leftmost stack which is not filled up to the maximum capacity.  

pop() - This function returns the value at the top of the rightmost stack which is not empty and removes it from that stack or returns -1 if all the stacks are empty.

popAtStack(int index) - This function returns the value at the top of the stack with the given index and removes it from that stack and returns -1 if that stack is empty.

You have to answer multiple queries, each query will correspond to one of the above-mentioned operations.

TYPE 1 corresponds to the push operation.
TYPE 2 corresponds to the pop operation.
TYPE 3 corresponds to the popAtStack operation.  
Input Format :
The first line contains a single integer T denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer N denoting the maximum capacity of the stacks.

The second line of each test case contains an integer Q denoting the number of queries to be answered.

The next Q lines contain two integers TYPE and X separated by a single space. The integer TYPE denotes the type of the query and X denotes the value or the index of the stack on which the operation is to be performed.
For TYPE-2 query, value of X is always -1. You can ignore this integer. 
Output Format :
For each query of type 2 print the value at the top of the rightmost stack or print -1 if all the stacks are empty.
For each query of type 3 print the value at the top of the stack with the given index or print -1 if the stack at the given index is empty. 

Print the answer for query in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given class.
Constraints :
1 <= T <= 5
1 <= N <= 10
1 <= Q <= 1000
1 <= TYPE <= 3
1 <= value <= 10^9

Where "value" is the integer to be inserted into the stack or the index of the stack depending on the type of the query.

Time Limit: 1 sec