A93155.「NOI2022」众数

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

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

有 $q$ 次操作，操作有以下类型:

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

从文件 major.in 中读入数据。

输入的第一行包含两个正整数 $n$ 和 $q$，分别表示数列的个数和操作的次数，保证 $n \le 5 \times {10}^5$、$q \le 5 \times {10}^5$。

接下来 $n$ 行，第 $i$ 行表示编号为 $i$ 的数列。每一行的第一个非负整数 $l_i$ 表示初始第 $i$ 号序列的数字个数，接下来有 $l_i$ 个非负整数 $a_{i,j}$ 按顺序表示数列中的数字。假定 $C_l = \sum l_i$ 代表输入序列长度之和，则保证 $C_l \le 5 \times {10}^5$、$a_{i,j} \le n + q$。

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

假定 $C_m = \sum m$ 代表所有操作 $3$ 需要拼接的序列个数之和，则保证 $C_m \le 5 \times {10}^5$。

输出到文件 major.out 中。

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

对于所有测试数据，保证 $1 \le n, q, C_m, C_l \le 5 \times {10}^5$。

$n, q$	$C_m, C_l$	测试点编号	特殊性质 A	特殊性质 B	特殊性质 C
$\le 300$	$\le 300$	$1 \sim 3$	否	否	是
$\le 4000$	$\le 4000$	$4 \sim 7$	否	否	是
$\le {10}^5$	$\le {10}^5$	$8$	是	是	是
$\le {10}^5$	$\le {10}^5$	$9$	是	否	否
$\le {10}^5$	$\le {10}^5$	$10$	否	是	否
$\le {10}^5$	$\le {10}^5$	$11 \sim 12$	否	否	是
$\le {10}^5$	$\le {10}^5$	$13$	否	否	否
$\le 5 \times {10}^5$	$\le 5 \times {10}^5$	$14$	是	是	是
$\le 5 \times {10}^5$	$\le 5 \times {10}^5$	$15$	是	否	否
$\le 5 \times {10}^5$	$\le 5 \times {10}^5$	$16$	否	是	否
$\le 5 \times {10}^5$	$\le 5 \times {10}^5$	$17 \sim 18$	否	否	是
$\le 5 \times {10}^5$	$\le 5 \times {10}^5$	$19 \sim 20$	否	否	否

特殊性质 A：保证 $n = 1$ 且没有操作 $4$。
特殊性质 B：保证任意时刻任何序列中只有数字 $1$ 和 $2$。
特殊性质 C：保证没有操作 $2$。