import collections import itertools class Deque(collections.deque): def __le__(self, other): for e1, e2 in itertools.zip_longest( # self, other, fillvalue='{'): if e1 == e2: continue elif e1 < e2: return True elif e1 > e2: return False return True def __lt__(self, other): return Deque.__le__(self, other) and not Deque.__eq__(self, other) def main(): str_deque = initialize() up_heap(str_deque) print(min_dict_order(str_deque)) def initialize(): N = int(input()) str_deque = Deque(Deque(input()) for i in range(N)) return str_deque def up_heap(str_deque: Deque): for index in range(len(str_deque) - 1, -1, -1): min_index = get_min_index(str_deque, index) if min_index != index: swap(str_deque, index, min_index) def min_dict_order(str_deque: Deque): seq = '' while True: for e in str_deque: print(e) chr_deque = str_deque[0] seq += chr_deque.popleft() if not chr_deque: str_deque.popleft() try: str_deque.appendleft(str_deque.pop()) except IndexError: break down_heap(str_deque) return seq def down_heap(str_deque: Deque): index = 0 while True: min_index = get_min_index(str_deque, index) if min_index == index: break else: swap(str_deque, index, min_index) index = min_index def get_min_index(str_deque, index): dct = {index: str_deque[index]} try: dct.update({2 * index: str_deque[2 * index]}) except IndexError: pass try: dct.update({2 * index + 1: str_deque[2 * index + 1]}) except IndexError: pass return min(dct, key=dct.get) def swap(seq, i, j): tmp = seq[i] seq[i] = seq[j] seq[j] = tmp if __name__ == '__main__': main()