题解 | 众数

import sys
from collections import defaultdict


def main():
    # 读取输入（处理大数据量时用sys.stdin更高效）
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    q = int(input[ptr])
    ptr += 1

    # 初始化每个序列的结构：
    # freq: 字典，key=数值，value=该数值的总次数
    # ops: 栈，存储操作记录 (type, x, cnt)
    #      type=1: 插入操作；type=2: 删除操作（实际是回退插入）
    # total_len: 序列的总长度
    sequences = []
    for _ in range(n):
        sequences.append({"freq": defaultdict(int), "ops": [], "total_len": 0})

    for _ in range(q):
        op_type = int(input[ptr])
        ptr += 1
        i = int(input[ptr])
        ptr += 1
        seq = sequences[i]

        if op_type == 1:
            # 操作1: 1 i k x - 插入k个x
            k = int(input[ptr])
            ptr += 1
            x = int(input[ptr])
            ptr += 1

            if k <= 0:
                continue  # 无效操作，跳过

            # 更新频率和总长度
            seq["freq"][x] += k
            seq["total_len"] += k
            # 记录操作，用于后续删除
            seq["ops"].append((1, x, k))

        elif op_type == 2:
            # 操作2: 2 i k - 删除末尾k个元素
            k = int(input[ptr])
            ptr += 1

            if seq["total_len"] == 0 or k <= 0:
                continue  # 无元素可删，跳过

            # 实际要删除的数量（不超过当前总长度）
            del_cnt = min(k, seq["total_len"])
            seq["total_len"] -= del_cnt

            # 从操作栈中回退，直到删够数量
            while del_cnt > 0 and seq["ops"]:
                last_op = seq["ops"][-1]
                last_type, last_x, last_k = last_op

                if last_type == 1:
                    # 上一个是插入操作，尝试回退
                    take = min(del_cnt, last_k)
                    # 更新频率
                    seq["freq"][last_x] -= take
                    if seq["freq"][last_x] == 0:
                        del seq["freq"][last_x]  # 清理次数为0的键

                    # 更新操作栈
                    if take == last_k:
                        seq["ops"].pop()
                    else:
                        seq["ops"][-1] = (1, last_x, last_k - take)

                    del_cnt -= take

        elif op_type == 3:
            # 操作3: 3 i - 查询众数
            if seq["total_len"] == 0:
                print(-1)
                continue

            # 找次数最多且数值最小的数
            max_count = -1
            res = -1
            # 按数值升序遍历，确保次数相同时取最小的
            for x in sorted(seq["freq"].keys()):
                cnt = seq["freq"][x]
                if cnt > max_count:
                    max_count = cnt
                    res = x
            print(res)


if __name__ == "__main__":
    main()