재채점됨

이 문제는 테스트케이스가 빈약해서 의도하지 않은 풀이로 정답을 받는 경우가 있었습니다. 2026-05-23에 테스트케이스가 보강되어 재채점 되었습니다. 그로인해 채점 결과가 변했을 수도 있습니다.

나중에 변경사항을 따로 탭에서 모아볼 수 있도록 개발해보겠습니다. (조서현)

문제

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

냉장고의 공간은 무한정 크지 않다. 만약 냉장고의 부피가 $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$를 출력한다.