Yuki è il giudice capo dell'International Convex Polygon Championship (ICPC). Ha proposto un problema di geometria per la competizione. Tuttavia, a causa della sua mancanza di esperienza in geometria, non è riuscito a generare dati corretti sui poligoni convessi.
Per dimostrare la sua abilità geometrica, Yuki ha iniziato di nuovo a giocare con i bastoncini. Ha $n$ bastoncini, dove la lunghezza dell'$i$-esimo bastoncino è $a_i$. Intende scegliere almeno $3$ bastoncini tra essi in modo tale che questi bastoncini possano formare un poligono convesso non degenere$^*$.
Tuttavia, poiché Yuki non sa molto di geometria, non sa come scegliere i bastoncini. Come buon amico di Yuki, devi aiutarlo a trovare un sottoinsieme di bastoncini tale che:
Il sottoinsieme contenga almeno $3$ bastoncini e il numero di bastoncini sia il più grande possibile;
Per qualsiasi sottoinsieme di almeno $3$ bastoncini scelto da questo sottoinsieme, questi bastoncini possano formare un poligono convesso non degenere.
Oppure segnala che un tale sottoinsieme non esiste.
$^*$: Un poligono convesso non degenere è un poligono in cui tutte le lunghezze dei lati sono maggiori di zero, non ci sono tre vertici collineari e tutti gli angoli interni sono strettamente minori di $180^\circ$.
Input
Questo problema contiene più casi di test.
La prima riga contiene un intero positivo $t$ ($1 \le t \le 10^5$), che rappresenta il numero di casi di test.
Per ogni caso di test:
La prima riga contiene un intero positivo $n$ ($3 \le n \le 5 \cdot 10^5$).
La seconda riga contiene $n$ interi positivi $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
È garantito che la somma di $n$ su tutti i casi di test non superi $5 \cdot 10^5$.
Output
Per ogni caso di test, stampa una riga:
Se un tale sottoinsieme non esiste, stampa un singolo intero $0$.
Se un tale sottoinsieme esiste, stampa prima un intero $k$, che rappresenta la dimensione del sottoinsieme trovato, seguito da $k$ interi $b_1,\ldots,b_k$, che rappresentano le lunghezze dei $k$ bastoncini nel tuo sottoinsieme.
Esempio
Input di esempio 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Output di esempio 1
3 6 2 6 0 4 3 4 5 6
Nota
Per il primo caso di test:
$\{6,2,6\}$ è un sottoinsieme valido; poiché $2+6>6$, questi $3$ bastoncini possono formare un triangolo non degenere; è facile dimostrare che non esiste alcun sottoinsieme valido più grande.
Anche $\{6,6,9\}$ è un sottoinsieme valido.
Per il secondo caso di test:
- Si può dimostrare che non esiste alcun sottoinsieme valido.
Per il terzo caso di test:
$\{3,4,5,6\}$ è un sottoinsieme valido; in questo caso, Yuki ha $5$ modi per scegliere i bastoncini: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, e ciascun modo può formare un poligono convesso non degenere; è facile dimostrare che non esiste alcun sottoinsieme valido più grande.
$\{3,4,5,6,9\}$ non è un sottoinsieme valido perché i bastoncini di lunghezze $3,4,9$ non possono formare un triangolo non degenere.
$\{3,5,6\}$ non è un sottoinsieme valido perché esiste un sottoinsieme valido più grande.