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\}$ 不是合法的子集,因為存在更大的合法子集。