A. Forgetful Shustrik and the Remote Control
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The hamster Shustrik received an unusual calculator as a gift from the hedgehog Shurshik. Initially, the number $$$A$$$ is displayed on the calculator screen.

The instructions for the calculator specify a fixed number $$$M$$$. All arithmetic operations are performed with this number. Additionally, Shurshik has thought of numbers $$$N$$$ and $$$B$$$ and informed Shustrik about them.

The calculator can perform only four operations, and in one step, one of the following operations can be applied:

  • Operation "+": replace the current value $$$A$$$ with $$$A + M$$$.
  • Operation "-": replace the current value $$$A$$$ with $$$A - M$$$.
  • Operation "*": replace the current value $$$A$$$ with $$$A \cdot M$$$.
  • Operation "%": replace the current value $$$A$$$ with the remainder of the division $$$A$$$ by $$$M$$$. After this operation, the condition $$$0 \le A \lt M$$$ holds.

After performing some (possibly empty) sequence of operations, the number $$$A'$$$ will be obtained.

The hedgehog Shurshik became curious whether Shustrik can obtain such a number $$$A'$$$ that

$$$$$$ A' \equiv B \pmod N. $$$$$$

In other words, the numbers $$$A'$$$ and $$$B$$$ must have the same remainders when divided by $$$N$$$.

Your task is to help the hamster find any sequence of operations of the smallest length, after which the specified condition will be satisfied, or determine that it is impossible to obtain such a number.

Input

In a single line, four integers are given separated by spaces: $$$A$$$, $$$M$$$, $$$B$$$, and $$$N$$$ ($$$|A| \leq 10^9$$$, $$$1 \leq M \leq 10^9$$$, $$$0 \leq B \lt N \leq 2 \cdot 10^6$$$).

Output

If the desired sequence of operations does not exist, output "-1" in a single line.

Otherwise, in the first line, output the length $$$x$$$ of the minimal suitable sequence. In the second line, output a string of length $$$x$$$ consisting of the characters "+", "-", "*", and "%" — the sequence of operations that transforms the initial $$$A$$$ into such $$$A'$$$ that $$$A' \equiv B \pmod N$$$.

If there are multiple such sequences, output any of them.

It can be proven that the length of the answer does not exceed $$$N$$$.

Scoring

Points for each subtask are awarded only if all tests for that subtask and necessary subtasks are successfully passed.

GroupPointsAdditional constraints Required groups
17$$$|A|, M, N \le 8$$$–
26$$$M = 1$$$–
38$$$M = N$$$–
412$$$M \equiv 0 \pmod N$$$3
515$$$N \equiv 0 \pmod M$$$2–3
616$$$N \cdot M \le 2 \cdot 10^{6}$$$1–2
718$$$A = 0$$$–
818–1–7
Examples
Input
1 3 2 5
Output
2
+*
Input
6 7 2 4
Output
0
Input
-1 3 2 4
Output
1
+
Input
5 6 1 6
Output
-1
Input
0 6 3 7
Output
3
---
Input
5 9 1 8
Output
3
*%+
Note

Consider the answer to the first example of the input data:

  • Initially, $$$A = 1$$$.
  • Operation "+": replace $$$A$$$ with $$$A + 3 = 1 + 3 = 4$$$.
  • Operation "*": replace $$$A$$$ with $$$A \cdot 3 = 4 \cdot 3 = 12$$$.
  • We get $$$A' = 12$$$. At the same time, $$$A' \equiv B \pmod N$$$ holds true, since $$$12 \equiv 2 \pmod 5$$$.
It can be proven that in this example there is no sequence of zero or one operation that results in a suitable $$$A'$$$. A sequence of two operations "++" is also suitable: $$$1+3+3 = 7 \equiv 2 \pmod 5$$$.