Məsələlər
Операции над множествами
Операции над множествами
В этой задаче следует выполнить операции на множествах согласно заданным выражениям.
Рассмотрим выражение из трех множеств \textbf{A}, \textbf{B} и \textbf{C} и тремя операциями: объединение, пересечение и дополнение.
В нашей задаче множества будут состоять только из чисел \{\textbf{1}, \textbf{2}, ... , \textbf{n}\} для некоторого фиксированного \textbf{n}. Объединением множеств \textbf{X} и \textbf{Y} является множество, которое содержит все числа, присутствующие хотя бы в одном из множеств \textbf{X} и \textbf{Y}. Пересечением множеств \textbf{X} и \textbf{Y} является множество, которое содержит элементы, присутствующие одновременно во множествах \textbf{X} и \textbf{Y} . Дополнением множества \textbf{X} является множество, содержащее все числа из \{\textbf{1}, \textbf{2}, ... , \textbf{n}\} которых нет в\textbf{ X}. например, при \textbf{n} = \textbf{5}, \textbf{X} = \{\textbf{3}, \textbf{4}\} и \textbf{Y} = \{\textbf{1}, \textbf{3}\} объединением \textbf{X} и \textbf{Y} будет \{\textbf{1}, \textbf{3}, \textbf{4}\}, пересечением \{\textbf{3}\}, а дополнением \textbf{X} - множество \{\textbf{1}; \textbf{2}; \textbf{5}\}.
Выражение рекурсивно определяется следующим образом:
\begin{itemize}
\item \textbf{A}, \textbf{B} и \textbf{C} - выражения, обозначающие соответственно множества\textbf{ A}, \textbf{B} и \textbf{C}.
\item Если \textbf{E} выражение, то ~\textbf{E} и (\textbf{E}) также являются выражениями.
\item Если \textbf{E} и \textbf{F} выражения, то \textbf{E }| \textbf{F} и \textbf{E} & \textbf{F} также являются выражениями.
\end{itemize}
Через ~\textbf{X} обозначается дополнение к множеству \textbf{X}, \textbf{X} | \textbf{Y} - объединение множеств \textbf{X} и \textbf{Y}, а \textbf{X} & \textbf{Y} - пересечение множеств \textbf{X} и \textbf{Y}. Дополнение вычисляется перед пересечением, которое в свою очередь вычисляется перед объединением. Скобки выполняют обычную роль определения приоритета выполнения операций. Например, выражение \textbf{A} | ~\textbf{B} & \textbf{C} вычисляется так же как и \textbf{A} | ((~\textbf{B}) & \textbf{C}).
Вам задано одно выражение и набор из трех множеств \textbf{A}, \textbf{B} и \textbf{C}. Вычислить значение выражения для каждой заданной тройки.
\InputFile
Первая строка содержит выражение длины от \textbf{1} до \textbf{300 000} символов. Гарантируется, что выражение соответствует приведенному выше рекурсивному определению. В первой строке отсутствуют пробелы.
Вторая строка содержит два числа \textbf{n} и \textbf{t} (\textbf{1} ≤ \textbf{n} ≤ \textbf{20}, \textbf{1} ≤ \textbf{t} ≤ \textbf{10 000}) - количество элементов и троек множеств.
Каждая из следующих \textbf{t} строк задает тройку множеств \textbf{A}, \textbf{B} и \textbf{C} именно в таком порядке. Множество задается набором чисел в нем в строго возрастающем порядке, за которым следует ноль. Числа разделены одним или несколькими пробелами.
\OutputFile
Для каждой из \textbf{t} троек множеств вывести в отдельной строке одно множество: результат вычисления выражения для заданных \textbf{A}, \textbf{B} и \textbf{C}. Множество следует записать как набор принадлежащих ему чисел в строго возрастающем порядке, за которым следует ноль. Разделяйте числа одним пробелом.
Giriş verilənləri #1
A|~B&C 5 2 1 3 0 3 4 0 2 3 5 0 0 1 3 5 0 0
Çıxış verilənləri #1
1 2 3 5 0 0
Şərh: Выражение вычисляется как A | ((~B) & C). Для первой тройки ~B = {1, 2, 5}, ~B & C = {2, 5}, а все выражение равно множеству {1, 2, 3, 5}. Для второй тройки ~B = {2, 4}, ~B & C пусто, ответ является пустым множеством.