시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB5161226719.940%

문제

chogahui는 수열 arr을 이용해 나머지 놀이를 하고 있습니다. 조가희는 수열에 다음과 같은 연산을 할 수 있습니다.

  • 수열 arr의 맨 뒤에 num을 추가합니다.
  • 수열 arr의 맨 뒤에 있는 원소를 제거합니다.

chogahui가 물어보는 질문은 다음과 같습니다.

  • 수열 arr맨 뒤에서부터 최소 몇 개의 수를 선택해야, 이들을 mod로 나누었을 때 나머지가 0, ... , mod-1인 경우가 최소 한 번 이상 나타나는가?

chogahui의 질문을 해결해 주세요.

입력

첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 106, 1 ≤ mod ≤ 2×109)

이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어집니다. 이는 맨 앞에 오는 정수의 값 (1, 2, 3)에 따라 구분됩니다.

  • 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 231-1)
  • 2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 만약 arr이 비어있으면 무시한다.
  • 3 : chogahui가 요구하는 쿼리에 대한 값을 계산한다.

처음에 수열 arr은 비어 있습니다.

출력

chogahui가 요구한 쿼리에 대한 값을 3번 쿼리가 들어올 때마다 출력합니다. 3번 쿼리는 입력에 1개 이상 존재합니다. 3번 쿼리에 대한 답이 존재하지 않는 경우에는 -1을 출력한다.

예제 입력 1

6 4
1 2
1 3
3
1 1
1 4
3

예제 출력 1

-1
4

출처