/**************************************************************************
 * Solution for ITA word numbers puzzle
 * Author: Wim Rijnders (wordnumbers AT axizo DOT nl)
 * Date_ 2 october 2007.
 *
 * See: htpp://www.wimrijnders/wordnumbers for details.
 *
 * You need a java 5 compliant compiler and runtime for compilation and 
 * execution.
 *
 * Compilation: javac WordNumbers.java
 * Execution:   java [-ea] WordNumbers
 *
 * 		-ea switch is for enabling assertion; optional
 *
 *************************************************************************/
import java.util.Collections;
import java.util.Vector;


/**
 * Simple Logger class, in order to centralize
 * tracing output.
 */
class Logger {
	static boolean enableTraces = true;

	static void displayTraces( boolean val ) {
		enableTraces = val;
	}	


	void trace( String val ) {
		if ( enableTraces ) {
			out( val );
		}
	}

	void out( String val ) {
		System.out.println( val);
	}
}


/**
 * Definition of a net, in which the nodes are doubly linked.
 *
 * The nodes are collected into graphs, which give a higher abstraction for 
 * manipulating collections of nodes.
 *
 */
abstract class Node implements Comparable<Node> {
	protected static Logger log = new Logger();

	Vector<Node> next     = new Vector<Node>();
	Vector<Node> previous = new Vector<Node>();

	void addNext( Node n) {
		this.next.add( n );
		n.previous.add( this );
	}


	/**
 	 * Remove the double link between the given nodes 
 	 * from the next-list.
 	 */
	void unlinkNext( Node n ) {
		next.removeElement( n );
		n.previous.removeElement(this);
	}


	/**
 	 * Take out given node from the graph, and rearrange previous and next
 	 * links of this node so that associations are still correct.
 	 */
	void removeNode() {
		Vector<Node> previousNodes = new Vector<Node>(previous);
		Vector<Node> nextNodes     = new Vector<Node>(next);
		
		// unlink from all previous and next
		for ( Node node: previousNodes ) {
			node.unlinkNext( this );
		}

		for ( Node node: nextNodes ) {
			this.unlinkNext( node );

			// Because of seg. fault (read below), we need to explicitly add the
			// previous link like following: somehow the addNext() doesn't work
			// within a loop over the Vector in which addNext() is executed.
			for ( Node node2: previousNodes ) {
				node.previous.add( node2);
			}
		}

		// Link up all previous and next nodes directly
		for ( Node node: previousNodes ) {
			// for() { addNext(); } - doesn't work here, produces segmentation fault.
			node.next.addAll( nextNodes );
		}
	}


	/**
 	 * Return true if current node does not have any next-nodes,
 	 * ie. is a leaf.
 	 *
 	 * Derived classes should override this method with their 
 	 * own implementation.
 	 */
	boolean isFinalNode() { return false; }


	/**
 	 * If this node does not have any previous nodes any more,
 	 * unlink from next nodes as well.
 	 *
 	 * This is done in order to remove the double links, so that
 	 * there will not be any references to the current node.
 	 *
 	 */ 
	void removeIfUnlinked() {
		if ( previous.size() == 0 ) {
			//log.trace( "Node of type '" + getClass().getName() + "' without previous.");
			for( Node node2: next ) {
				node2.previous.removeElement( this );
			}

			// Note that we do not clean up de next Vector
			// Since the double links are removed, this should be no problem.
		}
	}

	
	void copyLinks( Node n ) {
		copyLinks( n, true );
	}

	void copyLinks( Node n, boolean copyPrevious ) {
		n.next.addAll( next );

		if ( copyPrevious ) {
			n.previous.addAll( previous );
		}
	}
}


class EndNode extends NumberNode {

	EndNode() {
		name = "";
	}


	protected String print( int level, int depth ) {
		String out = "";


		if ( isFinalNode() ) {
			if ( depth != -1 && level > depth ) return "";

			String tabs = makeTabs( level );
			
			// Show explicitly as space
			out += tabs + ":0,0,1\n";
			// Don't drill deeper
		} else {
			// Don't print end node name - there isn't any
			// There might be more nodes after this one, though
			for ( Node node: next ) {
				// level left same intentionally
				out += ( (NumberNode) node ).print( level, depth );
			}
		}

		return out;
	}

	boolean isFinalNode() {
		return next.size() == 0;
	}
}


class Graph extends NumberNode {
	NumberNode last = new EndNode();

	Graph( String name ) {
		this.name = name;
	}

	void addNext( Node n, boolean fixlast ) {
		super.addNext( n );

		if ( fixlast) {
			n.addNext( last );
		}
	}

	protected int getNamelength() {
		// Graph names shouldn't count in running totals
		// of number words
		return 0;
	}

	protected String print( int level, int depth ) {
		if ( depth != -1 && level > depth ) return "";

		String tabs = makeTabs( level );
		String out = "";

		// Only level 0 is printed entirely.
		// Contents of graphs in lower levels aren't printed,
		// only the name. Further printing is then
		// passed on to whatever comes after this graph
		out += tabs + "[" + name + "]:";

		if ( printLengths ) {
			out += accumulatedLength;
		} else {
			out += value;
		}

		out += "," + accumulatedPaths;

		if ( inPath ) out+= "!";
		out	+= "\n";

		if ( level != 0 ) {
			out += last.print( level +1, depth );
		} else {
			out += super.print( level, depth );
		}

		return out;
	}


	void removeNode() {
		last = null;

		super.removeNode();
	}
}


class NumberAccumulator {
	protected static Logger log = new Logger();

	long tens;      // Digits before first 'hundred'
	long hundred;   // Digits before first 'hundred'

	/* digits before first 'thousand' */
	long tens_th;
	long hundred_th;

	/* Digits directly before 'million' */
	long tens_m;
	long hundred_m;

	/* Digits before the 'thousand million' */
	long tens_th_m;
	long hundred_th_m;

	long sum = 0;
	long multiplier = 1;

	void addValue( long val) {
		tens += val;
	}


	/** 
 	 * Move digits to before 'hundred'.
 	 */
	void doHundred() {
		hundred = tens;
		tens = 0;
	}


	/** 
 	 * Move digits to before 'thousand'.
 	 */
	void doThousand() {
		hundred_th = hundred;
		tens_th = tens;
		
		hundred = 0;
		tens = 0;
	}


	/** 
 	 * Move digits to before 'million'.
 	 */
	void doMillion() {
		hundred_th_m = hundred_th;
		tens_th_m = tens_th;
		hundred_m = hundred;
		tens_m = tens;
		hundred_th = 0;
		tens_th = 0;
		hundred = 0;
		tens = 0;
	}

	long getValue() {
		return ( 
			(tens_th_m + hundred_th_m*100)*1000 +
			(tens_m + hundred_m*100) 
		) *1000000L +
		( 
			(tens_th + hundred_th*100)*1000 +
			(tens +hundred*100 ) 
		);
	}

	NumberAccumulator duplicate() {
		NumberAccumulator n = new NumberAccumulator();

		n.tens = tens;
		n.hundred = hundred;
		n.tens_th = tens_th;
		n.hundred_th = hundred_th;
		n.tens_m = tens_m;
		n.hundred_m = hundred_m;
		n.tens_th_m = tens_th_m;
		n.hundred_th_m = hundred_th_m;

		n.multiplier = multiplier;

		return n;
	}

	static long sumOver(long val ) {
		return val*(val+1)/2;
	}

	static NumberAccumulator createOnes() {
		NumberAccumulator val = new NumberAccumulator();
		val.tens = sumOver(9);

		val.multiplier = 9;
		//log.trace("Created sum over Ones with value: " + val.getValue() );
		return val;
	}

	static NumberAccumulator createTens() {
		NumberAccumulator val = new NumberAccumulator();
		val.tens = sumOver(99);

		val.multiplier = 99;
		//log.trace("Created sum over Tens with value: " + val.getValue() );
		return val;
	}

	static NumberAccumulator createHundreds() {
		NumberAccumulator val = new NumberAccumulator();
		val.tens    = 10*sumOver(99);
		val.hundred = 100*sumOver(9);

		val.multiplier = 999;
		//log.trace("Created sum over Hundreds with value: " + val.getValue() );
		return val;
	}

	static NumberAccumulator createThousands() {
		NumberAccumulator val = new NumberAccumulator();
		val.tens    = 1000*10*sumOver(99);
		val.hundred = 1000*100*sumOver(9);

		val.tens_th    = 1000*10*sumOver(99);
		val.hundred_th = 1000*100*sumOver(9);

		val.multiplier = 999999L;
		//log.trace("Created sum over Thousands with value: " + val.getValue() );
		return val;
	}


	static NumberAccumulator createByGraph( String name ) {
		assert !("Millions".equals( name ) ): "Can't handle Millions";

		if ( "Ones".equals( name) ) {
			return createOnes();
		} else if ( "Tens".equals( name) ) {
			return createTens();
		} else if ( "Hundreds".equals( name) ) {
			return createHundreds();
		} else if ( "Thousands".equals( name) ) {
			return createThousands();
		} else {
			assert false: "Unknown Graph name";
		}

		return null;
	}


	NumberAccumulator divide(long val) {
		hundred_th_m /= val;
		tens_th_m /= val;
		hundred_m /= val;
		tens_m /= val;
		hundred_th /= val;
		tens_th /= val;
		hundred /= val;
		tens /= val;

		return this;
	}

	NumberAccumulator multiply(long val) {
		hundred_th_m *= val;
		tens_th_m *= val;
		hundred_m *= val;
		tens_m *= val;
		hundred_th *= val;
		tens_th *= val;
		hundred *= val;
		tens *= val;

		return this;
	}


	NumberAccumulator add( NumberAccumulator n) {
		tens += n.tens;
		hundred += n.hundred;
		tens_th += n.tens_th;
		hundred_th += n.hundred_th;
		tens_m += n.tens_m;
		hundred_m += n.hundred_m;
		tens_th_m += n.tens_th_m;
		hundred_th_m += n.hundred_th_m;

		return this;
	}
}


/*
 * Concretization for this specific problem
 */
class NumberNode extends Node { 

	static boolean printLengths = true;

	String name;
	long value;

	long accumulatedLength = 0;
	long firstIndex = 0;
	long accumulatedPaths = 0;
	boolean doneTotals = false;

	boolean inPath = false;
	long numPaths = 1;

	NumberNode() { super(); }

	NumberNode(String name, long value ) {
		this.name = name;
		this.value = value;
	}

	void setName( String name ) {
		this.name = name;
	}


	long getAccumulatedLength() {
		return accumulatedLength;
	}

	long getAccumulatedPaths() {
		return accumulatedPaths;
	}


	boolean isEmptyLeaf() {
		return isRegularNode() && next.size() == 0 && value == 0;
	}

	boolean isEndLeaf() {
		return next.size() == 0;
	}


	boolean isModifierNode() {
		return ( 
			name.indexOf( "hundred" ) != -1 || 
			name.indexOf( "thousand" ) != -1 || 
		    name.indexOf( "million" ) != -1  
		);
	}

	boolean isPureModifierNode() {
		return ( 
			"hundred".equals( name)  || 
			"thousand".equals( name)  || 
			"million".equals( name)   
		);
	}

	public String toString() {
		String str = "";

		str += "name: " + name + "; value: " + value + "; type: " + getClass().getName() 
				+ "; prev: " + previous.size() + "; next: " + next.size();

		if ( inPath ) str += "!";
		return str;
	}

	boolean isRegularNode() {

		if ( this instanceof Graph || this instanceof EndNode ) {
			return false;
		}

		if ( isModifierNode() ) {
			return false;
		}

		return true;
	}


	boolean isUnpureRegularNode() {

		if ( this instanceof Graph || this instanceof EndNode ) {
			return false;
		}

		if ( isPureModifierNode() ) {
			return false;
		}

		return true;
	}


	protected String print( int level ) {
		return print(level, -1 );
	}

	protected String print( int level, int depth ) {
		if ( depth != -1 && level > depth ) return "";

		String out = "";
		String tabs = makeTabs( level );

		out += tabs + name + ":";

		if ( printLengths ) {
			out	+= firstIndex
				+ "," + accumulatedLength;
		} else {
			out += value;
		}
		
		out += "," + accumulatedPaths;

		if ( inPath ) out+= "!";
		out	+= "\n";

		for ( int i = 0; i < next.size(); ++ i ) {
			out += ( (NumberNode) next.get( i ) ).print( level + 1, depth);
		}

		return out;
	}


	protected String makeTabs(int level) {
		final String tabs = "    ";

		String out = "";

		for ( int i = 0; i < level; ++ i ) {
			out += tabs;
		} 

		return out;
	}

	protected int getNamelength() {
		int length = 0;
 
		if ( name != null ) {
			length = name.length();
		}

		return length;
	}

	protected void calculateTotals( ) {
		if ( doneTotals ) return;

		int length = getNamelength();

		for ( int i = 0; i < next.size(); ++ i ) {
			NumberNode node = (NumberNode) next.get( i );

			node.calculateTotals();

			accumulatedPaths  += node.getAccumulatedPaths();
			accumulatedLength += node.getAccumulatedLength();
		}		

		if ( accumulatedPaths == 0 ) accumulatedPaths = 1;

		accumulatedLength +=  length*accumulatedPaths;

		doneTotals = true;
	}


	public int compareTo( Node n) {
		NumberNode node = (NumberNode) n;

		return name.compareTo( node.name );
	}

	
	void removeGraphNodes( boolean endNodesOnly ) {
		// Eliminate any graphs in this level
		int j = 0;
		while( j < next.size() ) {
			NumberNode node = (NumberNode) next.get(j);

			boolean remove;

			if ( endNodesOnly ) {
				remove = node instanceof EndNode;
			} else {
				remove = node instanceof Graph   ||  node instanceof EndNode;
			}

			if ( remove ) {

				unlinkNext( node );


				if ( node.isFinalNode() ) {
					// Replace the final node with an empty string node
					NumberNode emptyNode = new NumberNode( "", 0 );

					//tiny hack: need to specify number of links properly
					emptyNode.accumulatedPaths = 1;

					addNext( emptyNode  );
				} else {
					// Link the next-nodes to this node
					next.addAll( node.next );

					for ( Node n: node.next ) {
						n.previous.add( this );
					}

				}
				// If node has no previous, we can get rid of it
				node.removeIfUnlinked();

				// The opened graph may contain subgraphs;
				// we need to recheck
				// NB: This shouldn't be necessary for the empty string node.
				// However, the node order is screwed up, so retest anyway to be sure.
				j = 0;
			} else {
				j++;
			}
		}
	}
	

void combineSimilarNodes(boolean forceStrictOrdering ) {

		// Run a check for names which may cause problems in the sorting order.
		// Problems occur if one word is the beginning of another word.
		// Due to sorting, these words will always be adjacent
		for ( int i = 0; i < next.size() -1 ; ++ i ) {
			boolean redo = false;

			NumberNode node1 = (NumberNode) next.get(i);
			NumberNode node2 = (NumberNode) next.get( i + 1);

			if ( node2.name.equals( node1.name ) ) {
				// The node names are identical; combine these nodes
				// Note that this will also work for empty strings, which is fine
				
				// all next nodes in second should be moved to first
				for( int k=0; k < node2.next.size(); ++k ) {
					NumberNode node3 = (NumberNode) node2.next.get(k);

					node1.addNext( node3);
				}

				unlinkNext( node2 );
				if ( node2.inPath ) node1.inPath = true;

				if ( node2.previous.size() == 0 ) {
					node2.removeNode();
				}

				node1.resetTotals();
				redo = true;				
			} else if ( forceStrictOrdering &&
				!"".equals( node1.name ) && node2.name.indexOf( node1.name ) == 0 ) {

				// Nodes containing empty strings should NOT be combined with nodes
				// containing non-empty strings.

				// We have a conflict to resolve
				// Hang the second node under the first, where the name of the second
				// node is shortened with the name of the first node.
				unlinkNext( node2 );

				if ( node2.previous.size() > 0 ) {
					node2 = node2.duplicate();
				}

				// Move the longer node under the shorter node
				node2.setName( node2.name.substring( node1.name.length() ) );
				node1.addNext( node2 );

				// Adjust the value of the second so that the sum of the
				// shorter and longer node is equal to the previous value
				// of the long node
				node2.value = node2.value - node1.value;

				node1.resetTotals();
				node2.resetTotals();
				redo = true;
			}

			if ( redo ) {
				node1.calculateTotals();

				// One node less; redo current node
				i--;
			}
		}
	}

	void getFirst( String currentPrefix ) {
		removeGraphNodes(false);

		for ( int i = 0; i < next.size(); ++ i ) {
			NumberNode node = (NumberNode) next.get(i);

			if ( node.previous.size() > 1 ) {
				unlinkNext( node );
				addNext( node.duplicate() );
			}
		}


		Collections.sort( next);

//		log.trace("===== after sort =====");
//		log.trace( print(0)  );

		combineSimilarNodes( true );


		// At this point, for the previous nodes for this, we have the
		// correct order and the correct accumulated length per node.
		// We use this to specify the first index (which corresponds to a character
		// value) of the range of a given letter in this branch.
		// This index we can then use to home in on the exact letter we want.
		createIndexes( currentPrefix );
	}


	/**
 	 * Create the indexes of the subnodes.
 	 *
 	 * Indexing starts with the index of the parents.
 	 *
 	 * If you're beyond the first level in the tree, every 
 	 * string is offset by the collected word number till now.
 	 * We need to offset the indexes by the length of the preceding
 	 * string.
 	 */
	void createIndexes( String prefix ) {

		// Note: param already contains name of current node; don't re-include it.
		int prefixLength = prefix.length();

		if ( firstIndex == 0 ) firstIndex = 1;

		long runningTotal = firstIndex;
		long numLinks = 0;
		for ( int i = 0; i < next.size(); ++ i ) {
			NumberNode node = (NumberNode) next.get(i);

			node.firstIndex = runningTotal + prefixLength*numLinks;
			runningTotal += node.accumulatedLength;
			numLinks    += node.accumulatedPaths;
		}

	}


	/**
 	 * Search in next list for the node that should contain
 	 * the given index.
 	 * 
 	 * Return the node if found, null if not found (eg. given
 	 * index value too large or <= 0.
 	 *
 	 */
	int findBranchByIndex( String prefix, long index ) {
		int prefixlength = prefix.length();

		for ( int i = 0; i < next.size(); ++ i ) {
			NumberNode node = (NumberNode) next.get(i);

			long lastindex = node.firstIndex 
					+ prefixlength*node.accumulatedPaths 
					+ node.accumulatedLength;

			if ( node.firstIndex <= index && index < lastindex ) {
				return i;
			}
		}

		return -1;
	}


	void resetTotals() {
		accumulatedLength = 0;
		accumulatedPaths = 0;
		doneTotals = false;
	}


	NumberNode duplicate() {
		return duplicate(true);
	}

	NumberNode duplicate(boolean copyPrevious) {
		NumberNode n = new NumberNode( this.name, this.value);
		n.accumulatedLength = accumulatedLength;
		n.firstIndex = firstIndex;
		n.accumulatedPaths = accumulatedPaths;
		n.doneTotals = doneTotals;
		n.inPath = inPath;

		copyLinks( n, copyPrevious );

		return n;
	}
}



public class WordNumbers {
	protected static Logger log = new Logger();

	static String[] Ones = { 
		"one", 
		"two", 
		"three", 
		"four", 
		"five", 
		"six", 
		"seven", 
		"eight", 
		"nine" 
	};

	static String[] TenRange = { 
		"ten", 
		"eleven", 
		"twelve", 
		"thirteen", 
		"fourteen", 
		"fifteen", 
		"sixteen", 
		"seventeen", 
		"eighteen", 
		"nineteen" 
	};

	static String[] Tens = { 
		"twenty", 
		"thirty", 
		"forty", 
		"fifty", 
		"sixty", 
		"seventy", 
		"eighty", 
		"ninety" 
	};


	// Following fields used to store the search results
	static String foundName = null;
	static int    foundIndex;	// Index of found letter into String of foundName

	static Graph makeOnes() {
		Graph base = new Graph( "Ones" );

		for( int i = 0; i < Ones.length; ++i) {
			Node node = new NumberNode( Ones[i], i+1 );

			base.addNext( node, true );
		}

		base.value = 9L*10/2;
		base.numPaths = 9;

		return base;
	}


	static Graph makeTens() {
		Graph graph = new Graph( "Tens");
		Graph firstOnes = makeOnes();
		graph.addNext( firstOnes, false );
		firstOnes.last.addNext( graph.last );


		for( int i = 0; i < TenRange.length; ++i) {
			Node node = new NumberNode( TenRange[i], i+10 );

			graph.addNext(node, true);
		}

		Graph nextOnes = makeOnes();
		// End of this graph coincides with end of encompassing graph
		// we let last node of this instance point to end of Tens graph
		// and clean up later.
		nextOnes.last.addNext( graph.last );

		for( int i = 0; i < Tens.length; ++i) {
			Node node = new NumberNode( Tens[i], (i+2)*10 );
			node.addNext( nextOnes );

			graph.addNext( node, true );
		}

		graph.value = 99L*100/2;
		graph.numPaths = 99;

		return graph;
	}


	static Graph makeHundreds() {
		Graph graph = new Graph( "Hundreds" );

		Graph firstTens = makeTens();
		graph.addNext( firstTens, false );
		firstTens.last.addNext( graph.last );


		Graph nextTens = makeTens();
		nextTens.last.addNext( graph.last );

		NumberNode hundreds = new NumberNode( "hundred", 0);
		hundreds.addNext( graph.last );
		hundreds.addNext( nextTens );

		Graph ones = makeOnes();
		ones.last.addNext( hundreds );
		graph.addNext( ones, false );

		graph.value = 999L*1000/2;
		graph.numPaths = 999;

		return graph;
	}


	static Graph makeThousands() {
		Graph graph = new Graph( "Thousands" );

		Graph firstHundreds = makeHundreds();
		graph.addNext( firstHundreds, false );
		firstHundreds.last.addNext( graph.last );

		Graph nextHundreds = makeHundreds();
		nextHundreds.last.addNext( graph.last );

		NumberNode thousands = new NumberNode( "thousand", 0);
		thousands.addNext( graph.last );
		thousands.addNext( nextHundreds );
		firstHundreds.last.addNext( thousands );

		graph.value = 999999L*1000000L/2;
		graph.numPaths = 999999;

		return graph;
	}


	static Graph makeMillions() {
		Graph graph = new Graph( "Millions" );

		Graph firstThousands = makeThousands();
		graph.addNext( firstThousands, false );
		firstThousands.last.addNext( graph.last );

		Graph nextThousands = makeThousands();
		nextThousands.last.addNext( graph.last );

		NumberNode million = new NumberNode( "million", 0);
		million.addNext( graph.last );
		million.addNext( nextThousands );

		Graph firstHundreds = makeHundreds();
		graph.addNext( firstHundreds, false );
		firstHundreds.last.addNext( million );

		graph.value = 999999999L*1000000000L/2;
		graph.numPaths = 999999999;

		return graph;
	}


	void findNumber( long searchIndex, Graph graph) {
		graph.calculateTotals();

		String nameTillNow = "";
		NumberNode node = graph;

		while ( node.next.size()  > 0 ) {
			node.getFirst( nameTillNow );
			log.trace("===== after getFirst =====");
			log.trace( node.print(0, 2)  );


			// Mark the correct route for further processing
			int index = node.findBranchByIndex( nameTillNow, searchIndex );	
			NumberNode found = (NumberNode) node.next.get(index);
			found.inPath = true;

			// Create copies of all next-nodes for this node
			found.removeGraphNodes( false );
			for ( int j =0; j < found.next.size(); ++j ) {
				NumberNode n = (NumberNode) found.next.get(j);

				if ( n.previous.size() > 1 ) {
					log.trace("Old node: " + n.toString() );
					NumberNode newNode = n.duplicate( false );
					log.trace("New node: " + newNode.name );
					newNode.previous.add( found );
					found.next.setElementAt( newNode, j );
				} 
			}
			// Remove anything at this level beyond this node
			index = node.findBranchByIndex( nameTillNow, searchIndex );
			if ( index != -1 ) {
				while( index + 1 < node.next.size() ) {
					Node n = node.next.get(index + 1);
					node.unlinkNext(n);
				}
			}
			node = (NumberNode) node.next.get(index);

			nameTillNow += node.name;

			log.trace( "Name till now: " + nameTillNow );
			log.trace( "looking for index: " + searchIndex );
			log.trace("===== At end of loop =====");
			log.trace( node.print(0, 2)  );
		}


		if ( node.next.size() == 0 ) {
			// We must have found the node now; Store for later display
			foundIndex = (int) ( searchIndex - node.firstIndex );
			foundName  = nameTillNow;

			if ( Logger.enableTraces ) {
				log.out ( "----------------" );
				displayFoundNumber();
			}
		}	 
	}


	static void displayFoundNumber() {
		// Determine the exact letter found
		String letter = foundName.substring( foundIndex, foundIndex + 1);
		log.out ( "The letter is: " + letter );
		log.out ( "It is in position " + (foundIndex + 1) + " in the following string: " );
		log.out ( foundName );
		log.out ( "...which has length: " + foundName.length() );
	}


	static boolean combineRegularNodes( NumberNode graph ) {

		log.trace("=== Entered combineRegularNodes() ===");

		boolean changed = false;

		for ( int i = 0; i < graph.next.size(); ++ i ) {
			NumberNode node1 = (NumberNode) graph.next.get(i);

			node1.removeGraphNodes( true );
	
			if ( !node1.isRegularNode() ) {
				log.trace( "Node '" + node1.name + "' not regular.");
				continue;
			}
		
			for ( int j = 0; j < node1.next.size(); ++j ) {
				NumberNode node2 = (NumberNode) node1.next.get(j);

				// Combine nodes with regular values
				if ( node2.isRegularNode() && node2.value != 0 ) {
					//Combine the values
					node1.unlinkNext( node2 );
				
					if ( node2.previous.size() > 0 ) {
						node2 = node2.duplicate();
					}

					node2.name = node1.name + node2.name;
					node2.value += node1.value;
					log.trace( node2.toString() );

					if ( node2.inPath ) {
						node1.inPath = false;
					}

					graph.addNext( node2 );
					j--;
					changed = true;
					continue;
				}
			}
		}

		if ( changed ) {
			Collections.sort( graph.next);
			graph.combineSimilarNodes( false );
		}

		return changed;
	}

	static long calculateSum( NumberNode graph, NumberAccumulator prevAcc, 
		int level, int max) {
		return calculateSum( graph, prevAcc, level, max, false );
	}
 
	static long calculateSum( NumberNode graph, NumberAccumulator prevAcc, 
		int level, int max, boolean modifierOnly ) {

		long sum = 0L;

		if ( prevAcc == null ) prevAcc = new NumberAccumulator();
		NumberAccumulator numberAcc =  prevAcc.duplicate();


		// Apply value of current node.
		if ( "hundred".equals( graph.name ) ) {
			numberAcc.doHundred();
		} else if ( "thousand".equals( graph.name ) ) {
			numberAcc.doThousand();
		} else if ( "million".equals( graph.name ) ) {
			numberAcc.doMillion();
		} 

		if ( graph.isEndLeaf() ) {
			return numberAcc.getValue();
		}

		long sumBefore = sum;

		if ( level != 0 && (graph instanceof Graph) ) {
			Graph g = (Graph) graph;

			NumberAccumulator sumGraph = NumberAccumulator.createByGraph( g.name );

			if ( !modifierOnly ) {
				long accSum = calculateSum( g.last, sumGraph, level + 1, max, true );

				sum += numberAcc.multiplier*accSum;
				//log.trace("accSum: " + accSum);
			}

			long tmpSum = calculateSum( g.last, numberAcc , level + 1, max, modifierOnly );
			//log.trace("tmpSum: " + tmpSum );
			sum += sumGraph.multiplier*tmpSum;
		
		} else {
			if ( ! modifierOnly ) {	
				numberAcc.addValue( graph.value );
			}

			for ( int i = 0; i < graph.next.size(); ++i ) {
				NumberNode n = (NumberNode) graph.next.get(i);
				sum += calculateSum( n, numberAcc , level + 1, max, modifierOnly );
			}
		}


/*
 		// Debug code: show info and pause
		if ( !(graph instanceof EndNode ) ) {
			log.out("=== calculateSum === ");
			log.out( graph.print(0,1) );
			log.out("Level: " + level);
			log.out( "modifierOnly: " + modifierOnly );
			log.out("sum before: " + sumBefore );
			log.out("sum: " + sum );
			log.out("Value:" + numberAcc.getValue() );
			log.out("Waiting for input:");
			try {
				System.in.read();
			} catch( Exception e ) {
				log.out("Exception caught");
			}
		}
*/
		return sum; 
	}


	static void makeHundredNodes(NumberNode node ) {
		log.trace("makingHundreds: " + node.name );
		log.trace( node.print(0,1) );

		if ( node.isEmptyLeaf() ) return;

		while( combineRegularNodes( node ) );

		log.trace("=== After combineRegularNodes() === ");
		log.trace( node.print(0,1) );

		makeHundredNodes( getFoundNode( node ) );
	}


	static NumberNode getFoundNode( NumberNode node ) {
		for ( int i = 0; i < node.next.size(); ++ i ) {
			NumberNode node1 = (NumberNode) node.next.get(i);

			if ( node1.inPath ) return node1;
		}
		log.trace("next not found!");
		return null;	
	}


	public static void main( String[] arg) {
		// Enable debug output here
		Logger.displayTraces(false);

		WordNumbers obj = new WordNumbers();

		long searchIndex = 51000000000L;

		Graph graph = makeMillions();
		long expected = graph.value; 

		obj.findNumber(searchIndex, graph);
		log.trace( "=== Found the number ===" );

		//Search part
		NumberNode.printLengths = false;
		graph.value = 0;

		makeHundredNodes(graph);

		log.trace("=== After makeHundredNodes() ===");
		log.trace( graph.print(0,2) );

		long sum = calculateSum( graph, null, 0, 0 );

		//log.trace( "=== After calculateSum ===");
		//log.trace( graph.print(0,3) );
		log.trace("The sum is:                " + sum);
		log.trace( graph.name + " total should be : " + expected );
		log.trace( "=== done ===" );
	
		obj.displayFoundNumber();

		log.out(   "The sum up to and including this number is: " + sum);
		log.trace( "We were expecting:                          413540008163475743" );

	}
}