28698번 - 스트릭과 쿼리

문제

solved.ac에서 정지당한 현제는 본인만의 새로운 스트릭 시스템을 만들어 MatKor에 적용하고자 한다.

우선 현제의 스트릭 시스템은 유저별로 독립적으로 동작하며 서로 영향을 주지 않는다. 어떤 유저의 스트릭을 결정하는 것은 다음과 같다.

• 먼저 유저는 문제를 풀면 그 문제의 풀이 코드를 한 번에 하나씩 제출할 수 있고, 채점 시스템은 정답일 경우 맞았습니다!!를, 오답일 경우 다른 결과를 보여준다.
• 특정 문제에 대한 “첫 정답 제출”이란, 시간순으로 나타냈을 때 기존에 그 문제에서 맞았습니다!!를 받은 적이 없으며, 처음으로 맞았습니다!!를 받은 제출이다.
• “재채점”이란 기존에 제출된 코드들을 다시 채점하는 것을 의미한다. 재채점을 통해 특정 문제의 정답 여부가 바뀌게 되었다면, 해당 문제에 대한 “첫 정답 제출”을 제출한 시간을 기준으로 다시 계산해 “첫 정답 제출”이 달라질 수 있다.
• 유저가 어떤 연속한 $d$일 동안 모든 날짜에 “첫 정답 제출”이 존재한다면 해당 유저가 “$d$-스트릭 그룹”에 포함된다고 한다.
• 유저별 최장 스트릭은 해당 유저가 포함되는 “$d$-스트릭 그룹” 중 가장 큰 $d$의 값이다.

현제는 MatKor 부원 $n$명을 1ドル$번 부터 $n$번까지 번호를 매겼고, 10ドル^5$개의 문제로 구성된 스트릭 시스템을 현제는 시간순으로 들어오는 $m$개의 쿼리를 통해 관리하고자 한다.

• 1 u p c: u번 유저가 p번 문제의 풀이 코드를 제출하여 정답 여부는 c이다. c가 1ドル$이면 맞았습니다!!, 0ドル$이면 오답을 의미한다.(1ドル\le u\le N,ドル 1ドル\le p\le 10^5,ドル $c\in\{0,1\}$)
• 2: 날짜가 다음 날로 바뀐다.
• 3 i: i번째 쿼리의 제출이 재채점되어 정답 여부가 반전된다. 즉, 기존의 정답은 오답으로, 오답은 정답으로 바뀐다.(1ドル\le i\le m,ドル $i$번째 쿼리는 주어진 1ドル$번 쿼리이다.)
• 4 k: 현재 시점에서 최장 스트릭이 k번째로 긴 유저의 최장 스트릭을 출력한다.(1ドル\le k\le N$) 이 쿼리는 적어도 하나 이상 주어진다.

입력

첫 줄에 유저의 수 $n$(1ドル\le n\le 10^5$)과 쿼리의 개수 $m$(1ドル\le m\le 10^5$)이 주어진다.

다음 $m$개의 줄에 시간순으로 다음 네 가지 중 하나의 쿼리가 한 줄에 하나씩 주어진다.

출력

4번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.

제한

힌트