SP28597 BDOI16A - Guess the Queue

**Guess the Queue** Busland is a city where the only means of transportation are buses. To get on a bus in Busland, people have to wait in queue. Each person has a **unique** bus **ID**. The person at the front is considered the first person and the person at the back is considered the last person in the queue. Trivially, the first person will get on the bus first and the last person will get on last. It is well known that you should enter at the back of the queue. However, some people are very late and even though it is considered very rude, they try to enter in an alternative way. Since the sides of the queue are barricaded, the only alternative way is to enter from the front of the queue. Sometimes there are also people at the back of the queue, who become tired of waiting. They exit the queue from the back and just start walking to their destination instead. Your task is to deal with three types of operations as follows: 1\. ‘**1** _**x y**_’ The person with **ID** _**y**_ enters from the back or front, if _**x**_ is ‘**B**’ or ‘**F**’ respectively. 2\. ‘**2** _**x’**_ The person in the back or front exits the queue, if _**x**_ is ‘**B**’ or ‘**F**’ respectively. 3\. ‘**3** _**x y’**_ Find the **ID** of the person in the _**y**_th position of the queue or the position of the queue, where the person with **ID** _**y**_ is currently situated, if _**x**_ is ‘**D**’ or ‘**P**’ respectively. **Input:** The first line of input will contain the number of test cases, _**T**_ **(1

N/A

N/A