Hard Scheduling

Time limit1sMemory limit1024 MB

Summary

Apply Q commands that push a task to the front, sort the stack by ID ascending, or reverse it, then print the ID at position k.

Level: Medium5 of 10
Topics: Simulation, Sorting, Array
Solved: No attempts yet

Problem

Jihwan lives under a pile of work. Tasks come in by the dozens every day, more than he can count.

Each task has a unique positive integer ID $p_i$ ( $1 \leq p_i \leq N$ ). No two IDs are the same.

More work came in again. Fed up, Jihwan built a machine for scheduling, the 'Jihwanbot Scheduler', but it probably does not work quite right. The Jihwanbot Scheduler is basically a stack. That is, the task that was added last is processed first, following LIFO (Last In First Out).

Besides this basic behavior, these commands can be given to the Jihwanbot Scheduler:

0 p: Adds the task with ID $p$ to the scheduler. Unless another command changes it, a newly added task goes to the front of the scheduler. It becomes the task that must be processed first, regardless of its ID.
1: Sorts the tasks in the scheduler in ascending order of ID. Tasks with smaller IDs go closer to the front.
2: Reverses the processing order of the tasks in the scheduler. The tasks in the scheduler are processed in the opposite order.

The Jihwanbot Scheduler seems to have features that are not needed, but Jihwan expects to handle tasks more efficiently than before. After processing the $Q$ commands in order, find the ID of the task that is processed $k$ -th.

Input

The first line contains the ID range $N$ , the number of commands $Q$ , and $k$ . ( $1 \leq N, Q \leq 100000$ , $1 \leq k \leq$ the number of times command 0 appears)

From the second line onward, the $Q$ commands are given, one per line.

All numbers in the input are integers.

Output

After applying all commands in order, print the ID of the task that is processed $k$ -th.

Examples1

Example 1
Input
```
5 7 5
0 1
0 2
0 3
1
0 4
0 5
2
```
Expected output
```
5
```