Charging

Dongwoo uses many different electronic devices. Carrying every charger was a hassle, so Dongwoo bought a multi-port charger with $N$ ports. Unlike ordinary chargers, each port outputs a different amount of power. Port $i$ outputs $i$ units of power.

During the next $Q$ actions, Dongwoo plugs devices into the charger or unplugs them. There are two kinds of action, given as input in the following format.

• 1 $i$: Plug in a device whose minimum required power is $i$ into port $i$. If port $i$ already has a device, plug the device into the empty port with the smallest power that is at least the minimum power $i$. If every empty port has less power than $i$, do not plug in the device.
• 2 $i$: If a device is plugged into port $i$, unplug it.

The first line contains the number of ports $N$ ($1 \leq N \leq 10^{6}$) and the number of actions $Q$ ($1 \leq Q \leq 10^{6}$). Each of the next $Q$ lines contains an action type $t$ ($t \in \{1, 2\}$) and an integer $i$ ($1 \leq i \leq N$), separated by a space.

For each action, print the result on its own line.

For a 1 action, print the port number if the device was plugged in, or -1 if it was not.

For a 2 action, print the number of the action that plugged in the device currently in port $i$ if there is one, or -1 if the port is empty. Actions of both types are counted together, starting from 1.