You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你面前有一排 $n$ 堆硬币排成一线，同一堆硬币的面值相同，记第 $i$ 堆硬币的面值为 $a_i$。而每堆硬币的数量都相同，记为 $x$。

现在你知道每第 $i$ 堆硬币的面值 $a_i$，你需要确定一个正整数 $x$，使得每堆硬币的总金额的方差最接近于一个正整数 $k$。

两数 “最接近” 的定义：两数之差的绝对值最小。

方差定义：方差 $s ^ 2 = \cfrac{(a_1 - \bar x)^2 + (a_2 - \bar x) ^ 2 + \cdots + (a_n - \bar x) ^ 2}{n}$，其中 $\bar x$ 代表 $x$ 的平均值。

输入格式

第一行两个数 $n,k$。

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$，表示第 $i$ 堆硬币的面值 $a_i$。

输出格式

一行一个正整数，表示符合题意的 $x$ 值。如果有不同的答案，输出最小的一个。如果无论 $x$ 取什么值方差都为 $0$，输出一行 No answer!。

7 47
7 2 4 6 3 7 10

3

4 4
4 4 4 4

No answer!

提示

【样例 $\#1$ 解释】

当 $x=3$ 时，第 $i$ 个堆的硬币金额为 $3\times a_i$，这些硬币堆的金额分别为 $21,6,12,18,9,21,30$，可以计算得这些硬币金额的方差约为 $58.78$，可以证明当 $x=3$ 时方差最接近 $47$。

【样例 $\#2$ 解释】

可以发现，无论 $x$ 的取值，方差都会为 $0$，所以输出 No answer!。

【数据规模】

本题采用 Subtask 捆绑测试。

对于 $100\%$ 的数据，$1\le n,\forall a_i\le7\times10^6$，$1\le k\le3\times10^{18}$。记原来 $a$ 数组的方差为 $p$，则数据满足 $p=0$ 或 $p\in[0.25,\ 2^{63}-1]$ 。

【提示】

本题读入量较大，请使用合适的读入方式。此处推荐快速读入模板，对于 $\texttt{C/C++}$ 语言，你也可以使用 scanf 语句完成读入。

为避免卡精度，建议 C/C++ 选手使用 $\texttt{double}$ 类型，并不建议使用 eps。