할아버지의 질문

마리차가 할아버지에게 동화를 들려주는데, 할아버지가 자꾸 이야기를 끊고 질문한다.

동화 속에서 어린이 $N$명이 기차를 탄다. 어린이에게는 나이순으로 $1$번부터 $N$번까지 번호가 붙어 있어서 $1$번이 가장 어리고 $N$번이 가장 나이가 많다. 기차는 $0$번 역에서 출발해 $1$번, $2$번, $3$번 역 순서로 끝없이 정차한다.

마리차의 진술은 모두 같은 형태다. $X$번 역에서 $A$번 어린이가 내렸다. 진술이 나오는 순서는 역 번호와 아무 상관이 없다. $X$번 역에서 내린 어린이는 역 $X$개만큼 탄 것으로 센다.

할아버지의 질문도 형태가 정해져 있다. 지금까지 나온 진술만 놓고 볼 때, 번호가 $B$ 이상인 어린이 중에서 탄 역이 $Y$개 이하인 어린이 가운데 가장 어린 어린이는 누구인가. 질문한 시점까지 내렸다는 진술이 나오지 않은 어린이는 영원히 타고 간다고 본다. 가장 어린 어린이는 번호가 가장 작은 어린이를 뜻한다.

답은 할아버지가 질문한 그 시점을 기준으로 맞아야 한다. 나중에 새 진술이 나와서 답이 달라져도 상관없다.

마리차의 진술을 반영하면서 할아버지의 질문에 답하는 프로그램을 작성하시오.

첫 줄에 어린이의 수 $N$과 줄의 수 $Q$가 주어진다 ($2 \le N, Q \le 200000$).

다음 $Q$개 줄은 각각 둘 중 하나다.

• 마리차의 진술 M X A. M은 마리차를 뜻하고, $X$와 $A$는 정수다 ($1 \le X \le 1000000000$, $1 \le A \le N$).
• 할아버지의 질문 D Y B. D는 할아버지를 뜻하고, $Y$와 $B$는 정수다 ($1 \le Y \le 1000000000$, $1 \le B \le N$).

마리차의 진술은 모두 서로 다른 어린이를 가리키고, 입력에는 할아버지의 질문이 적어도 한 줄 들어 있다.

질문마다 조건을 만족하는 어린이의 번호를 한 줄에 하나씩 출력한다. 그런 어린이가 없으면 -1을 출력한다.