There is a class of ~N~ students, numbered ~0~ through ~N-1~. Every day the teacher of the class has some projects for the students. Each project has to be completed by a team of students within the same day. The projects may have various difficulty. For each project, the teacher knows the exact size of a team that should work on it.
Different students may prefer different team sizes. More precisely, student ~i~ can only be assigned to a team of size between ~A[i]~ and ~B[i]~ inclusive. On each day, a student may be assigned to at most one team. Some students might not be assigned to any teams. Each team will work on a single project.
The teacher has already chosen the projects for each of the next ~Q~ days. For each of these days, determine whether it is possible to assign students to teams so that there is one team working on each project.
Suppose there are ~N=4~ students and ~Q=2~ days. The students' constraints on team sizes are given in the table below:
On the first day there are ~M=2~ projects. The required team sizes are ~\mathrm K=1~ and ~\mathrm K=3~. These two teams can be formed by assigning student 0 to a team of size 1 and the remaining three students to a team of size 3.
On the second day there are projects ~M=2~ again, but this time the required team sizes are ~\mathrm K=1~ and ~\mathrm K=1~. In this case it is not possible to form the teams, as there is only one student who can be in a team of size 1.
You are given the description of all students: ~N~, ~A~, and ~B~, as well as a sequence of ~Q~ queries — one about each day. Each question consists of the number ~M~ of projects on that day and a sequence ~K~ of length ~M~ containing the required team sizes. For each question, your program must return whether it is possible to form all the teams.
Line ~1~ of input will contain a single integer ~N~, representing the number of students.
Lines ~2, \ldots, N + 1~ will each contain a pair of space-separated integers ~\mathrm A[i]~ and ~\mathrm B[i]~, representing the length ~N~ arrays ~A~ and ~B~, where ~\mathrm A[i]~ is the minimum team size for student ~i~ and ~\mathrm B[i]~ is the maximum team size for student ~i~.
Line ~N + 2~ will contain a single integer ~Q~, representing the number of queries to follow.
Lines ~N + 3, \ldots, N + Q + 2~ will each consists of a query in the format ~M~, ~\mathrm K, \mathrm K, \ldots, \mathrm K[M - 1]~. ~M~ represents the number of projects for this day and ~K~ is an array of length ~M~ containing the required team size for each of these projects.
For each query, output a separate line containing either
1 if it is possible to form all the required teams, or
4 2 4 1 2 2 3 2 3 2 2 1 3 2 1 1
Let us denote by ~S~ the sum of values of ~M~.
|1||21||~1 \le N \le 100~||~1 \le Q \le 100~||none|
|2||13||~1 \le N \le 100\,000~||~Q = 1~||none|
|3||43||~1 \le N \le 100\,000~||~1 \le Q \le 100\,000~||~S \le 100\,000~|
|4||23||~1 \le N \le 500\,000~||~1 \le Q \le 200\,000~||~S \le 200\,000~|