### IOI '15 - Almaty, Kazakhstan

## 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 `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.

student | 0 | 1 | 2 | 3 |
---|---|---|---|---|

A | 1 | 2 | 2 | 2 |

B | 2 | 3 | 3 | 4 |

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). For each question, your program must return whether it is possible to form all the teams.

### Input Format

Line 1 of input will contain a single integer `N`, representing the number of students.

Lines 2, …, `N` + 1 will each contain a pair of space-separated integers `A`[`i`] and `B`[`i`], representing the length `N` arrays `A` and `B`, where `A`[`i`] is the minimum team size for student `i` and `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, …, `N` + `Q` + 2 will each consists of a query in the format `M`, `K`[0], `K`[1], …, `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 Format

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

subtask | points | N | Q | additional constraints |
---|---|---|---|---|

1 | 21% | 1 ≤ N ≤ 100 | 1 ≤ Q ≤ 100 | none |

2 | 13% | 1 ≤ N ≤ 100,000 | Q = 1 | none |

3 | 43% | 1 ≤ N ≤ 100,000 | 1 ≤ Q ≤ 100,000 | S ≤ 100,000 |

4 | 23% | 1 ≤ N ≤ 500,000 | 1 ≤ Q ≤ 200,000 | S ≤ 200,000 |

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 2048M

**Added:** Sep 05, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Cassian_gon Jul 15, 2016 - 10:16:42 am UTC What's SImaxBlueon Oct 14, 2016 - 9:23:38 pm UTC Re: What's S