aquarelle

Marincho has a new passion - he loves to paint with watercolors. Now he wants to make a color sequence of $N$ cells. For each cell $i \ (1 \le i \le N)$, Marincho has chosen a set of colors $A_i$ of size $K_i$, which he will mix, to paint the cell fulfilling his aesthetic feel. He has already done an initial painting of all cells numbered from $l$ to $r$ in the described manner and is now about to paint the remaining cells. Marincho follows a strictly defined order of painting the cells - the next cell that can be painted will be the one with number $l-1$ or $r+1$ (if they exist). Formally, if he has already painted all cells numbered from $L$ to $R$, then the next possible cells to paint are:

• If $L = 1$ and $R = N$, then all cells have been painted.
• If $L = 1$ and $R < N$, then the next cell, which can be painted, is the one with number $R+1$.
• If $L > 1$ and $R = N$, then the next cell, which can be painted, is the one with number $L-1$.
• If $L > 1$ and $R < N$, then the next cell, which can be painted, is the one with number $L-1$ or $R+1$.

Task

Unfortunately, after Marincho has painted the cells numbered from $l$ to $r$ according to the corresponding sets $A_l, A_{l+1}, \dots, A_r$, Marincho thinks that the sequence has become too monochromatic. Therefore, he decided that for every next cell, he paints, there has to be at least one new color, which hasn't been used in the painted cells until now. Help Marincho by writing a program that finds whether it is possible to paint the remaining cells. Also, you have to find the answer for a few initial paintings - $Q$ pairs $l$ and $r$.

Input data

The first line of the standard input contains the positive integer $N$ -- the number of cells. The following $N$ lines contain $K_i$ and $c_1 \ c_2 \dots \ c_{K_i}$ which describe the number of colors of the corresponding set $A_i$ and the colors themselves (the colors are different positive integers). The next line contains the positive integer $Q$ -- the number of initial paintings. The last $Q$ lines contain pairs of positive integers $l$ and $r$ that specify which sequence has been painted initially.

The numbers in each line are separated by one space.

Output data

For each initial painting, in input order, print $1$, if it is possible to finish the painting or $0$ otherwise.

Constraints and clarifications

• $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 \leq l \leq r \leq N$
• $1 \leq Q \leq 5$

Example

stdin

6
2 5 3
1 4
1 1
1 2
2 3 4
1 6
3
3 4
2 3
5 5

stdout

1
1
0

Explanation

Let we analyze the first initial painting. Optimal sequence of paintings is described in the following table.

Note that if we painted the cell with number $5$, at first, we would not have been able to successfully paint all cells.

Let we analyze the third initial painting.

Note that if we painted the cell with number $6$, at first, then the next paintings would have been the same and we would still fail. Therefore, the answer here is $0$.