수채화

마린초는 수채화 그리기를 좋아한다. 그는 $N$개의 칸으로 이루어진 색 수열을 만들려고 한다. 각 칸 $i$ ($1 \le i \le N$)에 대해 크기가 $K_i$인 색 집합 $A_i$를 고르고, 이 색들을 섞어 칸을 칠한다.

마린초는 이미 $A_l, A_{l+1}, \dots, A_r$에 따라 칸 $l$부터 $r$까지를 칠했다. 이제 나머지 칸을 정해진 순서대로 칠한다. 다음에 칠할 칸은 존재하는 쪽의 $l-1$ 또는 $r+1$번 칸이다. 칠한 칸이 $L$부터 $R$까지일 때 다음 칸은 다음과 같다.

• $L = 1$이고 $R = N$이면 모든 칸을 칠한 상태이다.
• $L = 1$이고 $R < N$이면 다음 칸은 $R+1$이다.
• $L > 1$이고 $R = N$이면 다음 칸은 $L-1$이다.
• $L > 1$이고 $R < N$이면 다음 칸은 $L-1$ 또는 $R+1$이다.

마린초는 칸 $l$부터 $r$까지를 칠한 뒤 수열이 너무 단조롭다고 느꼈다. 그래서 앞으로 칠하는 칸마다, 지금까지 칠한 칸 어디에서도 쓰이지 않은 새 색이 최소 하나 있어야 한다고 정했다. 나머지 칸을 모두 칠할 수 있는지 판별하는 프로그램 aquarelle을 작성하라. $Q$개의 초기 칠하기 각각에 대해 답을 구하라.

첫 줄에 $N$이 주어진다. 이어서 $N$개의 줄에 각각 $K_i$와 색 $c_1 \ c_2 \dots \ c_{K_i}$가 주어진다. 색은 서로 다른 양의 정수이다. 다음 줄에 $Q$가 주어지고, 마지막 $Q$개의 줄에 $l$과 $r$이 주어진다. 각 줄의 수는 공백 한 칸으로 구분된다.

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq K_i \leq 1.2 \times 10^6$, $K_1 + K_2 + \dots + K_N \leq 1.2 \times 10^6$
• $1 \leq c_j \leq 10^6$
• $1 \le l \le r \le N$
• $1 \leq Q \leq 5$

입력 순서대로 각 초기 칠하기마다 나머지 칸을 모두 칠할 수 있으면 1, 없으면 0을 출력한다.

첫 번째 초기 칠하기를 분석해 보자. 최적의 순서는 아래 표와 같다.

5번 칸을 처음에 칠했다면 모든 칸을 칠하지 못했을 것이라는 점에 주목하라.

세 번째 초기 칠하기를 분석해 보자.

6번 칸을 처음에 칠해도 이후 과정은 같고 여전히 실패한다. 따라서 답은 0이다.