题目内容

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

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

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

输入描述

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

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

对于所有输入数据，均满足 $1\le n\le 10^5，1\le q\le 10^6$ ，任何出现的序列编号 $i$ 都满足 $0\le i\lt n$ 。

序列中出现的任何数值 $x$ 均满足 $0\le x\le 10^9$ ，插入和删除操作中的数目 $k$ 满足 $1\le k \le 10^9$ 。

输出描述

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

样例

输入

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

输出

2
1
-1

样例解释

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

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

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