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.

Example

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[0]=1~ and ~\mathrm 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 projects ~M=2~ again, but this time the required team sizes are ~\mathrm K[0]=1~ and ~\mathrm 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. For each question, your program must return whether it is possible to form all the teams.

Input Specification

Line ~1~ of input will contain a single integer ~N~, representing the number of students.
Lines ~2, \dots, 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, \dots, N+Q+2~ will each consists of a query in the format ~M~, ~\mathrm K[0], \mathrm K[1], \dots, \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.

Output Specification

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

Sample Input

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

Sample Output

1
0

Subtasks

Let us denote by ~S~ the sum of values of ~M~.

subtask	points	~N~	~Q~	Additional Constraints
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~