Sakurako et le vieux dictionnaire#11716

Sakurako et le vieux dictionnaire

1,25 seconde
256 mégaoctets
Difficile

Sakurako range la chambre. Il a trouvé un dictionnaire qui contient chaînes. Cependant, ce dictionnaire est particulier, et la présence d'une chaîne dans le dictionnaire ne signifie pas qu'un tel mot existe réellement.

Tout mot du monde de Sakurako peut être obtenu en réorganisant les chaînes dans le dictionnaire et en les concaténant en un seul mot. Par exemple, si le dictionnaire contient les chaînes : , les mots possibles sont : .

Comme le dictionnaire est un peu obsolète, de nouveaux mots sont apparus dans le monde. Ils peuvent encore être obtenus à partir de ce dictionnaire si au maximum chaînes sont inversées.

Aidez Sakurako à trouver le mot le plus petit lexicographiquement possible dans la vie moderne.

Entrée

La première ligne contient deux entiers n, k ~(1\le n\le 2\cdot 10^5;~k\in\{0,1\}) — le nombre de mots dans le dictionnaire et le nombre d'inversions possibles.

Chacune des lignes suivantes contient une chaîne s~(1\le |s_i|\le 2\cdot 10^5) qui appartient au dictionnaire.

Il est garanti que \sum |s_i|\le 4\cdot 10^5 et que toutes les chaînes sont composées de lettres minuscules anglaises.

Sortie

Sur une seule ligne, affichez le mot le plus petit lexicographiquement.

Exemples

Exemple

Loading
Loading

Notation

  1. ( points) : k = 0, ~|s_1|=|s_2|=\dots=|s_n| ;

  2. ( points) : k = 0, ~|s_i|\le 10 ;

  3. ( points) : k = 0 ;

  4. ( points) : n \le 500, ~|s_i|\le 10 ;

  5. ( points) : n \le 1000 ;

  6. ( points) : |s_1|=|s_2|=\dots=|s_n| ;

  7. ( points) : s_i est constitué de lettres et ;

  8. ( points) : sans restrictions supplémentaires.