Find The Order In Which Pets Are Bought From The Pet Shop

The pet shop holds only dogs and cats. It operates on a “first-in, first-out” basis. People must adopt either the oldest of all animals in the shop or they can select whether they would prefer a dog or a cat but they cannot select which specific animal they would like. Each cat or dog that is bought into the shop is represented by a unique identification number.

There are two types of operations:-

1 ‘uID’ ‘type1’ - where 1 represents an animal is being brought into the shop. ‘uID’ represents a unique identification number allotted to the animal. ‘type1’ is 0 if animal is dog or 1 if animal is cat.

2 ‘type2’ - where 2 represents an animal is being adopted. ‘type2’ is 0 if the oldest dog is preferred. ‘type2’ is 1 if the oldest cat is preferred. ‘type2’ is 2 if either of them is preferred.

You have been given ‘n’ operations which you need to perform in the shop. Your task is to return a vector/list that contains the unique identification number of pets that are adopted in the order they are adopted.

Example :

Let's say the pet shop's oldest dog’s uID that has not yet been adopted is 4 and that of the oldest cat is 3.
If operation 2 0 is performed then the oldest dog will be adopted i.e uID 4. 
If operation 2 1 is performed then the oldest cat will be adopted i.e uID 3. 
If operation 2 2 is performed then the animal older among them will be adopted.

Input Format :

The first line contains a single integer ‘T' representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the number of operations.

Next ‘N' lines contain operations that have to be performed on the shop. Each operation is either of type 1 or 2.

Output Format :

For each test case print a vector/list that contains the unique identification number of pets that are adopted in the order they are adopted.

Note :

1. All the operations are valid. 
2. You do not need to print anything; it has already been taken care of. Just implement the function. 

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= uID <= 10^6
0 <= type1 <= 1
0 <= type2 <= 2


Time Limit: 1sec