Aquarelle

Marincho loves to paint with watercolors. He wants to make a color sequence of $N$ cells. For each cell $i$ ($1 \le i \le N$), he picks a set of colors $A_i$ of size $K_i$, mixes them, and paints the cell with the result.

He has already painted cells $l$ through $r$ using $A_l, A_{l+1}, \dots, A_r$. He now paints the remaining cells in a fixed order. The next cell to paint is cell $l-1$ or $r+1$, whichever exists. If the painted cells are $L$ through $R$, the next cell is:

• If $L = 1$ and $R = N$, all cells are painted.
• If $L = 1$ and $R < N$, the next cell is $R+1$.
• If $L > 1$ and $R = N$, the next cell is $L-1$.
• If $L > 1$ and $R < N$, the next cell is $L-1$ or $R+1$.

After painting cells $l$ through $r$, Marincho finds the sequence too monochromatic. Every cell he paints from now on must contain at least one new color, one that appears in no cell painted so far. Write a program aquarelle that determines whether the remaining cells can all be painted. Answer this for each of the $Q$ initial paintings.

The first line contains $N$. Each of the next $N$ lines contains $K_i$ followed by the colors $c_1 \ c_2 \dots \ c_{K_i}$, which are distinct positive integers. The next line contains $Q$. Each of the last $Q$ lines contains $l$ and $r$. Numbers on a line are separated by one space.

• $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$

For each initial painting, in input order, print 1 if the remaining cells can be painted, otherwise print 0.

Let us analyze the first initial painting. An optimal order is shown in the table below.

Note that if cell 5 were painted first, the painting could not be completed.

Let us analyze the third initial painting.

Note that if cell 6 were painted first, the later steps would be the same and the painting would still fail. The answer here is 0.