P7229 [COCI 2015/2016 #3] SLON

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$.

The first line contains the expression $A$. The second line contains two positive integers $P$ and $M$.

The first line contains one positive integer $x$.

#### 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](https://hsin.hr/coci/archive/2015_2016/contest3_tasks.pdf), full score 120. Translated by ChatGPT 5