Операции над множествами
В этой задаче следует выполнить операции на множествах согласно заданным выражениям.
Рассмотрим выражение из трех множеств A, B и C и тремя операциями: объединение, пересечение и дополнение.
В нашей задаче множества будут состоять только из чисел {1, 2, ... , n} для некоторого фиксированного n. Объединением множеств X и Y является множество, которое содержит все числа, присутствующие хотя бы в одном из множеств X и Y. Пересечением множеств X и Y является множество, которое содержит элементы, присутствующие одновременно во множествах X и Y . Дополнением множества X является множество, содержащее все числа из {1, 2, ... , n} которых нет в X. например, при n = 5, X = {3, 4} и Y = {1, 3} объединением X и Y будет {1, 3, 4}, пересечением {3}, а дополнением X - множество {1; 2; 5}.
Выражение рекурсивно определяется следующим образом:
A, B и C - выражения, обозначающие соответственно множества A, B и C.
Если E выражение, то E и (E) также являются выражениями.
Если E и F выражения, то E | F и E F также являются выражениями.
Через X обозначается дополнение к множеству X, X | Y - объединение множеств X и Y, а X Y - пересечение множеств X и Y. Дополнение вычисляется перед пересечением, которое в свою очередь вычисляется перед объединением. Скобки выполняют обычную роль определения приоритета выполнения операций. Например, выражение A | B C вычисляется так же как и A | (( B) C).
Вам задано одно выражение и набор из трех множеств A, B и C. Вычислить значение выражения для каждой заданной тройки.
Входные данные
Первая строка содержит выражение длины от 1 до 300 000 символов. Гарантируется, что выражение соответствует приведенному выше рекурсивному определению. В первой строке отсутствуют пробелы.
Вторая строка содержит два числа n и t (1 ≤ n ≤ 20, 1 ≤ t ≤ 10 000) - количество элементов и троек множеств.
Каждая из следующих t строк задает тройку множеств A, B и C именно в таком порядке. Множество задается набором чисел в нем в строго возрастающем порядке, за которым следует ноль. Числа разделены одним или несколькими пробелами.
Выходные данные
Для каждой из t троек множеств вывести в отдельной строке одно множество: результат вычисления выражения для заданных A, B и C. Множество следует записать как набор принадлежащих ему чисел в строго возрастающем порядке, за которым следует ноль. Разделяйте числа одним пробелом.