时间限制： 1.0 秒

空间限制： 512 MB

题目描述

有 $n$ 个序列（依次编号为 $0,1,...,n-1$），初始时各个序列都为空，你的任务是维护这 $n$ 个序列，需要进行的各种操作的表示与意义如下：

• $1~i~k~x$：在第 $i$ 个序列的末尾插入 $k$ 个值都为 $x$ 的数；
• $2~i~k$：删除第 $i$ 个序列末尾的 $k$ 个数，若该序列已不足 $k$ 个数，则删除序列中全部的数；
• $3~i$：询问第 $i$ 个序列的众数。

其中，一个序列的众数定义为该数列中出现次数最多的数，若出现次数最多的数有多种，取其中数值最小的数。

输入格式

从标准输入读入数据。

输入的第一行为两个正整数 $n,q$，表示序列的个数与操作次数。

接下来 $q$ 行描述依次进行的操作，每行描述一个操作，每个操作的输入方式同题目描述。

输出格式

输出到标准输出。

对于每个询问操作，输出询问时对应序列中出现次数最多的数中数值最小者，并换行。

2 6
1 0 2 1
1 0 3 2
3 0
2 0 1
3 0
3 1

2
1
-1

样例 1 解释

第 $1$ 次询问时，$0$ 号序列为 $1~1~2~2~2$，唯一众数为 $2$ 。

第 $2$ 次询问时，$0$ 号序列为 $1~1~2~2$，两种数都出现了 $2$ 次，取较小的 $1$。

第 $3$ 次询问时，$1$ 号序列为空，输出 $-1$。

子任务

对于所有输入数据，均满足 $1\le n\le 10^5,~1\le q\le 10^6$，任何出现的序列编号 $i$ 都满足 $0\le i<n$，序列中出现的任何数值 $x$ 均满足 $0\le x \le 10^9$，插入和删除操作中的数目 $k$ 满足 $1\le k\le 10^9$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

提示

本题输入量较大，请采用效率较高的读入方式。