import java.util.Arrays;

public class BurrowsWheeler {
    // apply Burrows-Wheeler encoding, reading from standard input and writing to standard output
    public static void encode()
    {
    	String s = BinaryStdIn.readString();
    	int length = s.length();
    	int index = 0;
    	String[] permutations = permutate(s, length);
    	Arrays.sort(permutations);
    	char[] encoded = new char[length];
    	for(int i = 0; i < length; i++) {
    		encoded[i] = permutations[i].charAt(length-1);
    		if(permutations[i].equals(s)) index = i;
    	}
    	BinaryStdOut.write(index);
    	BinaryStdOut.write(String.valueOf(encoded));
     	StdOut.println(String.valueOf(encoded));
    }
    // apply Burrows-Wheeler decoding, reading from standard input and writing to standard output
    public static void decode()
    {
    	int sortedRow = BinaryStdIn.readInt();
    	String encoded = BinaryStdIn.readString();
    	char[] charList = encoded.toCharArray();
    	int length = charList.length;
    	//Sorted suffix array and next array
    	char[][] suffix = new char[length][length];
    	int[] next = new int[length];
    	for(int i = 0; i < length; i++) {
    		suffix[i][length-1] = charList[i];
    	}
    	Arrays.sort(charList);
    	for(int i = 0; i < length; i++) {
    		suffix[i][0] = charList[i];
    	}

    	int repeat = 0;
    	int rrpeat;
    	for(int i = 0; i < length; i++) {
    		if(i != 0) {
    			if(suffix[i-1][0] == (suffix[i][0])) repeat += 1;
    			else repeat = 0;
    		}
    		rrpeat = repeat;
    		for(int j = 0; j < length; j++) {
    			//int rrpeat = repeat;
    			if(j != i && suffix[i][0] == suffix[j][length-1] && repeat == 0) {
    				next[i] = j;
    				break;
    			}
    			else if(j != i && suffix[i][0] == suffix[j][length-1] && repeat > 0) {
    				repeat--;
    				continue;
    			}
    		}
    		repeat = rrpeat;
    	}
    	char[] original = new char[length];
    	for(int i = 0; i < length; i++) {
    		original[i] = suffix[sortedRow][0];
    		sortedRow = next[sortedRow];
    	}
    	BinaryStdOut.write(String.valueOf(original));

    }
    // if args[0] is '-', apply Burrows-Wheeler encoding
    // if args[0] is '+', apply Burrows-Wheeler decoding
    public static void main(String[] args)
    {
    	if(args[0].equals("-"))encode();
		else if(args[0].equals("+")) decode();
    }

    public static String[] permutate(String s, int length) {
    	String[] permutations = new String[length];
    	char[] stringedit = s.toCharArray();
    	permutations[0] = String.valueOf(stringedit);
    	for(int i = 1; i < length; i++) {
			char lastchar = stringedit[0];
			char temp = stringedit[1];
    		//move characters left by 1
    		for(int j = length-1; j >= 0; j--) {
    			temp = stringedit[j];
    			stringedit[j] = lastchar;
    			lastchar = temp;
    		}
    		//stringedit[0] = ;
    		permutations[i] = String.valueOf(stringedit);
    	}

		return permutations;
    }
}