4-2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

void permute(char *str, int left, int right, char **permutations, int *count) {
    if (left == right) {
        permutations[*count] = (char *)malloc((right + 2) * sizeof(char));
        strcpy(permutations[*count], str);
        (*count)++;
        return;
    }

    for (int i = left; i <= right; i++) {
        swap(&str[left], &str[i]);
        permute(str, left + 1, right, permutations, count);
        swap(&str[left], &str[i]);
    }
}

int compareStrings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    char input[100];
    char *permutations[10000]; 
    int count = 0;

    scanf("%s", input);

    int length = strlen(input);
    permute(input, 0, length - 1, permutations, &count);

    qsort(permutations, count, sizeof(char *), compareStrings);

    for (int i = 0; i < count; i++) {
        printf("%s\n", permutations[i]);
        free(permutations[i]);
    }

    return 0;
}