Secret Code

Time limit1sMemory limit512 MB

Summary

Given counts of digits 0 through 9, build the largest number whose every three consecutive digits form a multiple of 3, using a subset of the digits with no leading zeros.

Level: Medium7 of 10
Topics: Greedy, Math, Number theory, Implementation
Solved: No attempts yet

Problem

Bogdan is a fan of riddles and puzzles. He asked his friend Anton to come up with a secret code, and Bogdan would then decode it.

Anton decided to use a non-negative integer without extra leading zeroes as the secret code. The code must satisfy the following condition. If you take any three consecutive digits of it as a three-digit integer, that integer is divisible by three.

Anton told Bogdan all digits of his secret code, and possibly some other digits as well. He claims that the largest number satisfying the above condition that can be built from these digits is the secret code.

Help Bogdan find out what the secret code is.

Input

The input contains 10 integers: $c\_0, \ldots, c\_9$ , where $c\_i$ is the number of digits $i$ that Anton gave to Bogdan ( $0 \le c\_i \le 100\,000$ ). The sum of the $c\_i$ is strictly positive and does not exceed $100\,000$ .

Output

Output the largest integer that can be built from these digits. It must satisfy the condition that the integer formed by any three consecutive digits is divisible by three. It is not required to use all of the given digits. A one-digit or two-digit number automatically satisfies the condition, because it has no three consecutive digits. The answer must not contain extra leading zeroes: the first digit can be $0$ only if the number is zero, in which case it must be the only digit.

Examples2

Example 1
Input
```
1 2 3 0 0 0 0 0 0 0
```
Expected output
```
21021
```
Example 2
Input
```
1 1 1 1 1 1 1 1 1 1
```
Expected output
```
9876543210
```