8004 - [NOI2022] 众数

通过次数

1

提交次数

4

时间限制 : 3 秒
内存限制 : 512 MB

对于一个序列,定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入,在本题中请以题面中给出的定义为准。

一开始给定 n 个长度不一的正整数序列,编号为 1 ~n,初始序列可以为空。这 n 个序列被视为存在,其他编号对应的序列视为不存在。

有 q 次操作,操作有以下类型:

  • 1 x y:在 x 号序列末尾插入数字 y。保证 x 号序列存在,且 1 ≤ x, y ≤ n + q。
  • 2 x:删除 x 号序列末尾的数字,保证 x 号序列存在、非空,且 1 ≤ x ≤ n + q。
  • 3 m x1 x2 xm:将 x1, x2, ..., xm 号序列顺次拼接,得到一个新序列,并询问其众数。如果不存在满足上述条件的数,则返回 -1。数据保证对于任意 1 ≤ i ≤ m,xi 是一个仍然存在的序列,1 ≤ xi ≤ n + q,且拼接得到的序列非空。注意:不保证 x1, ... , xm 互不相同,询问中的合并操作不会对后续操作产生影响。
  • 4 x1 x2 x3:新建一个编号为 x3 的序列,其为 x1 号序列后顺次添加 x2 号序列中数字得到的结果,然后删除 x1, x2 对应的序列。此时序列 x3 视为存在,而序列 x1, x2 被视为不存在,在后续操作中也不会被再次使用。保证 1 ≤ x1, x2, x3 ≤ n + q、x1 ne x2、序列 x1, x2 在操作前存在、且在操作前没有序列使用过编号 x3。

输入

输入的第一行包含两个正整数 n 和 q,分别表示数列的个数和操作的次数,保证 n ≤ 5 x 10^5、q ≤ 5 x 10^5。

接下来 n 行,第 i 行表示编号为 i 的数列。每一行的第一个非负整数 li 表示初始第 i 号序列的数字个数,接下来有 li 个非负整数 a{i,j} 按顺序表示数列中的数字。假定 Cl = ∑ li 代表输入序列长度之和,则保证 Cl ≤ 5 x 10^5、a{i,j} ≤ n + q。

接下来 q 行,每行若干个正整数,表示一个操作,并按照题面描述中的格式输入。

假定 Cm = ∑ m 代表所有操作 3 需要拼接的序列个数之和,则保证 Cm ≤ 5 x 10^5。

输出

对于每次询问,一行输出一个整数表示对应的答案。

样例

输入

2 8
3 1 1 2
3 3 3 3
3 1 1
3 1 2
4 2 1 3
3 1 3
2 3
3 1 3
1 3 1
3 1 3

输出

1
3
-1
3
-1

输入

4 9
1 1
1 2
1 3
1 4
3 4 1 2 3 4
1 1 2
3 2 1 2
2 3
3 3 1 2 3
1 4 4
1 4 4
1 4 4
3 4 1 2 3 4

输出

-1
2
2
4

提示

【样例解释 #1】
第一次询问查询序列 1 的众数。由于序列包含两个 1,超过序列长度的一半,因此众数为 1。
第二次询问查询序列 2 的众数。由于序列只包含 3,因此众数为 3。
第三次询问询问序列 3 的众数。此时序列 3 为 (3, 3, 3, 1, 1, 2),不存在出现次数大于 3 次的数,因此输出为 -1。
【样例解释 #2】
第一次询问查询序列 1, 2, 3, 4 拼接后得到的序列的众数。拼接的结果为 (1, 2, 3, 4),不存在出现次数大于两次的数,因此输出为 -1。
第四次询问查询序列 1, 2, 3, 4 拼接后得到的序列的众数。拼接的结果为 (1, 2, 2, 4, 4, 4, 4),众数为 4。
【数据规模】

注:本题数据为模拟数据。