Teams
Teams
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 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 aregiven in the table below.
On the first day there are m = 2 projects. The required team sizes are k[0]
= 1 and k[1]
= 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 m = 2 projects again, but this time the required team sizes are k[0]
= 1 and k[1]
= 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.
Your 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. The sum of m across all queries will be equal to s (not given in the input, s ≤ 200000). For each question, your program must return whether it is possible to form all the teams.
Input data
First line contains the number n (1 ≤ n ≤ 500000) of students. Each of the next n lines contains a pair of space-separated integers a[i]
and b[i]
(1 ≤ a[i]
, b[i]
≤ n), where a[i]
is the minimum team size for student i and b[i]
is the maximum team size for student i. Next line contains the number of queries q (1 ≤ q ≤ 200000) to follow. Each of the next q lines consists of a query in the format m, k[0]
, k[1]
, ..., k[m−1]
. m (1 ≤ m ≤ n) 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. It is known that 1 ≤ k[i]
≤ n. Note that the sum of all k[i]
may exceed n.
Output data
For each query output a separate line containing either 1 if it is possible to form all the required teams, or 0 otherwise.
Examples
4 2 4 1 2 2 3 2 3 2 2 1 3 2 1 1
1 0