C. Chained Training
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

After retiring from competitive programming, May decided to become a Pokémon trainer. She has $$$N$$$ Pokémon, and each Pokémon is described by three values: defense ($$$d$$$), health ($$$h$$$), and attack ($$$a$$$).

May is creating a training plan called Chained Training. Her Pokémon are arranged in a line, and the Pokémon at index $$$i$$$ can only fight a Pokémon at index $$$j$$$ such that $$$j \lt i$$$.

When Pokémon $$$i$$$ battles Pokémon $$$j$$$, Pokémon $$$i$$$ gains experience according to the following formula:

$$$$$$ \text{experience}(i, j) = d_j \cdot a_i + \frac{h_j}{d_i} $$$$$$

May has a gym battle soon, so she wants her Pokémon to gain as much experience as possible by fighting against a single Pokémon. For each Pokémon, determine the maximum amount of experience it can gain if she chooses its rival optimally.

Input

The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$) — the number of Pokémon.

The next $$$N$$$ lines each contain three integers $$$d_i$$$, $$$h_i$$$, and $$$a_i$$$ ($$$1 \leq d_i, h_i, a_i \leq 10^6$$$) — the defense, health, and attack of the $$$i$$$-th Pokémon.

Output

Print $$$N$$$ lines. For each Pokémon $$$i$$$, output two integers — the numerator and denominator of the irreducible fraction representing the maximum experience that the $$$i$$$-th Pokémon can gain.

Examples
Input
5
4 3 17
5 2 5
4 1 30
1 2 2
8 1 10
Output
0 1
103 5
301 2
12 1
201 4
Input
5
1 2 10
3 3 21
8 2 34
1 1 16
4 2 53
Output
0 1
65 3
819 8
130 1
849 2
Input
1
1 2 3
Output
0 1