32490번 - 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$.

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 aquarelle 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$.

입력

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.

출력

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

제한

• 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ドル \le Q \le 5$

서브태스크

힌트

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ドル$.}\\