题目描述

A basic fraction can be represented by three integers $(a,b,c)$ which denotes $a+\dfrac{b}{c}$ where $1\le a,b,c\le 9$. An extended fraction has the form of $(a',b',c')$ where $a'$, $b'$ and $c'$ may be integers between one and nine or other extended fractions. Note that a basic fraction is also an extended fraction, and the length of the fraction is finite.

Given an extended fraction, we want to express its value as irreducible fraction. For example, the irreducible fraction of $((1\ 2\ 4)(5\ 2\ 3)(4\ 3\ (2\ 7\ 3)))$ is as follows.

$$\left(1+\dfrac{2}{4}\right)+\cfrac{5+\cfrac2 3}{4+\cfrac 3{2+\cfrac 7 3}}=\dfrac {991} {366} $$

Given a string form of an extended fraction, write a program that converts the extended fraction into the irreducible fraction.

输入格式

Your program is to read from standard input. The input starts with a line containing one integer $n$ ($2 \le n\le 100$), where $n$ is the number of symbols which are parentheses and digits between $1$ and $9$. The second line contains symbols, separated by a space, which represent an extended fraction.

输出格式

Your program is to write to standard output. Print exactly one line. If the answer is $x/y$ the line should contain two integers $x$ and $y$, which are relatively prime to each other. Otherwise, (for example, when the input is not valid) print -1. You will need 64-bit integers to get the correct answer.

5
( 1 2 3 )

5 3

8
( 1 2 ( 3 4 5 )

-1

21
( ( 1 2 4 ) ( 5 2 3 ) ( 4 3 ( 2 7 3 ) ) )

991 366