문제

서현이는 딸기모찌를 너무나도 좋아한다. 서현이는 가게에서 딸기모찌를 사면 냉장고에 보관하고, 먹을 때는 가장 먼저 산 딸기모찌부터 먹는다. 같은 시간에 산 딸기모찌가 여러 개라면, 아무거나 하나 먹는다.

냉장고의 공간은 무한정 크지 않다. 만약 냉장고의 부피가 \(V\)라면, 딸기모찌는 최대 \(V\)개까지만 보관할 수 있다.

서현이가 수행할 \(Q\)개의 동작이 시간 순서대로 주어질 때 아래 동작을 처리하는 프로그램을 작성해 보자.

• 1 x y : \(x\) 종류의 딸기모찌를 \(y\)개 구입하고, 냉장고에 보관한다.

  • 냉장고의 공간이 부족하다면 가능한 개수만큼만 보관하고 나머지는 즉시 먹는다.
  • 냉장고가 이미 가득 찼다면 넣지 않고 즉시 먹는다.

• 2 y : 냉장고에서 가장 먼저 산 \(y\)개의 딸기모찌를 순서대로 먹는다.

  • 냉장고에 보관된 딸기모찌의 개수가 \(y\)개 이하라면, 보관된 딸기모찌를 다 먹는다.
  • 냉장고가 비었다면 아무것도 먹지 못한다.

• 3 : 냉장고에 남아있는 딸기모찌 중 가장 먼저 산 딸기모찌의 종류를 출력한다.

  • 냉장고가 비었다면 대신 -1를 출력한다.

입력

첫째 줄에 동작의 개수 \(Q(1 \le Q \le 50\,000)\)와 냉장고의 부피 \(V(1 \le V \le 200\,000\,000)\)가 공백으로 구분되어 주어진다.

둘째 줄부터 \(Q\)개의 줄에 걸쳐 동작이 한 줄에 하나씩 주어진다. 동작은 \(1\ x\ y\) 또는 \(2\ y\) 또는 \(3\)이다. \((1 \le x \le 100\, 000; 1\le y \le V)\)

입력으로 주어지는 수는 모두 정수이며, 3번 동작은 적어도 하나 주어진다.

출력

\(3\)번 동작의 답을 한 줄에 하나씩 출력한다.

예제 입력 1

10 8
1 1 5
1 2 5
2 3
3
2 2
3
2 3
3
2 1
3

예제 출력 1

1
2
-1
-1

• 1 1 5: 동작 수행 이후, 냉장고의 상태는 \([1, 1, 1, 1, 1]\)이다.
• 1 2 5: 동작 수행 이후, 냉장고의 상태는 \([1, 1, 1, 1, 1, 2, 2, 2]\)이다. 냉장고는 최대 \(8\)개의 딸기모찌를 보관할 수 있기 때문에 남은 \(2\)개는 바로 먹는다.
• 2 3: 동작 수행 이후, 냉장고의 상태는 \([1, 1, 2, 2, 2]\)이다.
• 3: 냉장고에 있는 딸기모찌 중 가장 먼저 산 딸기모찌의 종류는 \(1\)이므로 \(1\)을 출력한다.
• 2 2: 동작 수행 이후, 냉장고의 상태는 \([2, 2, 2]\)이다.
• 3: 냉장고에 있는 딸기모찌 중 가장 먼저 산 딸기모찌의 종류는 \(2\)이므로 \(2\)를 출력한다.
• 2 3: 동작 수행 이후, 냉장고의 상태는 \([]\)이다.
• 3: 냉장고가 비었으므로 \(-1\)를 출력한다.
• 2 1: 냉장고가 비었으므로 아무것도 먹지 못한다.
• 3: 냉장고가 비었으므로 \(-1\)를 출력한다.