32387번 - 충전하기

문제

동우는 다양한 전자기기를 사용한다. 수많은 전자기기의 충전기를 모두 들고 다니는 것이 번거로웠던 동우는 $N$개의 포트가 있는 멀티 포트 충전기를 장만했다. 동우의 멀티 포트 충전기는 특이하여 각 포트별로 출력해주는 전력이 다르다. 구체적으로 동우가 구매한 멀티 포트 충전기의 $i$번 포트는 $i$만큼의 전력을 출력해준다.

동우는 다양한 전자기기로 작업을 하면서 총 $Q$번 충전기에 꽂거나 뽑을 것이다. 구체적으로 동우가 하는 행동은 2ドル$가지로 아래와 같은 입력으로 주어진다.

• 1 $i$: 최소 전력이 $i$인 전자기기를 $i$번 포트에 꽂는다. 만약 $i$번 포트에 전자기기가 꽂혀 있다면, 현재 남아 있는 최소 전력 이상의 포트 중 가장 전력이 작은 포트에 기기를 꽂는다. 만약 남아 있는 모든 포트가 최소 전력 미만이라면, 기기를 꽂지 않는다.
• 2 $i$: $i$번 포트에 기기가 꽂혀 있다면 기기를 뽑는다.

이때, 각 행동에 대해 다음을 출력하라.

• 1번 행동: 성공적으로 전자기기를 꽂았다면 포트의 번호를 출력하며, 꽂지 않았다면 -1을 출력한다.
• 2번 행동: 기기가 꽂혀 있었다면 몇 번째 행동에서 꽂힌 기기인지 출력하며, 꽂혀 있지 않았다면 -1을 출력한다. 여기서 몇 번째 행동인지는 1번과 2번을 행동을 합쳐서 센다.

입력

첫 번째 줄에 포트의 수 $N(1\leq N\leq 10^{6})$과 행동의 수 $Q(1\leq Q\leq 10^{6})$가 주어진다.

두 번째 줄부터 $Q$줄에 걸쳐 동우가 하는 행동의 타입 $t(t\in\{ 1,2 \})$와 포트 번호 또는 최소 전력을 의미하는 정수 $i(1\leq i\leq N)$가 공백으로 구분되어 주어진다.

출력

각각의 행동이 주어질 때마다 행동의 결과를 한 줄에 하나씩 출력한다.

제한

힌트