import java.io.*;    // for BufferedReader
import java.util.*;
    public class scramble  {
   
       public static void main(String[] args) throws IOException {
      
         String fileName = "inputstrings.txt", wordString, input;
         BufferedReader inFile = new BufferedReader(new FileReader(fileName));
         wordString = inFile.readLine();
         while (wordString != null) {
            System.out.println("Input word: " + wordString);
            ScrambleWord dummy = new ScrambleWord(wordString, "wordlist.txt");
            dummy.OutputData();
            wordString = inFile.readLine();
         }
         inFile.close();
      }
   }
    
    class ScrambleWord {
    	  
    	
    	 private Random generator = new Random();
    	 private String dictFile;
    	 private String input;
    	 private String scrWord;
    	 private Vector tempVector = new Vector();
    	 private String[] dictionaryArray;
    	 
    	ScrambleWord(String word, String fileName) throws IOException {
   	           
    		   dictFile=fileName;
    		   
    		  input = word;
    		  scram(input);
   	           
    		   
   	           
   	           BufferedReader inFile = 
   	        	   new BufferedReader(new FileReader(dictFile));
   	           while(!(inFile.readLine()== null)){
     	        	   tempVector.add(inFile.readLine());
   	           }
   	        String[] dictionaryArray = new String[tempVector.size()]; 
   	       	
   	         tempVector.copyInto(dictionaryArray);
   	        this.dictionaryArray = dictionaryArray;
     	   	        	
    	}
 		
    		private void scram(String input){
    			 String a = "";
    			 System.out.println(input);
    			for (int i = 0 ;i < (input.length()-1);i++){
    			if (generator.nextBoolean())
    				a = input.charAt(i) + a;
    				
    				else 
    					a = a + input.charAt(i);
        		}
    				scrWord = a;
    	}
    	
    	public void OutputData() {
    		
    		//System.out.println("testS2 " + scrWord);
    		
    		long start = System.currentTimeMillis();
    		// exit condition for while loop
    		boolean reportedSingle = false; 
    		boolean reportedDouble = false; 
    		boolean reportedTriple = false; 
    		//loops for a the a set time or if the word has been found
    		String b;
    		while((System.currentTimeMillis()-start) < 60000 ){
    			//System.out.println(System.currentTimeMillis()-start);
    			
    			 b = search(input, dictionaryArray);
    			
    		         if (b == null ){
    		        	 scram(b);
    		        	 //System.out.println(scrWord + "not found");
    	
    		         }
      				
    		         else if  (!reportedSingle){
    		        	 
    		        	 System.out.println("single:" + b);
    		        	reportedSingle = true;
    		        		
    		         }
    		         
    		         if (b.length() > 6 && !reportedDouble){
    		        	 int mid = b.length() / 2;
    		        	 String firstWord = b.substring(0, mid-1);
    		        	 String secondWord = 
    		        		 	b.substring(mid, b.length()-1);
    		        	 
    		        	scram(firstWord);
    		        	  String c = scrWord;
    		        	 scram(secondWord);
    		        	 	String d = scrWord;
    		        	 
    		        	 if ((search(firstWord, dictionaryArray)== null ))
    		        		 scram(firstWord);
    		        	        
    		        	 	else {
    		        	 		search(firstWord, dictionaryArray);
    		        	 		System.out.println("first word:" + firstWord); 
    		        	 	}
    		        	 if ((search(secondWord, dictionaryArray)== null ))
    		        		 scram(secondWord);
    		        	 	else {
    		        	 		search(secondWord, 
    		        					 			 dictionaryArray);
    		        			 System.out.println("first word:" + firstWord);
   
    		        	 }
    		        	
    		        }
    		         reportedDouble = true;
    		         
    		}
    	
    	}
    		
    	static String search(String targetWord, String[] sArray){
    		//System.out.println("index: "+ (sArray.length-1) );
    	   return searchHelper(targetWord, sArray, 0, (sArray.length-1));
    	}
    	
    	static String searchHelper(String targetWord,
    							   String[] sArray, int low, int high){
    		String rtn;
    		if (low > high){
    			
    			rtn = null;
    		}
    		else{
    			int middle = (low + high) / 2;
    			
    			if(sArray[middle].equals(targetWord))
    				rtn =  sArray[middle];
    			else if (sArray[middle].compareTo(targetWord) < 0)
    				rtn = searchHelper(targetWord, sArray, middle+1, high);
    			else 
    				rtn = searchHelper(targetWord, sArray, low, middle - 1);
     		 
    		}	
    		return rtn;
   	   }
  }