Description

There are $N$ students in the class, numbered from $0$ to $N-1$. Every day, the teacher has some projects that need to be completed by students. Each project must be completed within one day by a team of students. The projects may have different difficulty levels. For each project, the teacher knows how many students should be chosen to form a team to complete it.

Different students have different preferences for team size. More precisely, for student $i$, they are only willing to work in a team whose size is between $A[i]$ and $B[i]$ (including $A[i]$ and $B[i]$). Each day, a student can be assigned to at most one team. Some students may not be assigned to any team. Each team is responsible for exactly one project.

The teacher has already selected the projects for each of the next $Q$ days. For each day, you need to determine whether there exists an assignment of students such that every project has a team responsible for it.

Input Format

• Line $1$ contains a positive integer $N$, the number of students in the class.
• Lines $2$ to $N+1$ each contain two integers $A[i]$, $B[i]$.
• Line $N+2$ contains a positive integer $Q$.
• Lines $N+3$ to $N+Q+2$ each contain a positive integer $M$, the number of projects to be completed that day, followed by a sequence $K$ of length $M$. $K[i]$ ($1 \le i \le M$) denotes the required team size for project $i$.

Output Format

Output $Q$ lines. For each query, your program must output whether there exists a team assignment plan that can complete all projects of that day. If it is possible to form teams to complete all projects for that day, output 1; otherwise, output 0.

4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

1
0

Hint

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^5$, $1 \le Q \le 2 \times 10^5$, $\sum M \leq 2 \times 10^5$.

Translated by ChatGPT 5