Migrated from Lutece 2837 Nearest Shelter

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Due to a natural disaster, $n$ shelters have been built, labeled from $1$ to $n$. To prevent overcrowding, people can only get to the shelter labeled $i+1$ from the shelter labeled $i$.

The following events may occur:

• A Shelter Destroyed by Natural Disaster
• A person sends a distress signal from a location and wants to know the label of the nearest shelter he can get to.

You need to output the answer for each distress signal. If no such shelter exists, output $-1$.

Input

The first line contains two numbers, $n,m\ (1\le n\le 10^9,1\le m\le 10^5)$, representing the number of shelters and events.

For the next $m$ lines, each line contains two integers $\text{op}, \text{pos}\ (1\le \text{op}\le 2, 1\le \text{pos}\le n)$.

• If $\text{op}=1$, the shelter in $\text{pos}$ is destroyed. It is possible that this shelter has been destroyed before this event. If this shelter has been destroyed, please ignore this event.
• If $\text{op}=2$, there is a person in the shelter in $\text{pos}$ who has sent a signal. It is possible that the shelter has already been destroyed.

Output

For each query, output an integer, representing the nearest shelter's label.

Samples

4 5
2 4
1 3
2 3
1 4
2 3

4
4
-1

Resources

The 18th UESTC Programming Contest Preliminary