Description

Little Q is very naughty at school.

He is always bored in class, and he always makes the classroom a mess. The teacher wants him to calm down, so the teacher gave him a very hard math problem.

The teacher gives Little Q an arithmetic expression $A$, and integers $P$ and $M$. Little Q needs to answer the following question:

Find the smallest non-negative integer $x$ such that the value of the expression $A$ (with $x$ substituted in) has remainder $P$ when divided by $M$.

Note that every operator connects two numbers or variables. Every multiplication sign is explicit, and it is not allowed to multiply two subexpressions that both contain $x$. All parentheses are valid, and there may be parentheses that contain only a single number or variable.

The problem guarantees that after simplification, the original expression can always be written as a linear expression in one variable of the form $kx+b$.

Input Format

The first line contains the expression $A$.

The second line contains two positive integers $P$ and $M$.

Output Format

The first line contains one positive integer $x$.

5+3+x
9 10

1

20+3+x
0 5

2

Hint

Constraints

For $100\%$ of the testdata:

• Let $|A|$ be the length of the string $A$. Then $1 \le |A| \le 10 ^ 5$.
• The expression $A$ contains only $\texttt{+}$, $\texttt{-}$, $\texttt{*}$, $\texttt{(}$, $\texttt{)}$, $\texttt{x}$, and $\texttt{0}$ $\sim$ $\texttt{9}$.
• $0 \le P \le M - 1$.
• $1 \le M \le 10 ^ 6$.

Notes

Translated from COCI 2015-2016 #3 D SLON, full score 120.

Translated by ChatGPT 5