연결된 수열의 과반수 원소

이 문제에서 수열의 최빈값은 수열 안에서 전체 길이의 절반보다 많이 등장하는 수를 뜻한다.

처음에 길이가 서로 다른 양의 정수 수열 $n$개가 주어진다. 번호는 $1$부터 $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을 출력한다. 각 $x_i$는 아직 존재하며 $1 \le x_i \le n + q$이고, 이어 붙인 수열은 비어 있지 않다고 보장된다. $x_i$가 서로 다르지 않을 수도 있다. 이 연산에서 만든 연결 결과는 이후 연산에 영향을 주지 않는다.
• 4 x_1 x_2 x_3: 수열 $x_1$과 $x_2$를 이어 붙여 번호가 $x_3$인 새 수열을 만들고, 수열 $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$을 사용한 연산이 없다고 보장된다.

첫 줄에 양의 정수 $n$과 $q$가 주어진다. $n, q \le 5 \times 10^5$이 보장된다.

다음 $n$개의 줄에서 $i$번째 줄은 번호가 $i$인 수열을 나타낸다. 각 줄의 첫 번째 음이 아닌 정수 $l_i$는 수열의 길이이며, 이어서 수열의 원소 $a_{i,1}, \ldots, a_{i,l_i}$가 순서대로 주어진다. $C_l = \sum l_i$라 하면 $C_l \le 5 \times 10^5$이고 $a_{i,j} \le n + q$이다.

다음 $q$개의 줄에는 위 형식의 연산이 한 줄에 하나씩 주어진다. 종류 3 연산에서 나열되는 수열 개수의 합을 $C_m$이라 하면 $C_m \le 5 \times 10^5$이다.

종류 3 연산마다 답을 한 줄에 하나씩 출력한다.

모든 데이터에 대해 $1 \le n, q, C_m, C_l \le 5 \times 10^5$이다.