Tree Search
---- ------

Trax and Jax live in the tunnels inside the planet Pax.
There are a lot of tunnels.  But there is only one
path through the tunnels from any point to any other
point (no running around in circles possible).

Trax needs to locate Jax, and fortunately she has a
locator device that can help.  The device, however, does
not simply tell Trax where Jax is.  Instead Trax can
suggest to the device a possible location for Jax, and
the device will tell her whether Jax is there and if
not, which direction from the suggested location Jax is.

Unfortunately the locator device uses a lot of power
for each response, and can only answer a few queries.

In this problem you write a program that talks to the
locator device until you suggest the location where
Jax is or run out of power.

Your Input/Output
---- ------------

You write the program whose binary name is `treesearch'.
The locator is implemented by a separate program whose
name is `locator'.  The `locator' program runs your
`treesearch' program as a subprocess.  The command that
does this is

  locator [-trace] treesearch ... <TEST-CASE-INPUT

where ... are arguments passed to treesearch (only used
for debugging).  You write queries to your standard
output.  The locator program reads these and writes a
response so that you can read it from your standard
input.  The locator also gives you a tunnel map which
you read from your standard input at the very beginning
before any queries.

Note that YOUR program DOES NOT READ the test case input
or write the test case output.  The `locator' program
does this.

The tunnel map is a description of the tunnels viewed
as a computer science tree with you at the root.  The
syntax is

	tree ::= () | (tree-list)
	tree-list ::= tree | tree tree-list

Here () represents a tree leaf with no children and
(tree-list) is a tree whose children are the trees
listed in tree-list.  For example,

    (()(()())) represents:    ((()())()) represents:

	      *			        *
	     / \                       / \
	    *   *                     *   *
	       / \		     / \
	      *   *		    *   *

In order to identify tree nodes we number them in
the order that their `('s occur in the tree map.  Thus

    (()(()())) represents:    ((()())()) represents:

	      1			        1
	     / \                       / \
	    2   3                     2   5
	       / \		     / \
	      4   5		    3   4

The locator begins by writing the tree map to your
standard input.  You may then make queries.

To make a query you output the number S of the tree node
you are suggesting on a single line.  The response is
a single line that you can read which contains one of
the following:

  * just `FOUND' if Jax is at the suggested node
  * just `POWER' if the locator has run out of power
    and you have failed to locate Jax (and your
    submission will be rejected)
  * the number R of another tree node such that S and R
    are directly connected by a single tunnel and R is
    closer to Jax than S is; here distance between nodes
    is the number of tunnels needed to get from one node
    to the other node

If the tunnel map has N nodes, you are allowed Q queries
before power runs out, where

	2 <= N <= 1,000,000

	Q = 1 + ceiling of log base 2 of N

All lines input to your program will have at most 80
characters, except the line containing the tunnel_map,
which has 2*N characters.  All query lines output from
your program must have less than 80 characters.


WARNING
-------

If you use printf in C or C++ you must use fflush after
printing a line, as in

	printf ( "...\n", ... );
	fflush (stdout);

Similarly if you use `print' in python you must flush
after printing a line, as in

	print ( '....' )
	sys.stdout.flush()

Otherwise your output will be trapped in a buffer and
never get to the locator program.  The C++ `endl' IO
manipulator and JAVA `println' functions flush this
buffer, so if you are using these functions nothing
special needs to be done.

Debugging
---------

If you specify -trace in the command that runs your
treesearch program, your program will be run in trace
mode.

In trace mode the locator outputs to its standard output
(not your program) the lines it reads from your program,
prefaced by `<< ', and the lines it writes to your
program, prefaced by '>> '.  In trace mode, any line
output by your program that begins with a `*' will be
traced but otherwise ignored.  You can use such lines
for debugging output, and you can use arguments passed
to your program to tell your program to output these
lines.

The input tree, if not very large, may be printed or
displayed in an X-window by the commands:

	print_tree sample.in
	display_tree sample.in

You can replace `sample.in' by another locator input
file.  Jax's location is marked by a `*'.


Test Case Descriptions And Output
---- ---- ------------ --- ------

In the test environment, the locator (and not your
program) reads test case descriptions from its standard
input and the locator (and not your program) writes test
case output to its standard output.

Each test case description has two lines.  First a line
containing just the test case name.  Then a line
containing

	N SEED

where N is the number of tree nodes and SEED is an
unsigned integer used to seed a pseudo-random number
generator that generates the tunnel map.  SEED
is 9 digits long: 10**8 <= SEED < 10**9.

The test case output written by the locator to its
standard output (not your program) consists of
first a line copying the test case name input line,
then any trace output, and finally a single line
containing either just `FOUND' or `POWER'.


Sample Input
------ -----

-- SAMPLE 1 --
11 785983564
-- SAMPLE 2 --
35 352401876


Sample Output
------ ------

-- SAMPLE 1 --
FOUND
-- SAMPLE 2 --
FOUND


Sample Output in Trace Mode (with -trace)
------ ------ -- ----- ---- ----- -------

-- SAMPLE 1 --
>> (()((())())((()(()))))
<< 1
>> 7
<< 8
>> FOUND
FOUND
-- SAMPLE 2 --
>> ((((((())...rest omitted, see sample.trace
<< 8
>> 5
<< 26
>> 27
<< 28
>> FOUND
FOUND


File:	   treesearch.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Tue Oct 15 14:04:42 EDT 2019

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.