import java.util.*;

public class BurrowsWheelerTransform
{
	private static char EOF = '\u0007';
	private static int CHUNK_SIZE = 25000; //in characters
	
	public static String encode(String input)
	{
		input += EOF;
		StringBuilder output = new StringBuilder();
		ArrayList<String> transformation = new ArrayList<String>(input.length());
		
		for (int i=0; i < input.length(); ++i)
		{
			transformation.add(input.substring(input.length() - i, input.length()) + input.substring(0, input.length() - i));
		}
		
		Collections.sort(transformation);
		
		for (String s : transformation)
		{
			output.append(s.charAt(s.length() - 1));
			//System.out.println(s);
		}
		
		return output.toString();
	}
	
	public static String decode(String input)
	{
		String output = new String();
		
		ArrayList<String> matrix = new ArrayList<String>(input.length());
		
		for (int i=0; i < input.length(); ++i)
		{
			matrix.add(new String(input.substring(i, i+1)));
		}
		
		Collections.sort(matrix);
		
		for (int i=1; i < input.length(); ++i)
		{
			for (int j=0; j < matrix.size(); ++j)
			{
				matrix.set(j, input.substring(j, j+1) + matrix.get(j));
			}
			
			Collections.sort(matrix);
		}
		
		for (String s : matrix)
		{
			if (s.charAt(s.length()-1) == EOF)
			{
				output = s.substring(0, s.length()-1);
			}
		}

		return output.toString();
	}
}