Under construction

Still being built. Things may change

Streaks and Queries

Time limit1sMemory limit1024 MB

Summary
Given submissions, verdict flips, and day advances, print the longest streak of the user whose streak ranks k-th largest.
Level

Hard8 of 10

Topics
Segment tree, Hash map, Implementation
Solved
No attempts yet

Problem

Hyunje was suspended from solved.ac, so he wants to build his own streak system and apply it to MatKor.

Each user's streak system works independently and does not affect the others. A user's streak is determined as follows.

  • A user submits solution code for a problem one at a time. The judge shows 맞았습니다!! for a correct answer and a different result for a wrong answer.
  • The "first accepted submission" for a problem is, in time order, the first submission that receives 맞았습니다!! for that problem. No earlier submission for that problem received 맞았습니다!!.
  • "Re-judging" means judging previously submitted code again. If re-judging changes whether a problem is correct, the "first accepted submission" for that problem is recalculated based on submission time, and it may change.
  • If a user has a "first accepted submission" on every day of d consecutive days, the user belongs to a "d-streak group."
  • A user's longest streak is the largest d among all "d-streak groups" that the user belongs to.

Hyunje numbered the n members of MatKor from 1 to n. He wants to manage this streak system, which covers 10^5 problems, with m queries that arrive in time order.

  • 1 u p c: User u submitted solution code for problem p, and the verdict is c. If c is 1, the answer is 맞았습니다!!. If c is 0, the answer is wrong. (1≤u≤N1\le u\le N, 1≤p≤1051\le p\le 10^5, c∈{0,1}c\in\{0,1\})
  • 2: The date changes to the next day.
  • 3 i: The submission from the i-th query is re-judged, and its verdict is flipped. A previously correct answer becomes wrong, and a wrong answer becomes correct. (1≤i≤m1\le i\le m, and the i-th query is a type 1 query.)
  • 4 k: Print the longest streak of the user whose longest streak is the k-th largest at this moment. (1≤k≤N1\le k\le N) At least one query of this type is given.

Input

The first line contains the number of users n (1≤n≤1051\le n\le 10^5) and the number of queries m (1≤m≤1051\le m\le 10^5).

The next m lines contain the queries in time order, one per line, each being one of the four types above.

Output

For each type 4 query, print the answer on its own line, in the order the queries appear.

Examples2

  1. Example 1

    Input
    4 11
1 1 1 1
1 2 1 0
1 3 2 1
1 4 1 0
2
1 1 2 1
4 1
3 2
4 3
3 6
4 1
    Expected output
    2
1
1

  2. Example 2

    Input
    3 25
1 1 1 1
1 1 2 0
1 2 1 1
1 3 4 1
2
1 1 2 1
1 2 5 0
4 1
2
1 1 3 1
4 3
1 2 5 1
1 2 6 0
2
1 2 8 1
4 1
3 2
4 1
3 7
4 1
3 13
4 1
4 3
3 4
4 3
    Expected output
    2
1
3
2
2
4
1
0