Команди
У класі є n учнів, пронумерованих від 0 до n - 1. Щодня вчитель дає завдання, які учні повинні виконати в командах. Завдання можуть мати різну складність, і для кожного з них вчитель знає точну кількість учасників, які повинні бути в команді.
Кожен учень має свої уподобання щодо розміру команди. Учень з номером i може бути в команді, якщо її розмір від a[i] до b[i] включно. Щодня учень може бути в складі лише однієї команди або не бути в жодній. Кожна команда виконує одне завдання.
Вчитель вже обрав завдання на наступні q днів. Для кожного дня потрібно визначити, чи можливо розподілити учнів по командам так, щоб кожне завдання було виконане.
Розглянемо приклад: у класі 4 учні, і завдання розподіляються на два дні. Обмеження на розмір команди для учнів наведені в таблиці нижче.
У перший день є 2 завдання. Потрібні розміри команд — 1 і 3. Ці команди можна сформувати, включивши учня з номером 0 в команду з 1 особи, а решту трьох учнів — в команду з 3 осіб.
У другий день також є 2 завдання, але потрібні розміри команд — 1 і 1. У цьому випадку неможливо сформувати команди, оскільки лише один учень може бути в команді з 1 особи.
Вам надається опис усіх учнів: n, a і b, а також послідовність з q запитів, по одному для кожного дня. Кожен запит містить кількість завдань на цей день, позначену m, і послідовність k довжини m, де кожен елемент вказує на потрібний розмір команди. Для кожного запиту потрібно визначити, чи можливо сформувати всі команди.
Вхідні дані
Перша строка містить число n (1 ≤ n ≤ 500000) учнів. Кожен з наступних n рядків містить пару цілих чисел a[i] і b[i] (1 ≤ a[i], b[i] ≤ n), де a[i] - мінімальний розмір команди для i-го учня, а b[i] - максимальний розмір команди для i-го учня. Наступна строка містить кількість запитів q (1 ≤ q ≤ 200000). Кожен з наступних q рядків містить запит у форматі m, k[0], k[1], ..., k[m−1]. m (1 ≤ m ≤ n) вказує кількість завдань на сьогодні, K - масив довжини m, що містить розміри команд для кожного завдання. Відомо, що 1 ≤ k[i] ≤ n. Зазначимо, що сума всіх k[i] може перевищувати n.
Вихідні дані
Для кожного запиту виведіть в окремому рядку 1, якщо можна сформувати всі потрібні команди, або 0 інакше.