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,\ldots,a_n$($1 \le a_i \le 10^9$)。
保證所有測試數據嘅 $n$ 總和唔超過 $5 \cdot 10^5$。
輸出格式
對於每組測試數據,輸出一行:
如果冇呢種子集,輸出一個整數 $0$。
如果有呢種子集,先輸出一個整數 $k$,表示你搵到嘅子集大小,再輸出 $k$ 個整數 $b_1,\ldots,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\}$ 唔係合法子集,因為有更大嘅合法子集。