메모리 관리자

페테는 H++ 언어의 새 표준 라이브러리를 위한 메모리 관리자를 작성하라는 임무를 받았다. 관리자는 1번부터 N번까지 번호가 붙은 N개의 연속된 메모리 셀 배열을 사용한다. 관리자의 임무는 응용 프로그램의 메모리 할당 및 해제 요청을 처리하는 것이다.

메모리 할당 요청은 매개변수 K를 하나 가진다. 이 요청은 응용 프로그램이 K개의 연속된 메모리 셀을 할당해 달라고 요청하는 것이다. 관리자가 K개의 연속된 셀로 이루어진 빈 블록을 하나라도 가지고 있으면, 요청에 대한 응답으로 그러한 블록을 반드시 할당해야 한다. 이때 할당하는 블록의 첫 번째 셀 바로 앞에는 빈 셀이 있어서는 안 된다. 그 후 할당된 셀은 사용 중이 되어 해제될 때까지 메모리 할당에 사용할 수 없다. K개의 연속된 빈 셀로 이루어진 블록이 없으면 요청은 거부된다.

메모리 해제 요청은 매개변수 T를 하나 가진다. 이 요청은 관리자가 순번 T의 요청을 처리할 때 할당했던 메모리를 해제해야 한다는 뜻이다. 요청의 번호는 1부터 시작한다. 번호가 T인 요청은 할당 요청이며 아직 해제가 적용되지 않았음이 보장된다. 해제된 셀은 다시 메모리 할당에 사용할 수 있다. 번호가 T인 요청이 거부되었다면 현재 메모리 해제 요청은 무시된다.

주어진 조건을 만족하는 메모리 관리자를 작성해야 한다.

입력 파일의 첫 번째 줄에는 수 N과 M이 주어진다. N은 메모리 셀의 개수, M은 요청의 개수이다 (1 ≤ N ≤ 231 – 1; 1 ≤ M ≤ 105). 다음 M개의 줄에는 각각 수가 하나씩 들어 있다. 입력 파일의 (i+1)번째 줄 (1 ≤ i ≤ M)에는 i번째 요청이 매개변수 K를 가진 할당 요청이면 양수 K가 (1 ≤ K ≤ N), i번째 요청이 매개변수 T를 가진 해제 요청이면 음수 –T가 들어 있다 (1 ≤ T < i).

각 메모리 할당 요청에 대해 그 요청의 처리 결과를 출력 파일에 출력한다. 성공한 요청에 대해서는 할당된 블록의 첫 번째 메모리 셀 번호를, 거부된 요청에 대해서는 –1을 출력한다. 결과는 입력 파일에서 요청이 나온 순서대로 출력해야 한다.