-235. Pachinko

Task Description

Write a program to simulate a Pachinko. For this problem, we will use a very simple pachinko. There are $N$ rows of pins in this pachinko. The $i$-th pin of a row is between the $i$-th and $(i-1)$-th pin in the previous row, as shown in the figure below. When a ball drops on a pin, it will go either left or right. This probability varies from pin to pin. After hitting $N$ pins, the ball will fall into one of the $N + 1$ buckets. After knowing the probability of going left or right for every pin, compute the probability that a ball falls into each $N + 1$ bucket.

• The number of rows of pins $N$ is less than or equal to $15$.

p235.jpg

Input

The first line of the input has the number of rows $N$. The next $N(N+1)/2$ line has two integers $a$, $b$, that indicate the ratio of the probability that the ball will go left or right. The probability ratio is given from top to bottom, from left to right. $a, b \ge 0$, and it is guaranteed that one of $a, b > 0$.

Output

Please output $N + 1$ lines -- each has a fractional number. The $i$-line has the probability of the ball falling into the $i$-th bucket. Each line has a ratio of $q/p$ to indicate the probability. You need to simplify the $q/p$ ratio; you should output $1/2$ instead of $2/4$.

Sample input

2
1 2
2 3
3 1

Sample output

2/15
7/10
1/6

Hint

In order to prevent arithmetic overflow, you should reduce the denominator and numerator of each fractional number you use.