Yuki é o juiz principal do Campeonato Internacional de Polígonos Convexos (ICPC). Propôs um problema de geometria para a competição. No entanto, por falta de experiência em geometria, não conseguiu gerar dados corretos de polígonos convexos.
Para provar a sua capacidade geométrica, Yuki voltou a brincar com varetas. Tem $n$ varetas, sendo $a_i$ o comprimento da $i$-ésima. Pretende escolher pelo menos $3$ delas de modo que possam formar um polígono convexo não degenerado$^*$.
Porém, como Yuki não sabe muito de geometria, não sabe como escolher as varetas. Como bom amigo dele, precisas de o ajudar a encontrar um subconjunto de varetas tal que:
O subconjunto contenha pelo menos $3$ varetas e o número de varetas seja o maior possível;
Para qualquer subconjunto de pelo menos $3$ varetas escolhido deste subconjunto, essas varetas possam formar um polígono convexo não degenerado.
Ou indica que não existe tal subconjunto.
$^*$: Um polígono convexo não degenerado é um polígono em que todos os lados têm comprimento maior que zero, não há três vértices colineares e todos os ângulos internos são estritamente menores que $180^\circ$.
Entrada
Este problema contém vários casos de teste.
A primeira linha contém um inteiro positivo $t$ ($1 \le t \le 10^5$), que representa o número de casos de teste.
Para cada caso de teste:
A primeira linha contém um inteiro positivo $n$ ($3 \le n \le 5 \cdot 10^5$).
A segunda linha contém $n$ inteiros positivos $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
É garantido que a soma de $n$ em todos os casos de teste não excede $5 \cdot 10^5$.
Saída
Para cada caso de teste, imprime uma linha:
Se não existir tal subconjunto, imprime um único inteiro $0$.
Se existir, imprime primeiro um inteiro $k$, que representa o tamanho do subconjunto encontrado, seguido de $k$ inteiros $b_1,\ldots,b_k$, que representam os comprimentos das $k$ varetas do subconjunto.
Exemplos
Entrada 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Saída 1
3 6 2 6 0 4 3 4 5 6
Nota
Para o primeiro caso de teste:
$\{6,2,6\}$ é um subconjunto válido; como $2+6>6$, estas $3$ varetas podem formar um triângulo não degenerado; é fácil provar que não existe um subconjunto válido maior.
$\{6,6,9\}$ também é um subconjunto válido.
Para o segundo caso de teste:
- Pode provar-se que não existe um subconjunto válido.
Para o terceiro caso de teste:
$\{3,4,5,6\}$ é um subconjunto válido; neste caso, Yuki tem $5$ formas de escolher varetas: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$, e cada forma pode produzir um polígono convexo não degenerado; é fácil provar que não existe um subconjunto válido maior.
$\{3,4,5,6,9\}$ não é um subconjunto válido porque as varetas de comprimentos $3,4,9$ não podem formar um triângulo não degenerado.
$\{3,5,6\}$ não é um subconjunto válido porque existe um subconjunto válido maior.