Task «Triple sorting: frequency, length, lexicographically»

Given a list of strings. Sort the strings according to three criteria: first by decreasing frequency of occurrence of the string in the original list, then by increasing length of the string, and finally lexicographically (in increasing order, standard string comparison). If two strings have the same frequency and length, they are compared lexicographically. Implement the sorting without using the built-in sort function with a custom key (prohibited), but only using your own sorting function (e.g., quicksort, merge sort, or another). Input data: first an integer N (1 ≤ N ≤ 10^5) — the number of strings, then N strings. Output the strings in sorted order, each on a new line. Time limit: 2 seconds, memory limit: 256 MB.

Example 1

Example 2