Dat je niz brojeva a₁, a₂, ..., a_n. Pod konkatenacijom dva broja x i y podrazumevamo broj xy, koji je dobijen nadovezivanjem cifara broja y posle broja x (npr. konkatenacijom brojeva 123 i 45 dobijamo broj 12345). Veliki broj dobijamo kada dopisujemo brojeve jedan iza drugog u nekom redosledu. Odrediti najmanji broj koji se dobija konkatenacijom svih brojeva a₁, a₂, ..., a_n.

Ulaz:

(Ulazni podaci se nalaze u datoteci najmanji.in) U prvom redu ulazne datoteke nalazi se ceo broj n (2 ≤ n ≤ 5000). U sledećih n redova se nalaze prirodni brojevi a₁, a₂, ..., a_n (1 ≤ a_i ≤ 2000000000). Brojevi su zadati bez početnih (nevažećih) nula.

Izlaz:

(Izlazne podatke upisati u datoteku najmanji.out) U prvom redu izlazne datoteke ispisati najmanji broj koji se dobija konkatenacijom učitanih brojeva.

Ograničenja:

• Maksimalno vreme izvršavanja programa je 1 sekunda.

Primer 1:

2
91919
919191

91919191919

Primer 2:

5
32
11
987
12
3

1112323987

Objašnjenje:

Najmanji broj dobijamo konkatenacijom redom 11, 12, 32, 3, 987.

/*
  DRZAVNO TAKMICENJE 2008
  ZADATAK: najmanji
  AUTOR: Aleksandar i Andreja Ilic, Nis

    Treba odrediti permutaciju unetih brojeva a [1], a [2], ..., a [n]
  tako da je konkatenirani veliki broj najmanji moguc. Vrsimo zamenu
    dva susedna broja x i y  ako je broj xy veci od yx.

    Zbog ogranicenja u zadatku, brojeve je najbolje posmatrati kao
  stringove ili 64-bitne brojeve.

    Vremenska slozenost je O (n log n), a prostorna O (n).

*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>
#define MAXN 5001
using namespace std;

int n, length;
long a [MAXN];

// Fja uporedjivanja dva broja
int compare (const void * a, const void * b)
{
  __int64 x = *(long*) a;
  __int64 y = *(long*) b;

  long tmp = (long) y;
  __int64 xy = x;
  while (tmp > 0)
  {
    xy = xy * 10;
    tmp = tmp / 10;
  }
  xy = xy + y;

  tmp = (long) x;
  __int64 yx = y;
  while (tmp > 0)
  {
    yx = yx * 10;
    tmp = tmp / 10;
  }
  yx = yx + x;

  if (xy < yx)
    return -1;
  else if (xy > yx)
    return 1;
  else
    return 0;
}

int main ()
{
  /* Ucitavanje podataka */
  ifstream in ("najmanji.in");
  in >> n;
  for (int i = 0; i < n; i++)
    in >> a [i];
  in.close();

  /* Sortiranje */
  qsort (a, n, sizeof (long), compare);

  /* Stampa rezultata */
  ofstream out ("najmanji.out");
  for (int i = 0; i < n; i++)
    out << a [i];
  out << endl;
   out.close();
    return 0;
}