Petya and Vasya want to take part in an ACM contest
but couldn't find the third player. But they decided to
participate anyway. However, in the absence of the third
team member, they are very anxious about their winning
chances and use all means to increase them. Accordingly,
they both want to have lucky tickets when they ride a
bus to the contest. Of course, they need to sit together
in the bus to be able to discuss the tactics of their
actions during the contest.
When Petya and Vasya approached the ticket window, they
decided to wait and let other people buy tickets until
the next two tickets to be sold were lucky. For how long
will they have to wait in this situation? Write a program
that finds the nearest pair of adjacent lucky tickets.
P.S. Recall that there are two different approaches to determination if a ticket is lucky. In the first approach, one calculates and
compares the sums of digits in the left and the right halves of
the number. In the second approach, the sums of digits in even
and uneven positions are calculated. In both cases, a ticket is
considered lucky if the sums are equal.
P.P.S. Petya and Vasya do not follow a specific approach. Each of them will be satisfied if his ticket is lucky with respect to any of the described approaches.
The first input line contains a single number
containing 2N digits (4 ≤ 2N ≤ 1500),
which is the number of the current ticket at the ticket
window (there may be leading zeros).
Output one line with two successive numbers of the nearest pair of lucky tickets
separated with a space. If the current ticket in the ticket
window is lucky and successive one is lucky too Petya and
Vasya would buy this pair of tickets. The last ticket in
the ticket window consists of all nines. If Petya and Vasya
would never get the pair of lucky tickets print “No solution”.
Problem Author: Eugine Krokhalev
Problem Source: The 7th USU Open Personal Contest - February 25, 2006