//------------
// Introduction to Programming Using Java: An Object-Oriented Approach
//	Arnow/Weiss
//------------
// the search method
// Chapter 10, Section 10.4, Page 395
// MODIFICATIONS:
//    search and moveHalfwayUp are made static here so we
//    can test them 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 TestmoveHalfway {
	private static void  moveHalfwayUp(Vector  v,  int  k)  {
		if  (k!=0)  {  
			v.insertElementAt(v.elementAt(k),k/2);
			v.removeElementAt(k+1);
		}
	}

	private static int search(String s) {	// Returns the index of a match to s in v
						//    or -1 if there is no match
		int k;	// k== the index of the next position in the vector to check.
			// No match has been found in positions 0 through k-1.
		k = 0;
		while (!(k==v.size() || s.equals(v.elementAt(k))))
			k++;
		// k==v.size() || s.equals(v.elementAt(k))
		if (k==v.size())
			return -1;
		else {
			moveHalfwayUp(v,k);	// Found a match at position k,
						//   move half way up
			if (k!=0)
				return k/2;
			else
				return 0;
		}
	}

	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();
		}
		int k=0;
		while (k != v.size()) {
			String s = (String) v.elementAt(k);
			int m=search(s);
			if (k==0) {
				if (m!=0 || !s.equals((String)v.elementAt(m))) {
					System.err.println("search failure");
					fails = true;
				}
			} else if (m!=k/2 || !s.equals((String)v.elementAt(m))) {
				System.err.println("search failure");
				fails = true;
			}
			k++;
		}
		if (search(huge)!=-1) {
			System.err.println("search failure");
			fails = true;
		}
		k=0;
		while (k != v.size()) {
			String s = (String) v.elementAt(k);
			int m=search(s);
			if (k==0) {
				if (m!=0 || !s.equals((String)v.elementAt(m))) {
					System.err.println("search failure");
					fails = true;
				}
			} else if (m!=k/2 || !s.equals((String)v.elementAt(m))) {
				System.err.println("search failure");
				fails = true;
			}
			k++;
		}
		if (search(huge)!=-1) {
			System.err.println("search failure");
			fails = true;
		}
		if (!fails)
			System.out.println("search passes these tests");
	}

	static Vector v;
}

// Sample test input (no duplicates allowed!)
// butter
// mustard
// ketchup
// abc
// x
// z
// antidisestablishmentarianism