문제

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

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

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

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

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

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

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

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

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

입력

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

둘째 줄부터 Q개의 줄에 걸쳐 동작이 한 줄에 하나씩 주어진다. 동작은 1\ x\ y 또는 2\ y 또는 3이다. (1 ≤ x ≤ 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를 출력한다.