#include <iostream>

void backtrack(int p, int n, char* trace, int* avail) {
    if (p == n) {
        std::cout << trace << '\n';
        return;
    }
    for (int i = 255; i >= 0; --i) {
        if (avail[i] > 0) {
            trace[p] = 127 - i;
            avail[i]--;
            backtrack(p+1, n, trace, avail);
            avail[i]++;
        }
    }
}

void permuteString(int n, char* str) {
    char* trace = new char[n+1]();
    int* avail = new int[256]();
    for (int i = 0; i < n; ++i) {
        avail[127 - str[i]]++;
    }
    backtrack(0, n, trace, avail);
    delete[] avail;
    delete[] trace;
}

int main() {
    int n;
    char* str;
    std::cout << "Enter n: ";
    std::cin >> n;
    str = new char[n+1]();
    std::cout << "Enter string: ";
    std::cin.ignore(1000, '\n');
    std::cin.get(str, n+1, '\n');

    permuteString(n, str);

    delete[] str;

    return 0;
}