C. Черепашки, но не ниндзя
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В Долине Медленных Шагов черепашки записывают на панцире длинные числа. Иногда некоторые цифры стираются, и на их месте появляется символ ?. Черепашки хотят восстановить число так, чтобы оно делилось на $$$3$$$.

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из цифр 0–9 и символов ?. Требуется заменить каждый символ ? на одну из цифр 0–9 так, чтобы получившееся число:

  • не имело ведущих нулей (то есть при $$$n \gt 1$$$ первая цифра не равна 0);
  • делилось на $$$3$$$.

Среди всех подходящих чисел нужно вывести минимальное по величине.

Если восстановить число невозможно, выведите -1.

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

В единственной строке дана непустая строка $$$s$$$, длиной не более $$$10^5$$$ символов, состоящая из символов 0–9 и ?.

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

Выведите минимальное число, кратное $$$3$$$, которое можно получить из $$$s$$$ заменой всех символов ? на цифры без ведущих нулей. Если такого числа не существует, выведите -1.

Примеры
Входные данные
1?3
Выходные данные
123
Входные данные
52
Выходные данные
-1
Входные данные
?2
Выходные данные
12
Входные данные
?8?
Выходные данные
180