Optimal Triangulation
------- -------------

A triangulation of a polygon is a division of the area
of the polygon into disjoint triangles whose vertices
are vertices of the polygon.  Given an assignment of
values to triangles, an optimal triangulation is a
triangulation for which the sum of the values of the
triangles is maximal. 

You have been asked to find optimal triangulations of
convex polygons.  The triangle value function is repre-
sented in fully parenthesized prefix operator notation
using the components:

    a, b, c	The sizes in degrees of the angles of
    		the triangle.
    A, B, C	The lengths of the sides of the tri-
    		angle.  Side A is opposite angle a,
		side B opposite angle b, side C opposite
		angle c.
    +		Sum of arguments.
    *		Product of arguments.
    -		If one argument, the negative of that,
    		and if two arguments, the first minus
		the second.  Illegal for more than two
		arguments.
    ^		Maximum of arguments.  (circumflex)
    v		Minimum of arguments.  (letter v)

There is no whitespace in a function representation; for
example, (+abc) denotes the sum of angles of a triangle
(which always equals 180).  A `(' is always followed by
an operator, i.e., by `+', `*', `-', `^', or `v'.  An
operator is always preceded by a `('.  Operators always
have at least 2 arguments, except `-' which can have
one argument.  Functions can return negative values.

The value function is required to be symmetric under
permutation of the angles of a triangle, with sides
being changed in corresponding fashion.  For example,

		(v(*aBC)(*bCA)(*cAB))

is symmetric, but (+ab) is not.

You are to represent a triangulation as a list of vertex
triples, one for each triangle, giving the vertices of
the triangle.  If there are N polygon vertices, there
will be N-2 triangles.


Input
-----

For each of several test cases, a line containing just
the test case name, followed by a line containing the
triangle valuation function, followed by a lines con-
taining the following numbers

	N x[1] y[1] x[2] y[2] ... x[N] y[N]

where N is the number of vertices of the convex polygon
and the vertices in counter-clockwise order are
(x[1],y[1]), (x[2],y[2]), ..., (x[N],y[N]).  These
numbers are separated by spaces and new lines.  The x
and y coordinates are floating point numbers in the
range [-1000,1000].  The polygons are guaranteed to be
convex, without any 3 vertices being on a straight line.

3 <= N <= 100.  Lines will have no more than 80
characters.  Input ends with an end of file.


Output
------

For each test case, a line that is an exact copy of the
test case name input line, followed by N-2 lines each
with the format

	i j k

specifying the triangle whose vertices are

	(x[i],y[i])	(x[j],y[j])	(x[k],y[k])

These triangles give the desired triangulation whose
sum of triangle values is maximal.  The input will be
such that this triangulation is unique.



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

-- SAMPLE 1 --
(^abc)
4 0 0 1 0 1 2 0 1
-- SAMPLE 2 --
(vabc)
4 0 0 1 0 1 2 0 1

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

-- SAMPLE 1 --
1 3 4
1 2 3
-- SAMPLE 2 --
1 2 4
2 3 4


File:	   opttriangulation.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Tue Oct 11 08:08:21 EDT 2011

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

RCS Info (may not be true date or author):

    $Author: walton $
    $Date: 2011/10/11 12:08:34 $
    $RCSfile: opttriangulation.txt,v $
    $Revision: 1.7 $