Mining Plan Priority

The mining area is divided into several development regions. In each development region, the mineral quantity is proportional to the square of its area. More precisely, if a region has area \(s\), then its mineral quantity is \(s^2\).

There are m mining plans. Each plan specifies a set of development regions (by giving an encrypted polygon boundary – which uniquely determines the set of regions) but for the purpose of this problem the plan input is given as a list of areas of the regions it covers. The priority of a mining plan is defined as:

Priority = \(\frac{\sum_{i=1}^{k} s_i^2}{\sum_{i=1}^{k} s_i}\)

Your task is to compute the priority of each mining plan and output it as a reduced fraction. That is, if the total mineral quantity is \(\text{num}\) and the total area is \(\text{den}\) and they share a common factor, you must cancel it so that the numerator and denominator are coprime (e.g. if the sum of region areas is 2 and the mineral sum is 1.5, you should output 3 4; if the sums are 2 and 4, output 1 2).

There is one more twist: for security reasons, you must process the mining plans in order. The input for every mining plan after the first is encrypted. Specifically, for the first mining plan the numbers are given in plain text. For each subsequent plan, each integer (both the count and the region areas) is increased by an offset D, where D is defined as the sum of the numerator and denominator (i.e. A+B) of the previous plan's answer. You must subtract D from every integer to recover the actual values.

Input Summary:

• The first line contains an integer m, the number of mining plans.
• For each mining plan:
• The first line contains an integer k, the number of development regions in the plan. (Encrypted for all but the first plan.)
• The second line contains k space-separated integers representing the areas of the development regions. (Encrypted for all but the first plan.)

Output Summary:

• For each mining plan, output a line with two integers: the numerator and denominator of the plan's priority in simplest form.

inputFormat

The input begins with an integer m representing the number of mining plans. Then for each mining plan:

1. An integer k indicating the number of development regions. (For the first plan, k is given as is; for every subsequent plan, the given integer is k + D, where D is the offset from the previous plan's answer.)
2. A line with k space-separated integers representing the areas of these regions. (For subsequent plans each area is given as area + D.)

You must decode the encrypted values (by subtracting the offset D from each integer) before computing the answer for that plan. For the first plan, D is 0.

Example: Suppose the first mining plan is not encrypted and has:

2
3 5

Then its total area is 8 and the mineral quantity is 9+25 = 34, so the priority is \(34/8\) which simplifies to \(17/4\). The offset for the next plan is then D = 17 + 4 = 21.

outputFormat

For each mining plan output a line with two integers separated by a space: the numerator and denominator of the mining plan's priority in its simplest form.

Example Output:

17 4
17 7
10 1

sample

3
2
3 5
24
23 23 24
25
34

17 4
17 7
10 1

</p>