Задача «Тройная сортировка: частота, длина, лексикографически»

Дан список строк. Требуется отсортировать строки по трём критериям: сначала по убыванию частоты встречаемости строки в исходном списке, затем по возрастанию длины строки, и наконец лексикографически (по возрастанию, стандартное сравнение строк). Если две строки имеют одинаковую частоту и длину, сравниваются лексикографически. Реализуйте сортировку без использования встроенной функции sort с кастомным ключом (запрещено), а только с помощью собственной функции сортировки (например, быстрой сортировки, сортировки слиянием или другой). Входные данные: сначала целое число N (1 ≤ N ≤ 10^5) — количество строк, затем N строк. Выведите строки в отсортированном порядке, каждую на новой строке. Ограничение по времени: 2 секунды, по памяти: 256 МБ.

Пример 1

Пример 2