Команды
В классе 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 иначе.