import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AutocompleteSystem
{
	TrieAS root = new TrieAS();

	public AutocompleteSystem( String[] sentences, int[] times )
	{
		for ( int i = 0; i < sentences.length; i++ )
		{
			root.update( sentences[i], times[i] );
		}
	}

	StringBuilder find = new StringBuilder();

	public List<String> input( char c )
	{
		if ( c == '#' )
		{
			root.update( find.toString(), 1 );
			find.delete( 0, find.length() );
			return new ArrayList<>();
		}
		find.append( c );
		List<String[]> list = new ArrayList<>();
		findStr( find.toString(), list );
		Collections.sort( list, new Comparator<String[]>()
		{

			@Override
			public int compare( String[] o1, String[] o2 )
			{
				int v1 = Integer.valueOf( o1[1] ), v2 = Integer.valueOf( o2[1] );
				return v1 != v2 ? v2 - v1 : o1[0].compareTo( o2[0] );
			}

		} );
		List<String> ret = new ArrayList<>();

		for ( int i = 0, n = list.size(); i < Math.min( 3, n ); i++ )
		{
			ret.add( list.get( i )[0] );
		}
		return ret;
	}

	void findStr( String string, List<String[]> list )
	{
		TrieAS r = root;
		for ( char k : string.toCharArray() )
		{
			int pos = k == ' ' ? 26 : k - 'a';
			if ( r._child[pos] == null )
				return;
			r = r._child[pos];
		}
		for ( String s : r.map.keySet() )
			list.add( new String[] { s, String.valueOf( r.map.get( s ) ) } );

	}

	public static void main( String[] args )
	{
		String[] s = { "i love you", "island", "iroman", "i love leetcode" };
		int[] t = { 5, 3, 2, 2 };
		AutocompleteSystem ats = new AutocompleteSystem( s, t );
		String[][] inp = { { "i" }, { " " }, { "a" }, { "#" }, { "i" }, { " " }, { "a" }, { "#" }, { "i" }, { " " }, { "a" }, { "#" } };
		for ( int i = 0; i < inp.length; i++ )
			System.out.println( ats.input( inp[i][0].toCharArray()[0] ) );
	}
}

class TrieAS
{
	TrieAS[] _child = new TrieAS[27];
	Map<String, Integer> map = new HashMap<>();
	List<String> _str = new ArrayList<>();
	List<Integer> _hotness = new ArrayList<>();

	void update( String string, int hotness )
	{
		TrieAS root = this;
		for ( char k : string.toCharArray() )
		{
			int pos = k == ' ' ? 26 : k - 'a';
			if ( root._child[pos] == null )
				root._child[pos] = new TrieAS();
			root.map.put( string, root.map.getOrDefault( string, 0 ) + hotness );
			root = root._child[pos];
		}
		root.map.put( string, root.map.getOrDefault( string, 0 ) + hotness );
	}

}