katappas-strategy

Katappa killed Bahubali because he failed in maths exam every time, and Bahubali was the king of the state. So he killed him and redefined all mathematical equations. According to Katappa sum of two fractions w/x and y/z is (w/x)+(y/z)={(w+y)/(x+z)}. So now the problem is, given are N fractions, find the maximum fraction you can obtain by adding N fractions starting from a position ‘i’, where ‘i’ gets incremented each time.

Input : 
The first line contains T the number of test cases. Next line of the test case will contain N denoting the number of fractions. Next N lines contains values in “x/y” form . A ‘\n’ will separate the next test case.
Output :
N lines for each test cases, each line displays a fraction which denotes the maximum value starting from the “i”th position. Fraction should be in the simplified form. Insert a newline after after finishing each of the test case.

Constraints:
1 ≤ Test cases T ≤ 5
1 ≤ N ≤ 10^5
1 ≤ x, y ≤ 10^5

Sample Input :
2
4
3/2
2/1
5/2
3/1
3
2/3
3/1
4/2

Sample Output :
13/6
5/2
8/3
3/1

3/2
3/1
2/1

Explanation:
Test case 1:
Starting from position 1.
3/2, 
3/2 + 2/1 =5/3, 
3/2+2/1+5/2=2/1
3/2+2/1+5/2+3/1=13/6 out of all the values 13/6 is the maximum
Increment “i”. Position 2.
2/1,
2/1+5/2=7/3
2/1+5/2+3/1=5/2 (5/2 is the highest value among the three.
Position 3.
5/2,
5/2+3/1=8/3 (8/3 is the highest value among the two)
Position 4
3/1, (only one value, so its the highest)

Test case 2:
 
i=1,
2/3,
2/3+3/1=5/4
2/3+3/1+4/2=3/2 (this the highest among all)
i=2,
3/1,
3/1+4/2=7/3 (3/1 is the highest among the two)
i=3,
4/2 (=2/1 only one value, hence it’s the highest)

SAMPLE INPUT
2
4
3/2
2/1
5/2
3/1
3
2/3
3/1
4/2

SAMPLE OUTPUT
13/6
5/2
8/3
3/1

3/2
3/1
2/1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: