A. Забывчивый Шустрик и пульт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хомяк Шустрик получил в подарок от ёжика Шуршика необычный калькулятор. Изначально на экране калькулятора отображается число $$$A$$$.

В инструкции к калькулятору указано фиксированное число $$$M$$$. Все арифметические операции выполняются именно с этим числом. Кроме того, Шуршик загадал числа $$$N$$$ и $$$B$$$ и сообщил их Шустрику.

Калькулятор умеет выполнять только четыре операции, за один шаг можно применить одну из следующих операций:

  • Операция «+»: заменить текущее значение $$$A$$$ на $$$A + M$$$.
  • Операция «-»: заменить текущее значение $$$A$$$ на $$$A - M$$$.
  • Операция «*»: заменить текущее значение $$$A$$$ на $$$A \cdot M$$$.
  • Операция «%»: заменить текущее значение $$$A$$$ на остаток от деления $$$A$$$ на $$$M$$$. После этой операции выполняется условие $$$0 \le A \lt M$$$.

После выполнения некоторой (возможно, нулевой) последовательности операций получится число $$$A'$$$.

Ёжику Шуршику стало интересно, сможет ли Шустрик получить такое число $$$A'$$$, что

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

Иначе говоря, числа $$$A'$$$ и $$$B$$$ должны иметь одинаковые остатки при делении на $$$N$$$.

Ваша задача — помочь хомяку найти любую последовательность операций наименьшей длины, после применения которой выполнится указанное условие, либо определить, что получить такое число невозможно.

Входные данные

В единственной строке входных данных дано четыре целых числа через пробел: $$$A$$$, $$$M$$$, $$$B$$$ и $$$N$$$ ($$$|A| \leq 10^9$$$, $$$1 \leq M \leq 10^9$$$, $$$0 \leq B \lt N \leq 2 \cdot 10^6$$$).

Выходные данные

Если искомой последовательности операций не существует, в единственной строке выведите «-1».

Иначе, в первой строке выведите длину $$$x$$$ минимальной подходящей последовательности. Во второй строке выведите строку длины $$$x$$$ из символов «+», «-», «*» и «%» — последовательность операций, приводящий изначальное $$$A$$$ в такое $$$A'$$$, что $$$A' \equiv B \pmod N$$$.

Если таких последовательностей несколько, выведите любую из них.

Можно доказать, что длина ответа не превышает $$$N$$$.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ГруппаБаллыДоп. ограничения Необходимые группы
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
Примеры
Входные данные
1 3 2 5
Выходные данные
2
+*
Входные данные
6 7 2 4
Выходные данные
0
Входные данные
-1 3 2 4
Выходные данные
1
+
Входные данные
5 6 1 6
Выходные данные
-1
Входные данные
0 6 3 7
Выходные данные
3
---
Входные данные
5 9 1 8
Выходные данные
3
*%+
Примечание

Рассмотрим ответ на первый пример входных данных:

  • Изначально $$$A = 1$$$.
  • Операция «+»: заменить $$$A$$$ на $$$A + 3 = 1 + 3 = 4$$$.
  • Операция «*»: заменить $$$A$$$ на $$$A \cdot 3 = 4 \cdot 3 = 12$$$.
  • Получилось $$$A' = 12$$$. При этом $$$A' \equiv B \pmod N$$$ верно, так как $$$12 \equiv 2 \pmod 5$$$.
Можно доказать, что в данном примере не существует последовательности из нуля или одной операции, получающей подходящее $$$A'$$$. Последовательность из двух операций «++» тоже является подходящей: $$$1+3+3 = 7 \equiv 2 \pmod 5$$$.