28616번 - Биомаркеры 스페셜 저지다국어

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

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

Свой биомаркер Эйден нашел в больнице после стычки на Базаре, и, к сожалению, он немного неисправен. Его неисправность выражается в том, что помимо настоящего уровня зараженности он может выводить лишние цифры. Например, если настоящий уровнь зараженности равен $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$.

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