Pentru un număr dat cu k cifre $c_1c_2…c_k$, se numeşte algoritm de deplasare circulară spre dreapta de la o cifră iniţială $c_i$, la o cifră finală $c_j$, deplasarea din cifră în cifră spre dreapta de $c_i$ ori (1≤i,j≤k). Dacă pe parcursul deplasării s-a ajuns la cifra $c_k$, se continuă deplasarea circulară spre dreapta cu cifra $c_1$.
Un număr cu k cifre se numeşte număr „circular” dacă îndeplineşte următoarele două cerinţe:

• toate cifrele sunt nenule;
• pornind de la cifra $c_1$, aplicând algoritmul de deplasare circulară spre dreapta de exact k ori, se ajunge din nou la $c_1$, fiecare dintre cifrele numărului fiind exact o singură dată cifră iniţială.
  De exemplu, numărul 2396 este un număr “circular”, pentru că are doar cifre nenule şi algoritmul de deplasare circulară spre dreapta se aplică astfel:
  1. Se porneşte de la cifra iniţială 2 (2 3 9 6) şi se numără două cifre spre dreapta, ajungând la cifra finală 9: 2 3 9 6.
  2. Se porneşte de la cifra iniţială 9 şi se numără nouă cifre spre dreapta, ajungând la cifra finală 6: 2 3 9 6.
  3. Se porneşte de la cifra iniţială 6 şi se numără şase cifre spre dreapta, ajungând la cifra finală 3: 2 3 9 6.
  4. Se porneşte de la cifra iniţială 3 şi se numără trei cifre spre dreapta, ajungând la cifra finală 2: 2 3 9 6.
  Astfel, se ajunge la prima cifră din număr, adică la cifra 2, după exact 4 aplicări ale algoritmului, iar fiecare dintre cifrele numărului este exact o dată cifră iniţială.

Cerința

Scrieţi un program care citeşte numărul natural nenul n, apoi numerele naturale $x_1, x_2, …, x_n$, şi determină:
a) cel mai mare număr din şir în care există cel puţin o cifră care apare de minimum două ori, iar în cazul în care în şir nu există un astfel de număr, se va afişa cel mai mare număr din şir;
b) un şir $a_1, a_2, …, a_n$ de n numere naturale pentru care un element $a_i$(1≤i≤n)se calculează astfel:

• este egal cu $x_i$ , dacă $x_i$ este număr circular;
• este numărul cel mai apropiat de $x_i$ (număr mai mare sau mai mic decât $x_i$), cu proprietatea că este număr circular; dacă pentru un număr din şir se identifică un număr circular y, $y > x_i$ şi un număr circular z, z<$x_i$, pentru care $y – x_i$ = $x_i – z$, atunci se va alege numărul y.

Date de intrare

Fişierul numar.in conţine pe prima linie numărul n, iar pe următoarele n linii numerele naturale $x_1, x_2, …, x_n$.

Date de ieșire

Fişierul numar.out va conţine pe prima linie un număr natural determinat conform cerinţei a), iar pe următoarele n linii şirul de numere determinat conform cerinţei de la punctul b), fiecare număr pe câte un rând.

Restricții și precizări

• 0 < n < 100
• 9 < $x_i$ < 999589, 1 ≤ i ≤ n

Exemplu:

numar.in

5
15
123
1972
222
515

numar.out

515
15 
117
1959
222
522

Explicație

a) 515 este cel mai mare număr dintre cele cinci numere citite, număr ce conţine o cifră care apare de minimum două ori.
b) Pentru 15: de la cifra iniţială 1, se numără o cifră şi se ajunge la cifra finală 5, apoi începând de la cifra 5 ca cifră iniţială, se numără cinci cifre şi se ajunge la cifra finală 1. Astfel cifrele 1, 5 sunt o singură dată cifre iniţiale şi după două aplicări ale algoritmului de deplasare se ajunge la prima cifră, deci 15 este număr circular.