#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

int longest_non_inc(char v[], int len) {
  int i = len - 2;

  while (i >= 0 && v[i] >= v[i+1]) {
    i--;
  }
  return i;
}

int swap_location(char v[], int len, char x) {
  int j = len - 1;
  while (v[j] <= x) {
    j--;
  }
  return j;
}

int verbose = 0;

bool next(char v[], int len) {

  int i = longest_non_inc(v, len);
  if (i < 0) {
    return false;
  }
  int j = swap_location(v, len, v[i]);

  if (verbose) {
    printf("---------------------\n");
    printf("%s\n", v);
    for (int l = 0; l < i; l++) {
      printf(" ");
    }
    printf("i");
    for (int l = 0; l < j - i - 1; l++) {
      printf(" ");
    }
    printf("j\n");
  }

  std::swap(v[i], v[j]);
  if (verbose) {
    printf("%s (swapped)\n", v);
  }
  std::reverse(v + i + 1, v + len);

  if (verbose) {
    for (int l = 0; l < i + 1; l++) {
      printf(" ");
    }
    printf("^");
    for (int l = 0; l < len - (i + 1) - 1; l++) {
      printf(" ");
    }
    printf("^\n");
    printf("%s (reversed)\n", v);
    printf("---------------------\n");
  }
  return true;
}


int main(int argc, char *argv[]) {
  int maxlen = 100;
  char v[maxlen];

  if (argc < 2 || argc > 3) {
    printf("Usage %s: <string>\n", argv[0]);
    return 0;
  }

  if (argc == 3) {
    verbose = 1;
  }

  strcpy(v, argv[1]);

  int len = strlen(v);

  for (;;) {
    printf("%s\n", v);
    if (!next(v, len)) {
      break;
    }
  }
}