바이오마커

Villedor 주민은 모두 바이오마커라는 특수 장치를 지니고 있다. 바이오마커 값은 좀비 바이러스 감염 수준을 나타낸다. 이 값이 클수록 사람들은 좀비화 발작을 걱정해서 당신과 교류하려 하지 않는다.

좀비에게 물린 사람은 바이오마커 값이 $3$으로 나누어떨어질 때, 그리고 그때에만 좀비화 발작이 일어난다는 것이 알려져 있다.

Eiden은 Bazaar에서 충돌이 일어난 뒤 병원에서 자신의 바이오마커를 찾았는데, 안타깝게도 이 장치는 조금 고장 나 있다. 고장 난 바이오마커는 실제 감염 수준 외에 불필요한 숫자를 추가로 표시할 수 있다. 예를 들어 실제 감염 수준이 $123$이면 바이오마커는 $1234$나 $19203$을 표시할 수 있지만, $123$에 불필요한 숫자를 덧붙여서 만들 수 없는 $1453$은 표시할 수 없다.

발작 중에 Eiden은 실제 감염 수준이 $3$으로 나누어떨어진다는 것을 정확히 안다. 이제 그의 바이오마커가 숫자 $n$을 표시하고 있을 때, 실제 감염 수준으로 가능한 최댓값이 얼마인지 알고 싶어 한다.

첫 줄에는 정수 $k$ ($1 \leqslant k \leqslant 5 \cdot 10^5$)가 주어진다. 이는 바이오마커에 표시된 수 $n$의 십진수 표기에 있는 자릿수 개수이다.

둘째 줄에는 $n$의 십진수 표기를 이루는 $k$개의 숫자가 $0$부터 $9$까지 주어진다. $n$의 표기에는 선행 0이 없다고 보장된다.

$n$에서 일부 숫자를 지워서 얻을 수 있는 감염 수준의 최댓값을 한 줄에 출력한다. 답은 선행 0 없이 출력한다.

$n$의 모든 숫자가 불필요해서, $n$을 어떤 $3$의 배수에 숫자를 덧붙여 만들 수 없다면 $0$을 출력한다.

첫 번째 예제에서 가능한 감염 수준 값은 $0$(모든 숫자가 불필요한 경우), $3$, $12$, $24$, $123$, $234$이다. 이 중 최댓값은 $234$이며, 이것이 답이다.