Ana şi Bogdan joacă un nou joc, numit R&V. Jocul are două table de joc: una roşie şi una verde. Pe tabla roşie este iniţial plasat un şir de jetoane, pe fiecare jeton fiind scrisă o literă mică a alfabetului englez. Tabla verde este iniţial goală.
Ana şi Bogdan execută mutări pe rând, Ana fiind prima la mutare. La o mutare, jucătorul care este la rând trebuie să ia un jeton de la unul dintre capetele şirului aflat pe tabla roşie şi să îl plaseze pe tabla verde, la sfârşitul şirului de jetoane de pe această tablă. Jocul continuă până când toate jetoanele se află pe tabla verde.
Scopul Anei este ca şirul obţinut pe tabla verde să fie cât mai mare din punct de vedere lexicografic.
Scopul lui Bogdan este ca şirul obţinut pe tabla verde să fie cât mai mic din punct de vedere lexicografic.

Cerinţă

Scrieţi un program care să determine şirul obţinut pe tabla verde la finalul jocului, în ipoteza că ambii jucători joacă optimal.

Date de intrare

Fişierul de intrare rv.in conţine pe prima linie un şir de litere mici ale alfabetului englez, reprezentând în ordine literele de pe jetoanele aflate pe tabla roşie la începutul jocului.

Date de ieşire

Fişierul de ieşire rv.out va conţine o singură linie pe care vor fi scrise în ordine literele scrise pe jetoanele de pe tabla verde la finalul jocului, în ipoteza că ambii jucători joacă optimal.

Restricţii

• Pe tabla roşie se află iniţial cel mult 100 de jetoane.
• Fie x₁x₂...x_n si y₁y₂...y_n doua siruri. Spunem ca x este mai mic decat y din punct de vedere lexicografic daca exista un indice k (1<=k<=n) astfel incat x_i=y_i (pentru orice 1<=i<k) si x_k<y_k.

Exemple

rv.in	rv.out
abcde	eadbc

rv.in	rv.out
aaaca	aacaa

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com