J. Maximal Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"I think Christopher Robin is a pretty cool guy," said Pooh carelessly, "eh sums integers without carrying and doesnt afraid of anything."

"Oh, Pooh! Do you mean that Christopher Robin writes something like $$$5+5=0$$$, $$$19+3=12$$$ and $$$75+25=90$$$?" asked Piglet anxiously.

"Yes," said Bear, "And he calls that digitwise sum. He just sums pairs of corresponding digits modulo 10. But what maximal sum can Christopher Robin make if I ask him to use numbers from my very own list only? Do you wonder, Piglet?"

Input

On the first line Winnie-the-Pooh wrote a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$). After a little break he wrote $$$n$$$ more lines: on line number $$$i + 1$$$ he wrote an integer $$$x_i$$$ ($$$0 \lt x_i \lt 10^6$$$). When Winnie-the-Pooh had finished his writings, he brought them right to Christopher Robin.

Output

On the first line output a single integer $$$a$$$ — maximal digitwise sum Christopher Robin can make. On the second line output integer number $$$m$$$ — how many numbers Christopher Robin have used to make sum $$$a$$$. But $$$0 \leq m \leq 108$$$ because Winnie-the-Pooh is a Bear of Very Little Brain and he won't check the answer if $$$m$$$ is greater than one hundred eight. On the third line output $$$m$$$ numbers used to make sum $$$a$$$ separated by spaces. Remember that each number in the third line should be one of $$$x_i$$$ numbers from the Pooh's list.

If there is no answer Winnie-The-Pooh can check, output just $$$a$$$ on the first line and $$$-1$$$ on the second line instead.

Examples
Input
1
1
Output
9
9
1 1 1 1 1 1 1 1 1
Input
2
12
13
Output
99
9
12 12 12 12 12 12 12 12 13
Input
2
15
5
Output
95
9
15 15 15 15 15 15 15 15 15