Yuki 是国际凸多边形锦标赛(ICPC)的主裁判。他为比赛设计了一道几何题。然而,由于缺乏几何方面的经验,他未能生成正确的凸多边形数据。
为了证明自己的几何能力,Yuki 又开始玩起了木棍。他有 $n$ 根木棍,其中第 $i$ 根木棍的长度为 $a_i$。他打算从中挑选至少 3 根木棍,使得这些木棍能够组成一个非退化的凸多边形*。
然而,由于 Yuki 对几何知之甚少,他不知道该如何选择木棍。作为 Yuki 的好朋友,你需要帮助他找到一个木棍的子集,满足:
- 该子集至少包含 3 根木棍,且木棍的数量尽可能多;
- 从该子集中任意选择至少 3 根木棍,这些木棍都能组成一个非退化的凸多边形。
或者报告不存在这样的子集。
*:非退化凸多边形是指所有边长均大于零、任意三点不共线且所有内角均严格小于 $180^\circ$ 的多边形。
输入格式
本题包含多个测试用例。
第一行包含一个正整数 $t$($1 \le t \le 10^5$),表示测试用例的数量。
对于每个测试用例:
- 第一行包含一个正整数 $n$($3 \le n \le 5 \cdot 10^5$)。
- 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$($1 \le a_i \le 10^9$)。
保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。
输出格式
对于每个测试用例,输出一行:
- 如果不存在这样的子集,输出单个整数
0。 - 如果存在这样的子集,首先输出一个整数 $k$,表示你找到的子集的大小,随后输出 $k$ 个整数 $b_1, \dots, b_k$,表示你选择的子集中这 $k$ 根木棍的长度。
样例
输入 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
输出 1
3 6 2 6 0 4 3 4 5 6
说明
对于第一个测试用例:
- $\{6, 2, 6\}$ 是一个合法的子集;因为 $2 + 6 > 6$,这 3 根木棍可以组成一个非退化三角形;易证不存在更大的合法子集。
- $\{6, 6, 9\}$ 也是一个合法的子集。
对于第二个测试用例:
- 可以证明不存在合法的子集。
对于第三个测试用例:
- $\{3, 4, 5, 6\}$ 是一个合法的子集;在这种情况下,Yuki 有 5 种选择木棍的方式:$\{3, 4, 5\}$、$\{3, 4, 6\}$、$\{3, 5, 6\}$、$\{4, 5, 6\}$、$\{3, 4, 5, 6\}$,每种方式都可以组成一个非退化凸多边形;易证不存在更大的合法子集。
- $\{3, 4, 5, 6, 9\}$ 不是一个合法的子集,因为长度为 3, 4, 9 的木棍无法组成一个非退化三角形。
- $\{3, 5, 6\}$ 不是一个合法的子集,因为存在一个更大的合法子集。