8004 - [NOI2022] 众数

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

一开始给定 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。

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

【样例解释 #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。
【数据规模】

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