동적 메모리 할당

카밀라는 새 프로그래밍 언어를 설계하고 있다. 메모리 관리 구문의 명세는 이미 정해 두었지만 구현은 아직 남아 있다. 명세대로 동작하는 메모리 관리 시스템을 만들어라.

사용할 수 있는 메모리는 $0$번부터 $n-1$번까지 번호가 붙은 $n$개의 바이트로 이루어진 배열이다. 처음에는 모든 바이트가 비어 있다. 즉 아무 바이트도 할당되지 않았다. 시스템은 주어진 질의를 순서대로 처리하면서 바이트를 할당하거나 해제한다.

할당 질의는 정수 $\ell$ 하나로 주어진다. 시스템은 비어 있는 바이트가 $\ell$개 연속한 구간을 찾아 그 구간을 할당하고, 첫 바이트의 번호를 반환한다. 그런 구간이 여러 개면 시작 번호가 가장 작은 구간을 고른다. 그런 구간이 없으면 질의를 거부하고 $-1$을 반환한다. 거부된 질의는 메모리 상태를 바꾸지 않는다.

해제 질의는 정수 두 개 $x$와 $\ell$로 주어진다. 시스템은 $x$번 바이트에서 시작하는 연속한 $\ell$개의 바이트를 비어 있는 상태로 바꾸고, 실제로 해제된 바이트의 개수를 반환한다. 실제로 해제된 바이트란 그 구간 안에서 질의 직전에 비어 있지 않았던 바이트를 말한다.

첫째 줄에 메모리의 바이트 수 $n$과 질의의 개수 $q$가 주어진다 ($1 \le n, q \le 3 \times 10^5$).

다음 $q$개의 줄에 질의가 하나씩 주어진다. 각 줄의 첫 정수는 질의의 종류이고, $1$은 할당, $2$는 해제를 뜻한다. 할당 질의는 이어서 정수 $\ell$이 하나 더 주어진다 ($1 \le \ell \le n$). 해제 질의는 이어서 정수 $x$와 $\ell$이 주어진다 ($0 \le x \le n-1$, $1 \le \ell \le n-x$).

질의마다 시스템이 반환한 값을 주어진 순서대로 한 줄에 하나씩 출력한다.