У каждого жителя Вилледора есть специальные устройства — биомаркеры. Значение биомаркера отражает уровень зараженности зомби-вирусом. Чем больше этот показатель, тем с меньшей охотой люди будут с тобой взаимодействовать, опасаясь приступа зомбификации.
Известно, что с людьми, которых кусали зомби, случается приступ превращения в зомби, тогда и только тогда, когда значение их биомаркера делится на три.
Свой биомаркер Эйден нашел в больнице после стычки на Базаре, и, к сожалению, он немного неисправен. Его неисправность выражается в том, что помимо настоящего уровня зараженности он может выводить лишние цифры. Например, если настоящий уровнь зараженности равен $$$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$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 8 | $$$k \leqslant 3$$$ | полная | |
2 | 13 | $$$k \leqslant 6$$$ | 1 | полная |
3 | 15 | $$$k \leqslant 18$$$ | 2 | полная |
4 | 18 | $$$k \leqslant 350$$$, $$$n$$$ не содержит нулей | 3 | полная |
5 | 12 | цифры в числе $$$n$$$ идут в порядке неубывания | полная | |
6 | 15 | $$$n$$$ не содержит нулей | 1 – 5 | первая ошибка |
7 | 19 | нет | 6 | первая ошибка |
4 1234
234
5 54784
5784
2 80
0
Значения зараженности, которые могут возможны в первом примере: $$$0$$$ (все цифры лишние), $$$3$$$, $$$12$$$, $$$24$$$, $$$123$$$ и $$$234$$$. Максимальное из них — $$$234$$$, что и является ответом.