//------------
// Introduction to Programming Using Java: An Object-Oriented Approach
//	Arnow/Weiss
//------------
// the search method
// Chapter 10, Section 10.4, Page 395
// MODIFICATIONS:
//    bsearch is made static here so we
//    can test it without creating an object
//    main creates a Vector of Strings from input and then tests to see if
//	each String can be found in the Vector.

import java.io.*;
import java.util.*;

class Testbsearch {
	static boolean bsearch(String s) {	// Returns true if and only if s equals one 
					//       of the Strings in v
		int    left, right;
		// If the String is anywhere, it is in positions left through right-1.
		// The String is not in a position before left.
		// The String is not in a position after right-1.
		// left<right
		left = 0;
		right = v.size();
		while  (left!=right-1)  {
			// 0<=left<right-1<right<=v.size()  and so right-left>=2
			int  m  =  (right+left)/2;
			// 0<=left<m<=right-1<right<=v.size()
			String sm  =  (String)  v.elementAt(m);
			if  (sm.compareTo(s)<0)
				left  =  m;        // Move left to the middle.
			else  if  (sm.compareTo(s)>0)
				right  =  m;       // Move right to the middle.
			else  {
				left  =  m;
				right  =  m+1;
			}
		}
		// left==right-1
		return s.equals((String) v.elementAt(left));
	}

	public static void main(String[] a) throws Exception {
		boolean fails=false;
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		v = new Vector();
		String line = f.readLine();
		String huge = "";
		while (line != null) {
			huge = huge.concat(line);
			v.addElement(line);
			line = f.readLine();
		}

		Enumeration e = v.elements();
		while (e.hasMoreElements()) {
			System.out.print((String)e.nextElement());
			System.out.print(" ");
		}
		System.out.println();

		int m=0;
		while (m!=v.size()) {
			String s = (String) v.elementAt(m);
			System.out.println(s+" "+bsearch(s));
			m++;
		}





		int k=0;
		while (k != v.size()) {
			fails |= !bsearch((String)v.elementAt(k));
			k++;
		}
		fails |= bsearch(huge);
		if (fails)
			System.out.println("search fails these tests");
		else
			System.out.println("search passes these tests");
	}

	static Vector v;
}

// Sample test input (must be sorted!)
// antidisestablishmentarianism
// abc
// butter
// butter
// ketchup
// mustard
// x
// z