Custom Sort Orders

Lab C++ Intermediate 20 points

Read n words and sort them by length descending, then alphabetically, using sort with a lambda. Then print the words sorted by their last letter with stable_sort (keeping the previous order for ties).

Input

n, then n words.

Output

Two lines.

Example

Input

6
banana kiwi apple fig cherry plum

Output

banana cherry apple kiwi plum fig
banana apple fig kiwi plum cherry

Sample input available Sample output available

Editor

C++

Hints

Chaining a stable sort after another sort keeps the first order among ties.

Solution explanation

This "sort by secondary key, then stable sort by primary key" trick is widely used.

Show solution

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void print(const vector<string> &v) {
    for (size_t i = 0; i < v.size(); i++) cout << v[i] << (i + 1 < v.size() ? " " : "\n");
}

int main() {
    int n;
    cin >> n;
    vector<string> w(n);
    for (auto &s : w) cin >> s;
    sort(w.begin(), w.end(), [](const string &a, const string &b) {
        if (a.size() != b.size()) return a.size() > b.size();
        return a < b;
    });
    print(w);
    stable_sort(w.begin(), w.end(), [](const string &a, const string &b) { return a.back() < b.back(); });
    print(w);
    return 0;
}

Output

Answer