ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Twofold Luck

Time limit: 1.0 second
Memory limit: 64 MB
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”.


293149 293150
Problem Author: Eugine Krokhalev
Problem Source: The 7th USU Open Personal Contest - February 25, 2006
To submit the solution for this problem go to the Problem set: 1432. Twofold Luck