31598번 - Forming Groups 다국어

문제

There are $n$ students, numbered from 1ドル$ to $n,ドル who need to form groups for the upcoming hackathon. You are student 1ドル,ドル the captain of the students. Student $i$ has skill level $a_i$.

Students 2ドル$ to $n$ are standing in a line from left to right in order. You can choose to stand in between any two students, to the left of student 2ドル,ドル or to the right of student $n$. You cannot change the order of the $n - 1$ students.

You can also choose the number of groups $k$ ($k > 1$ and $k$ must be a divisor of $n$) to participate in the hackathon. The groups will be numbered from 1ドル$ to $k$. After you have chosen your position and the value of $k,ドル the students will be grouped as follows:

• The first student from the left will be assigned to group 1ドル$.
• The second student from the left will be assigned to group 2ドル$.
• $\dots$
• The $k$-th student from the left will be assigned to group $k$.
• The $(k + 1)$-th student from the left will be assigned to group 1ドル$.
• The $(k + 2)$-th student from the left will be assigned to group 2ドル$.
• $\dots$
• The $n$-th student from the left will be assigned to group $k$.

Formally, for each $j$ (1ドル ≤ j ≤ k$) and for each $i$ (0ドル ≤ i < n/k$), the $(i \times k +j)$-th student from the left will be assigned to group $j$. It can be shown that each student will be assigned to exactly one group and all the groups have the same number of students.

The skill level of a group is the sum of the skill levels of the students inside the group. By choosing where you stand as well as the number of groups $k$ optimally, you want to minimize the ratio $x_\max/x_\min$ where

• $x_\max$ is the skill level of the group with the largest skill level, and
• $x_\min$ is the skill level of the group with the smallest skill level.

입력

The first line of input contains one integer $t$ (1ドル ≤ t ≤ 100,円 000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line of a test case contains two integers $n$ and $a_1$ (2ドル ≤ n ≤ 10^6$; 1ドル ≤ a_1 ≤ 1000$). The next line contains $n - 1$ integers $a_2, a_3, \dots , a_n$ (1ドル ≤ a_i ≤ 1000$ for all $i$).

The sum of $n$ across all test cases in one input file does not exceed 10ドル^6$.

출력

For each test case, output one line containing two positive integers $p$ and $q$ such that the minimum ratio is $p/q$. The fraction $p/q$ should be irreducible. In other words, $p$ and $q$ should be coprime.

제한

힌트