30978번 - 버스 기사 집합지

문제

진주 나들이를 온 보선이는 나들이를 끝내고 원래 살던 곳인 서울로 돌아가려고 진주 개양터미널에 도착했다. 그런데 이게 무슨 일인가? 장난꾸러기인 버스 기사분들이 전부 숨어버리거나 사라져버렸다. 숨은 장소 $N$곳에 대한 힌트만 남겨 놓은 채….

개양터미널 매표원 수현이는 난처해졌지만 잘생긴 얼굴 하나만 믿고, 보선이한테 버스 기사분들을 꼭 찾아서 각 버스에 배정해 달라고 부탁을 했다. 보선이는 '돌아가는 교통편을 무료로 이용할 수 있겠지?'라는 마음으로 수현이의 부탁을 들어주기로 했다. 그와 동시에 자기가 돌아가는 교통편의 버스에 가장 실력이 좋은 버스 기사를 배정해야겠다고 다짐했다.

버스 기사의 운전 실력은 0ドル$ 이상 50ドル$ 이하의 정수로 표현할 수 있으며, 운전 실력의 수치가 높을수록 실력이 좋다. 또한 버스 기사분들이 숨은 곳을 버스 기사 집합지라고 부르며, 총 $N$곳이 있다.

어떠한 구간 $[A, B]$가 주어지고 구간 내에서 우수한 버스 기사 집합지를 찾고자 할 때, 다음과 같이 찾을 수 있다.

1. $A$번째 버스 기사 집합지에서 $B$번째 버스 기사 집합지까지 중 운전 실력이 50ドル$인 버스 기사가 있는 버스 기사 집합지를 전부 선택한다. 만약 그러한 버스 기사 집합지가 없다면 $A$번째 버스 기사 집합지에서 $B$번째 버스 기사 집합지까지 전부를 선택한다.
2. 1번 과정에서 여러 곳이 선택되었다면 그중에서 운전 실력이 49ドル$인 버스 기사가 있는 버스 기사 집합지를 선택한다. 만약 그러한 버스 기사 집합지가 없다면 직전 과정에서 선택된 곳 전체를 선택한다.
3. 2번 과정을 하나의 버스 기사 집합지가 선택될 때까지 찾는 운전 실력을 1ドル$씩 줄여가며 반복한다. 만약 운전 실력이 음수가 되었다면, 직전 과정에서 선택된 곳 전체를 선택하고 중단한다. 따라서, 우수한 버스 기사 집합지는 여러 곳일 수 있다.

또한, 어떠한 구간 $[A, B]$가 주어지고 구간 내에서 저조한 버스 기사 집합지를 찾고자 할 때, 다음과 같이 찾을 수 있다.

1. $A$번째 버스 기사 집합지에서 $B$번째 버스 기사 집합지까지 중 운전 실력이 50ドル$인 버스 기사가 없는 버스 기사 집합지를 전부 선택한다. 만약 그러한 버스 기사 집합지가 없다면 $A$번째 버스 기사 집합지에서 $B$번째 버스 기사 집합지까지 전부를 선택한다.
2. 1번 과정에서 여러 곳이 선택되었다면 그중에서 운전 실력이 49ドル$인 버스 기사가 없는 버스 기사 집합지를 선택한다. 만약 그러한 버스 기사 집합지가 없다면 직전 과정에서 선택된 곳 전체를 선택한다.
3. 2번 과정을 하나의 버스 기사 집합지가 선택될 때까지 찾는 운전 실력을 1ドル$씩 줄여가며 반복한다. 만약 운전 실력이 음수가 되었다면, 직전 과정에서 선택된 곳 전체를 선택하고 중단한다. 따라서, 저조한 버스 기사 집합지는 여러 곳일 수 있다.

따라서, 구간 $[A, B]$ 내에서 우수한 버스 기사 집합지와 저조한 버스 기사 집합지는 동일할 수 있다.

위와 같이 버스 기사와 버스 기사 집합지에 대한 정보를 얻은 보선이는 일이 수월할 것이라고 믿었지만, 장난꾸러기인 버스 기사분들은 한 곳에 가만히 있지 않는다. 갑자기 알 수 없는 곳으로 사라지기도 하고, 갑자기 나타날 수도 있으며, 다른 집합지로 이동할 수도 있다. 다행히 개양터미널에서 보낸 정보원 우근이 덕분에 버스 기사분들의 이동 정보를 쉽게 알 수 있었지만, 보선이는 점점 귀찮아져서 우리한테 대신 부탁을 해왔다.

이동 정보의 개수나 우수한 버스 기사 집합지 및 저조한 버스 기사 집합지를 알아내야 하는 횟수, 즉 모든 쿼리의 개수는 총 $Q$개다. 이를 우리가 대신 처리해 보자.

입력

첫 번째 줄에는 버스 기사 집합지의 개수 $N$이 주어진다. $(1 ≤ N ≤ 200,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 버스 기사 집합지에 있는 버스 기사의 수 $M_i$와 버스 기사의 운전 실력 $L_1,ドル $\dots,ドル $L_{M_i}$가 공백으로 구분되어 주어진다. 각 줄에 주어지는 $L_j$은 중복되지 않는다. $(1 ≤ M_i ≤ 50; 0 ≤ L_j ≤ 50)$

2ドル+N$번째 줄에는 쿼리의 개수 $Q$가 주어진다. $(1 ≤ Q ≤ 200,000円)$

3ドル+N$번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 다음과 같다.

• 1ドル$ $A$ $B$ $M$ $L_1$ $\dots$ $L_M$: $A ≤ i ≤ B$인 모든 $i$번째 버스 기사 집합지에 각각 운전 실력이 $L_1,ドル $\dots,ドル $L_M$인 버스 기사 1명씩 총 $M$명이 추가된다. 주어지는 $L_j$은 중복되지 않는다. $(1 ≤ A ≤ B ≤ N; 1 ≤ M ≤ 50; 0 ≤ L_j ≤ 50)$
• 2ドル$ $A$ $B$ $M$ $L_1$ $\dots$ $L_M$: $A ≤ i ≤ B$인 모든 $i$번째 버스 기사 집합지에서 $L_1,ドル $\dots,ドル $L_M$ 중 그 어떤 수치도 운전 실력으로 갖추지 않는 버스 기사는 전부 사라진다. 주어지는 $L_j$은 중복되지 않는다. $(1 ≤ A ≤ B ≤ N; 1 ≤ M ≤ 50; 0 ≤ L_j ≤ 50)$
• 3ドル$ $A$ $M$ $L_1$ $\dots$ $L_M$: $A$번째 버스 기사 집합지에서 $L_1,ドル $\dots,ドル $L_M$ 중 그 어떤 수치도 운전 실력으로 갖추지 않는 버스 기사는 전부 사라진다. 그리고 주어진 $L_1,ドル $\dots,ドル $L_M$에 대해 각각 $L_i$인 운전 실력을 갖춘 버스 기사가 $A$번째 버스 기사 집합지에 없다면 1명씩 추가 된다. 주어지는 $L_i$은 중복되지 않는다. $(1 ≤ A ≤ N; 1 ≤ M ≤ 50; 0 ≤ L_i ≤ 50)$
• 4ドル$ $A$ $B$: $A$번째 버스 기사 집합지에 있는 모든 버스 기사는 $B$번째 버스 기사 집합지로 가고, $B$번째 버스 기사 집합지에 있는 모든 버스 기사는 $A$번째 버스 기사 집합지로 간다. 즉, $A$번째 버스 기사 집합지의 버스 기사 상태와 $B$번째 버스 기사 집합지의 버스 기사 상태가 바뀐다. $(1 ≤ A ≤ B ≤ N)$
• 5ドル$ $A$ $B$: 구간 $[A, B]$ 내의 저조한 버스 기사 집합지에 있는 모든 버스 기사의 운전 실력을 중복을 제외하고 오름차순으로 출력한다. 만약 저조한 버스 기사 집합지에 버스 기사가 없다면 -1을 출력한다. $(1 ≤ A ≤ B ≤ N)$
• 6ドル$ $A$ $B$: 구간 $[A, B]$ 내의 우수한 버스 기사 집합지에 있는 모든 버스 기사의 운전 실력을 중복을 제외하고 오름차순으로 출력한다. 만약 우수한 버스 기사 집합지에 버스 기사가 없다면 -1을 출력한다. $(1 ≤ A ≤ B ≤ N)$
• 7ドル$ $A$ $B$: 구간 $[A, B]$ 내의 저조한 버스 기사 집합지가 구간 $[A, B]$ 내의 우수한 버스 기사 집합지가 되기 위해 최소 명수로 하여금 추가되어야 하는 모든 버스 기사의 운전 실력을 오름차순으로 출력한다. 단, 추가하는 버스 기사의 운전 실력은 구간 $[A, B]$ 내의 우수한 버스 기사 집합지에 있는 버스 기사의 운전 실력이어야 한다. 만약 버스 기사가 추가되지 않아도 구간 $[A, B]$ 내의 우수한 버스 기사 집합지가 될 수 있다면 -1을 출력한다. $(1 ≤ A ≤ B ≤ N)$

모든 쿼리는 주어지는 순서대로 한 번에 하나씩 진행되며, 출력을 요구하는 쿼리는 한 번 이상 주어진다. 그리고 입력으로 주어지는 모든 수는 정수이다.

출력

5, 6, 7번 쿼리에 대해 알맞은 정답을 한 줄에 하나씩 출력한다.

제한

노트

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.