Points and Lines

Parse an expression of points and lines joined by @, evaluate geometric operations, and print the resulting point rounded to 8 decimals.

Medium6ImplementationMathGeometryNo attempts yetTime limit8sMemory limit512 MB

Problem

One day you found an old scroll covered with strange text.

The text is an expression that gives the position of a treasure. The expression is built from three operations.

  • From two points, it yields the line that passes through both points.
  • From a point and a line, it yields the point symmetric to that point with respect to the line.
  • From two lines, it yields the point where the two lines cross.

The syntax of the expression is given by the following BNF.

<expression>      ::= <point>
<point>           ::= <point-factor> | <line> "@" <line-factor> | <line> "@" <point-factor> | <point> "@" <line-factor>
<point-factor>    ::= "(" <number> "," <number> ")" | "(" <point> ")"
<line>            ::= <line-factor> | <point> "@" <point-factor>
<line-factor>     ::= "(" <line> ")"
<number>          ::= <zero-digit> | <positive-number> | <negative-number>
<positive-number> ::= <nonzero-digit> | <positive-number> <digit>
<negative-number> ::= "-" <positive-number>
<digit>           ::= <zero-digit> | <nonzero-digit>
<zero-digit>      ::= "0"
<nonzero-digit>   ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Each <point> and <point-factor> denotes a point, and each <line> and <line-factor> denotes a line. A <point-factor> of the form (X,Y) is the point whose x coordinate is X and whose y coordinate is Y on the plane. The character @ applies an operation to its two operands. The three operations are told apart by whether each operand is a point or a line, so all of them are written with the same character @. As the grammar shows, @ is left associative.

Find the position of the treasure.

Input

The input consists of several datasets. Each dataset is one line that holds one expression denoting the position of the treasure.

Each dataset satisfies the following conditions.

  • The length of the line is at most 10210^2.
  • If both operands of an @ are points, the distance between the two points is greater than 1.
  • If both operands of an @ are lines, the two lines are not parallel.
  • At every step of the evaluation, the absolute value of each coordinate of every point is at most 10210^2.

There are at most 100 datasets. The last line of the input holds a single #, and that line is not a dataset.

Output

For each dataset, print on one line the x coordinate and the y coordinate of the point denoted by the expression, in this order, separated by a single space.

Print each coordinate rounded to 8 digits after the decimal point. When a coordinate is zero, print 0.00000000 and not -0.00000000.