Биомаркеры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Известно, что с людьми, которых кусали зомби, случается приступ превращения в зомби, тогда и только тогда, когда значение их биомаркера делится на три.

Свой биомаркер Эйден нашел в больнице после стычки на Базаре, и, к сожалению, он немного неисправен. Его неисправность выражается в том, что помимо настоящего уровня зараженности он может выводить лишние цифры. Например, если настоящий уровнь зараженности равен $$$123$$$, биомаркер может отображать числа $$$1234$$$ и $$$19203$$$, но не может отображать число $$$1453$$$, так как его нельзя получить из $$$123$$$ дописыванием лишних цифр.

Во время очередного приступа Эйден точно знает, что его настоящий уровень зараженности делится на три. И теперь его интересует, какое максимальное значение зараженности может быть у него на самом деле, если сейчас его биомаркер отображает число $$$n$$$?

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

В первой строке ввода дано единственное целое число $$$k$$$ ($$$1 \leqslant k \leqslant 5 \cdot 10^5$$$) — количество цифр в десятичной записи отображаемого на биомаркере числа $$$n$$$.

Во второй строке ввода даны $$$k$$$ цифр от $$$0$$$ до $$$9$$$ — десятичная запись числа $$$n$$$, текущего отображаемого на биомаркере уровня зараженности. Гарантируется, что в записи $$$n$$$ нет ведущих нулей.

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

В единственной строке выходных данных выведите максимальное возможное значение уровня зараженности Эйдена зомби-вирусом, которое может быть получено удалением некоторых цифр числа $$$n$$$.

Ответ следует выводить без ведущих нулей.

Если все цифры числа $$$n$$$ лишние, то есть не существует числа, кратного трем, из которого можно получить число $$$n$$$ добавлением каких-то цифр, выведите $$$0$$$.

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

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
18$$$k \leqslant 3$$$полная
213$$$k \leqslant 6$$$1полная
315$$$k \leqslant 18$$$2полная
418$$$k \leqslant 350$$$, $$$n$$$ не содержит нулей3полная
512 цифры в числе $$$n$$$ идут в порядке неубывания полная
615$$$n$$$ не содержит нулей1 – 5первая ошибка
719нет6первая ошибка

Примеры

Входные данные
4
1234
Выходные данные
234
Входные данные
5
54784
Выходные данные
5784
Входные данные
2
80
Выходные данные
0

Примечание

Значения зараженности, которые могут возможны в первом примере: $$$0$$$ (все цифры лишние), $$$3$$$, $$$12$$$, $$$24$$$, $$$123$$$ и $$$234$$$. Максимальное из них — $$$234$$$, что и является ответом.