题目描述

我们有$N$个整数$A_1, A_2, ..., A_N$。

有$\frac{N(N-1)}{2}$种方式可以选择其中两个数并组成一对。如果我们计算每对的乘积并按升序排序结果，那么列表中的第$K$个数字是什么？

约束条件

• 输入中的所有值都是整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq \frac{N(N-1)}{2}$
• $-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)$

输入

输入数据的格式如下：

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。

示例输入 1

4 3
3 3 -4 -2

示例输出 1

-6

有六种方式可以组成一对。这些对的乘积分别为$9$, $-12$, $-6$, $-12$, $-6$, $8$。

将这些数按升序排序，我们得到$-12$, $-12$, $-6$, $-6$, $8$, $9$。在这个列表中第三个数字是$-6$。

示例输入 2

10 40
5 4 3 2 -1 0 0 0 0 0

示例输出 2

6

示例输入 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

示例输出 3

448283280358331064