30855번 - Fraction 다국어

문제

A basic fraction can be represented by three integers $(a,円 b,円 c)$ which denotes $a + \frac{b}{c}$ where 1ドル ≤ a, b, c ≤ 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 $\left((1,円 2,円 4)(5,円 2,円 3)\left(4,円 3 (2,円 7,円 3) \right)\right)$ is as follows.

$$\left(1 + \frac{2}{4}\right) + \displaystyle\frac{5 + \displaystyle\frac{2}{3}}{4 + \displaystyle\frac{3}{2 + \displaystyle\frac{7}{3}}} = \displaystyle\frac{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ドル ≤ n ≤ 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.

제한

힌트