// yukicoder: No.205 マージして辞書順最小 // 2019.4.15 bal4u #include //// 高速入力 #if 1 #define gc() getchar_unlocked() #define pc(c) putchar_unlocked(c) #else #define gc() getchar() #define pc(c) putchar(c) #endif int in() // 非負整数の入力 { int n = 0, c = gc(); do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0'); return n; } int ins(char *s) // 文字列の入力 スペース以下の文字で入力終了 { char *p = s; do *s = gc(); while (*s++ > ' '); *--s = 0; return s - p; } void outs(char *s) { while (*s) pc(*s++); } //// 優先度付きキュー #define MAX 10000 typedef struct { int id; char c; } QUE; QUE que[MAX]; int qsize; #define PARENT(i) ((i)>>1) #define LEFT(i) ((i)<<1) #define RIGHT(i) (((i)<<1)+1) void min_heapify(int i) { int l, r, min; QUE qt; l = LEFT(i), r = RIGHT(i); if (l < qsize && que[l].c < que[i].c) min = l; else min = i; if (r < qsize && que[r].c < que[min].c) min = r; if (min != i) { qt = que[i]; que[i] = que[min]; que[min] = qt; min_heapify(min); } } void deq() { que[0] = que[--qsize]; min_heapify(0); } void enq(int id, char c) { int i, min; QUE qt; i = qsize++; que[i].id = id, que[i].c = c; while (i > 0 && que[min = PARENT(i)].c > que[i].c) { qt = que[i]; que[i] = que[min]; que[min] = qt; i = min; } } int N; char S[55][55]; int w[55], top[55]; char ans[3000]; int sz; int main() { int i, c, N; N = in(); for (i = 0; i < N; i++) { w[i] = ins(S[i]); enq(i, S[i][0]), top[i] = 1; } while (qsize) { c = que[0].c, i = que[0].id, deq(); ans[sz++] = c; if (top[i] < w[i]) enq(i, S[i][top[i]++]); } ans[sz] = 0, outs(ans), pc('\n'); return 0; }