31292번 - Compare Continued Fractions 다국어

문제

In this problem, you have to compare two rational numbers represented by their continued fractions.

A finite continued fraction is a sequence $[a_{0}; a_{1}, a_{2}, \ldots, a_{n}]$. The following restrictions are applied:

• $n$ is a non-negative finite integer,
• the elements $a_{0},ドル $a_{1},ドル $a_{2},ドル $\ldots,ドル $a_{n}$ are integers,
• $a_{i} > 0$ for each $i > 0,ドル
• $a_{n} > 1$ if $n > 0$.

These restrictions allow to establish a one-to-one correspondence between rational numbers and finite continued fractions: every rational number $x$ corresponds to the unique continued fraction $[a_{0}; a_{1}, a_{2}, \ldots, a_{n}]$ such that $$x = a_{0} + \frac {1} {a_{1} + \frac {1} {a_{2} + \frac {1} {\ddots + \frac {1} {a_{n}}}}}\text{.}$$ Thus, the following notation is used: $x = [a_{0}; a_{1}, a_{2}, \ldots, a_{n}]$. For example, $$\frac {17} {25} = 0 + \frac {1} {\frac {25} {17}} = 0 + \frac {1} {1 + \frac {8} {17}} = 0 + \frac {1} {1 + \frac {1} {\frac {17} {8}}} = \mathbf{0} + \frac {1} {\mathbf{1} + \frac {1} {\mathbf{2} + \frac {1} {\mathbf{8}}}}\text{,}$$ so we write $\frac {17} {25} = [0; 1, 2, 8]$.

Given the continued fractions for two rational numbers $x$ and $y,ドル find whether $x < y,ドル $x = y,ドル or $x > y$.

입력

The input consists of two lines. The first line contains the continued fraction for the rational number $x$. The second line contains the continued fraction for the rational number $y$.

Each continued fraction is given as a sequence of integers separated by single spaces. First goes an integer $n,ドル the length of the continued fraction (0ドル \le n \le 100,000円$). It is followed by $(n + 1)$ integers which are the elements of the continued fraction: $a_{0},ドル $a_{1},ドル $a_{2},ドル $\ldots,ドル $a_{n}$ ($|a_{i}| \le 10^{9}$). It is guaranteed that $a_{i} > 0$ for each $i > 0$ and $a_{n} > 1$ if $n > 0$.

출력

On the first line of output, print a single character: "<" if $x < y,ドル "=" if $x = y,ドル or ">" if $x > y$.

제한

힌트