Background

$\text{bh1234666}$ is learning multiplication.

Problem Description

$\text{bh1234666}$ has a certain number of digits $0 \sim 9$. Now he wants you to find an allocation scheme that splits them into two integers so that their product $p$ is maximized.

Since $\text{bh1234666}$ does not like numbers that are too large, you only need to output two non-negative integers such that their product is equal to the maximum product $p$, but the counts of digits $0 \sim 9$ used in these two integers must not be equal to the given counts (it is enough that the count of any one digit is different; leading zeros are not considered).

$\text{bh1234666}$ is very kind: if the counts of $0 \sim 9$ are exactly the same as the given counts, you can still get half of the points.

Input Format

The first line contains ten integers $c_0,c_1,\cdots c_9$, representing the counts of digits $0 \sim 9$, respectively.

Output Format

Two lines, each containing a non-negative integer, representing the two non-negative integers you provide.

1 2 3 2 1 1 2 1 2 1

13949030
620572547

Hint

Sample Explanation

The maximum possible product is $97643210 \times 88653221=13949030 \times 620572547=8656385075279410$.

If you output $97643210 \times 88653221$, you can only get half of the points, because the number of occurrences of $0\sim 9$ is the same as the given one.

Constraints and Notes

This problem uses bundled tests. There are $5$ $\text{subtask}$ in total, and the final score is the sum of the scores of all $\text{subtask}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \sum c_i\le \cr\hline 1 & 10 & 20 \cr\hline 2 & 20 & 100 \cr\hline 3 & 20 & 5000 \cr\hline 4 & 20 & 10^6 \cr\hline 5 & 30 & 10^7 \cr\hline \end{array}$$

For $100\%$ of the testdata, it is guaranteed that $1 \le c_i$ and $\sum c_i \le 10^7$.

Notes

This problem has an $\text{spj}$. If the product of the two numbers is correct, you get half of the points; if the digit counts are different from the given ones and the product is correct, you get full points. Therefore, for each $\text{subtask}$, the score is the minimum value among the scores of all test points in it.

Input Format

The first line contains ten integers $c_0,c_1,\cdots c_9$, representing the counts of digits $0 \sim 9$, respectively.

Output Format

Two lines, each containing a non-negative integer, representing the two non-negative integers you provide.

Translated by ChatGPT 5