import java.io.*;
import java.util.*;
 
public class WordTable
{
  public WordTable(String filename, int nWords)
       throws FileNotFoundException
  {
    this.filename = filename;
    this.nWords = nWords;

    Words = new String[nWords];
 
    try {
      BufferedReader is = new BufferedReader(new FileReader(filename));
      readData(is);
      is.close();      
    }
    catch(IOException e) {
      System.out.print("ErrorPig: " + e);
      System.exit(1);
    }
  }

  public void readData(BufferedReader is) throws IOException
  {
    
    for(int i=0; i < nWords; i++)
      Words[i] = is.readLine().toLowerCase();

  }

  public void printWord(int r)
  {
    System.out.println(Words[r]);
  }

  public String getWord(int r)
  {
    return Words[r];
  }

  public int length()
  {
    return nWords;
  }

  // return largest word that starts incoming string
  // return empty string if fail
  public String LargestPrefix(String s)
  {
    int first = 0, last = nWords-1;

    // find where it would be, 
    // shrink it by one and re-search
    while (s.length() > 0) {
      Range r = SearchPrefix(s);

      // System.out.print("<" + s + "> ");
      // DumpRange(r);

      if (r.empty()) { // range is empty (word too big)
	s = s.substring(0, s.length() - 1);
      }
      else if (Words[r.begin()].length() == s.length())  // found it!
	return s;
      else {         // range doesn't include (word too small, or in between)
	s = s.substring(0, s.length() - 1);
      }
    }
    return s;
  }

  public void DumpRange(Range r)
  {
    System.out.println("Range of " + r.begin() + " to " + r.end());
    for (int i=r.begin(); i <=r.end(); i++) {
      printWord(i);
    }
  }

  public boolean isWord(String s)
  {
      Range r = SearchPrefix(s);
      if (r.empty())
	  return false;
      else return (getWord(r.begin()).length() == s.length());
  }

  // find range of wordlist that has s as a prefix
  public Range SearchPrefix(String s)
  {
    return SearchPrefixRanged(s, 0, nWords-1);
  }


  // Reasonably efficient version
  public Range SearchPrefixRanged(String s, int first, int last)
  {
    int middle = 0;
    boolean found = false;
    int top = first, bottom = last;
    int finalfirst, finallast;

    while (first <= last && !found) {
      middle = (first + last) / 2;
      // System.out.println("[mid:"+Words[middle]+"]");
      if (Words[middle].startsWith(s))
	found = true;
      else {
	if (Words[middle].compareTo(s) > 0)
	  last = middle - 1;
	else
	  first = middle + 1;
      }
    }

    int center = middle;

    // at this point, middle is somewhere in the range
    // of matches (if found at all)

    // To make this part more efficient, have it
    // binary search each part for edges, within constrained ranges
    if (found) {

      //  find first
      // binary search the range from the beginning to the known match
      first = top;
      last = center;
      while ((last-first) > 2) {
	middle = (first + last) / 2;
	if (Words[middle].startsWith(s))
	  last = middle;  // last stays in the range
	else
	  first = middle; // first stays in front of the range
      }
      // at this point, last is toward the left end of the matching range
      for (first = last; first >= 0 && Words[first].startsWith(s); first--)
	;
      finalfirst = first + 1;

      //  find last
      // binary search the range from the known match to the end
      first = center;
      last = bottom;
      while ((last-first) > 2) {
	middle = (first + last) / 2;
	if (Words[middle].startsWith(s))
	  first = middle;  // first stays in the range
	else
	  last = middle;  // last stays after the range
      }
      // at this point, first is toward the right end of the matching range
      for (last = first; last < nWords && Words[last].startsWith(s); last++)
	;
      finallast = last - 1;
    }
    else{
      finalfirst = 0;
      finallast = finalfirst - 1;
    }
    
    Range r = new Range(finalfirst, finallast);
    return r;
  }



  // find range of wordlist that has s as a prefix
  public Range SearchPrefixOLD(String s)
  {
    return SearchPrefixRangedOLD(s, 0, nWords-1);
  }



  // Inefficient, old version
  public Range SearchPrefixRangedOLD(String s, int first, int last)
  {
    int middle = 0;
    boolean found = false;

    while (first <= last && !found) {
      middle = (first + last) / 2;
      // System.out.println("[mid:"+Words[middle]+"]");
      if (Words[middle].startsWith(s))
	found = true;
      else {
	if (Words[middle].compareTo(s) > 0)
	  last = middle - 1;
	else
	  first = middle + 1;
      }
    }

    // inefficient linear search part
    if (found) {
      for (first = middle; first >= 0 && Words[first].startsWith(s); first--)
	;
      first++;

      for (last = middle; last < nWords && Words[last].startsWith(s); last++)
	;
      last--;
    }
    else
      last = first - 1;
    
    Range r = new Range(first, last);
    return r;
  }



  public static void main(String[] args) throws FileNotFoundException
  {
    if (args.length != 2)
      System.out.println("Usage: java WordTable <dict> <length>");
    else {
      WordTable wt = 
	new WordTable(args[0], Integer.parseInt(args[1]));
      wt.printWord(0);
      wt.printWord(10);
      wt.printWord(100);
      wt.printWord(1000);
      wt.printWord(Integer.parseInt(args[1]) - 1);
    }
  }

  private int nWords;
  private String filename;
  private String[] Words;
}