Teams#7768

Teams

2 seconds

128 megabytes

Hard

There is a class of $n$ students, numbered $0$ through $n - 1$ 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}$ a_i and $b_{i}$ 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$ n = 4 students and $q = 2$ q = 2 days. The students' constraints on team sizes aregiven in the table below.

On the first day there are $m = 2$ m = 2 projects. The required team sizes are $k_{0} = 1$ k_0 = 1 and $k_{1} = 3$ 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$ m = 2 projects again, but this time the required team sizes are $k_{0} = 1$ k_0 = 1 and $k_{1} = 1$ 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$ .

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. The sum of $m$ across all queries will be equal to $s$ (not given in the input, $s \leq 200000$ s \leq 200000). For each question, your program must return whether it is possible to form all the teams.

Input

First line contains the number $n$ ( $1 \leq n \leq 500000$ 1 \leq n \leq 500000) of students. Each of the next $n$ lines contains a pair of space-separated integers $a_{i}$ a_i and $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \leq a_i, b_i \leq n), where $a_{i}$ a_i is the minimum team size for student $i$ and $b_{i}$ b_i is the maximum team size for student $i$ . Next line contains the number of queries $q$ ( $1 \leq q \leq 200000$ 1 \leq q \leq 200000) to follow. Each of the next $q$ lines consists of a query in the format $m$ , $k_{0}$ k_0, $k_{1}$ k_1, ..., $k_{m - 1}$ k_{m-1}. $m$ ( $1 \leq m \leq n$ 1 \leq m \leq 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 \leq k_{i} \leq n$ 1 \leq k_i \leq n. Note that the sum of all $k_{i}$ k_i may exceed $n$ .

Output

For each query output a separate line containing either $1$ if it is possible to form all the required teams, or $0$ otherwise.

Examples

Example 1