Description

After entering middle school, Mingming learned algebraic expressions. One day, he encountered a troublesome multiple-choice question. The stem first gives an algebraic expression, then lists several options, each of which is also an algebraic expression. The task is to determine which options are equivalent to the expression in the stem.

This is tedious to do by hand. Since Mingming is interested in computer programming, he wonders if a computer can solve it. Suppose you are Mingming. Can you complete this task?

Every expression in this multiple-choice problem satisfies the following properties:

1. The expression may contain only one variable, $\tt a$.
2. All numbers that appear in the expression are positive integers less than $10000$.
3. The expression may include four operations: + (addition), - (subtraction), * (multiplication), ^ (exponentiation), and parentheses (). Parentheses have the highest precedence, followed by ^, then *, and finally + and -. + and - have the same precedence. Operations of the same precedence (including ^) are evaluated from left to right.
4. Exponents can only be positive integers from $1$ to $10$ inclusive.
5. There may be extra spaces within the expression, at the beginning, or at the end.

If an option contains an invalid expression (e.g., unmatched parentheses), ignore that option.

Here are some valid examples: ((a^1) ^ 2)^3, a*a+a-a, ((a+a)), 9999+(a-a)*a, 1 + (a -1)^3, 1^10^9.

Input Format

The first line contains the expression in the stem.

The second line contains an integer $n$, the number of options. The next $n$ lines each contain the expression of one option. These $n$ options are labeled $A, B, C, D, \cdots$.

Each expression in the input has length at most $50$ characters. It is guaranteed that at least one option is equivalent to the expression in the stem.

Output Format

Output one line containing the labels of all options that are equivalent to the expression in the stem. The labels must be in alphabetical order with no spaces.

( a + 1) ^2
3
(a-1)^2+4*a
a + 1+ a
a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a

AC

Hint

• For $30\%$ of the testdata, only the two operators + and - may appear.
• For the other testdata, all four operators +-*^ may appear in expressions.
• For $100\%$ of the testdata, parentheses () may appear, and $2 \le n \le 26$.

Problem Source

NOIP 2005 Senior Problem 4.

Translated by ChatGPT 5