Yuki es el juez principal del Campeonato Internacional de Polígonos Convexos (ICPC). Propuso un problema de geometría para la competición. Sin embargo, debido a su falta de experiencia en geometría, no logró generar datos correctos de polígonos convexos.
Para demostrar su capacidad geométrica, Yuki volvió a jugar con palos. Tiene $n$ palos, y la longitud del palo $i$ es $a_i$. Quiere elegir al menos $3$ de ellos de modo que puedan formar un polígono convexo no degenerado$^*$.
Sin embargo, como Yuki no sabe mucho de geometría, no sabe cómo elegir los palos. Como buen amigo suyo, debes ayudarlo a encontrar un subconjunto de palos tal que:
El subconjunto contenga al menos $3$ palos y el número de palos sea lo mayor posible;
Para cualquier subconjunto de al menos $3$ palos elegido de este subconjunto, esos palos puedan formar un polígono convexo no degenerado.
O informa de que no existe tal subconjunto.
$^*$: Un polígono convexo no degenerado es un polígono cuyos lados tienen longitudes mayores que cero, en el que no hay tres vértices colineales y todos los ángulos interiores son estrictamente menores que $180^\circ$.
Entrada
Este problema contiene varios casos de prueba.
La primera línea contiene un entero positivo $t$ ($1 \le t \le 10^5$), que representa el número de casos de prueba.
Para cada caso de prueba:
La primera línea contiene un entero positivo $n$ ($3 \le n \le 5 \cdot 10^5$).
La segunda línea contiene $n$ enteros positivos $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $5 \cdot 10^5$.
Salida
Para cada caso de prueba, imprime una línea:
Si no existe tal subconjunto, imprime un único entero $0$.
Si existe, imprime primero un entero $k$, que representa el tamaño del subconjunto encontrado, seguido de $k$ enteros $b_1,\ldots,b_k$, que representan las longitudes de los $k$ palos de tu subconjunto.
Ejemplos
Entrada 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Salida 1
3 6 2 6 0 4 3 4 5 6
Nota
Para el primer caso de prueba:
$\{6,2,6\}$ es un subconjunto válido; como $2+6>6$, estos $3$ palos pueden formar un triángulo no degenerado; es fácil demostrar que no existe un subconjunto válido mayor.
$\{6,6,9\}$ también es un subconjunto válido.
Para el segundo caso de prueba:
- Se puede demostrar que no existe ningún subconjunto válido.
Para el tercer caso de prueba:
$\{3,4,5,6\}$ es un subconjunto válido; en este caso, Yuki tiene $5$ formas de elegir palos: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, y cada una puede formar un polígono convexo no degenerado; es fácil demostrar que no existe un subconjunto válido mayor.
$\{3,4,5,6,9\}$ no es un subconjunto válido porque los palos de longitudes $3,4,9$ no pueden formar un triángulo no degenerado.
$\{3,5,6\}$ no es un subconjunto válido porque existe un subconjunto válido mayor.