Вася и множества
Вася и множества
Васе нравится всё формализировать. Вот например, у бабушки на огороде Вася видит множество овощей, у младшего брата - множество игрушек. А что же будет, если попытаться объединить или пересечь n множеств? Причём больших и разных: вплоть до миллиона элементов (включительно)!
Так как Вася мечтает стать математиком, то свои исследования он решил начать с исследования более простых множеств, а именно множеств целых чисел.
Входные данные
В первой строке задано количество разных множеств n (1 ≤ n ≤ 20). Далее задано n множеств в следующем формате:
В первой строке число t (1 ≤ t ≤
10^6
) - количество чисел в следующей строке.Во второй строке t чисел
x[i]
(1 ≤x[i]
≤10^6
), являющихся элементами множества.
Следующая строка содержит количество запросов m (1 ≤ m ≤ 100). Далее в m строках заданы запросы одного из двух типов:
INTERSECTION a b, где 1 ≤ a, b ≤ n
UNION a b, где 1 ≤ a, b ≤ n
Выходные данные
Для каждого запроса нужно вывести:
Для запроса первого типа количество элементов в пересечении a-го и b-го множеств.
Для запроса второго типа количество элементов в объединении a-го и b-го множества.
Пример
2 2 1 2 2 2 3 2 INTERSECTION 1 2 UNION 1 2
1 3