가희의 수열놀이 (Large)
시간 제한1초메모리 제한256 MB
스택에 값을 넣고 빼는 연산을 처리하면서, 3번 질의마다 접미사 중 나머지 0부터 mod-1까지가 모두 한 번 이상 나타나는 가장 짧은 길이를 구하고 불가능하면 -1을 출력한다.
문제
chogahui는 수열 arr로 나머지 놀이를 하고 있다. chogahui는 수열에 다음 연산을 할 수 있다.
- 수열 arr의 맨 뒤에 num을 추가한다.
- 수열 arr의 맨 뒤에 있는 원소를 제거한다.
chogahui가 던지는 질문은 다음과 같다.
- 수열 arr의 맨 뒤에서부터 최소 몇 개의 수를 선택해야, 이들을 mod로 나눈 나머지가 0, ..., mod-1인 경우가 한 번 이상씩 모두 나타나는가?
chogahui의 질문에 답해 주자.
입력
첫째 줄에 쿼리의 수 Q와 나누는 정수 mod가 공백으로 구분되어 주어진다. (1 ≤ Q ≤ 10^6, 1 ≤ mod ≤ 2×10^9)
이어서 Q개의 줄에 걸쳐 다음 세 종류의 쿼리 중 하나가 주어진다. 맨 앞에 오는 정수 1, 2, 3으로 종류를 구분한다.
- 1 num : 수열 arr의 맨 뒤에 num을 추가한다. (1 ≤ num ≤ 2^31-1)
- 2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 수열이 비어 있으면 무시한다.
- 3 : chogahui가 요구하는 쿼리의 값을 계산한다.
처음에 수열 arr은 비어 있다.
출력
3번 쿼리가 들어올 때마다 chogahui가 요구한 쿼리의 값을 출력한다. 3번 쿼리는 입력에 1개 이상 존재한다. 3번 쿼리의 답이 존재하지 않으면 -1을 출력한다.