eolymp
Задачи

Кратное трём

Кратное трём

Дано число. Степан хочет заменить в нем одну цифру таким образом, чтобы новое число делилось на 3 и было максимально возможным. В заданном числе нужно обязательно заменить одну цифру, даже если оно уже делится на 3. Поскольку Степан только начал посещать факультатив по программированию, то он просит помощи у Вас.

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

Дано одно натуральное число. Длина числа может достигать 100 цифр.

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

Выведите натуральное число, удовлетворяющее следующим условиям:

  • Новое число должно отличаться от заданного ровно одной цифрой.
  • Новое число должно делиться на 3.
  • Новое число должно быть максимально возможным среди всех таких чисел.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
123
Выходные данные #1
723
Входные данные #2
8
Выходные данные #2
9
Источник 2016 ACM Ukraine, Первый этап Украина, 16 апреля