Problem Description

In front of you there is a row of $n$ piles of coins in a line. Coins in the same pile have the same face value; denote the face value of the $i$-th pile by $a_i$. The number of coins in each pile is the same, denoted by $x$.

Now you are given the face value $a_i$ of each pile. You need to determine a positive integer $x$ such that the variance of the total amount of money in each pile is closest to a positive integer $k$.

Definition of “closest” between two numbers: the absolute value of their difference is minimal.

Variance definition: $s ^ 2 = \cfrac{(a_1 - \bar x)^2 + (a_2 - \bar x) ^ 2 + \cdots + (a_n - \bar x) ^ 2}{n}$, where $\bar x$ represents the average of $x$.

Input Format

The first line contains two integers $n,k$.

The second line contains $n$ integers. The $i$-th integer is $a_i$, meaning the face value of the $i$-th pile is $a_i$.

Output Format

Output one positive integer on one line, representing the value of $x$ that satisfies the requirement. If there are multiple answers, output the smallest one. If no matter what value $x$ takes the variance is always $0$, output one line No answer!.

7 47
7 2 4 6 3 7 10

3

4 4
4 4 4 4

No answer!

Hint

[Sample $\#1$ Explanation]

When $x=3$, the amount of money in the $i$-th pile is $3\times a_i$. These amounts are $21,6,12,18,9,21,30$. The variance of these amounts is approximately $58.78$. It can be proven that when $x=3$, the variance is closest to $47$.

[Sample $\#2$ Explanation]

It can be found that no matter what value $x$ takes, the variance will be $0$, so output No answer!.

[Constraints]

This problem uses bundled Subtask testdata.

For $100\%$ of the testdata, $1\le n,\forall a_i\le7\times10^6$, $1\le k\le3\times10^{18}$. Let the variance of the original array $a$ be $p$. Then the testdata satisfies $p=0$ or $p\in[0.25,\ 2^{63}-1]$.

[Hint]

The input size of this problem is large. Please use a suitable input method. Here we recommend a fast input template. For $\texttt{C/C++}$, you can also use scanf to read input.

To avoid precision issues, $\texttt{C/C++}$ users are advised to use type $\texttt{double}$, and it is not recommended to use eps.

Translated by ChatGPT 5