Yuki ist der Hauptschiedsrichter der Internationalen Meisterschaft der konvexen Vielecke (ICPC). Er schlug eine Geometrieaufgabe für den Wettbewerb vor. Wegen seiner mangelnden Erfahrung in Geometrie gelang es ihm jedoch nicht, korrekte Daten konvexer Vielecke zu erzeugen.
Um seine geometrischen Fähigkeiten zu beweisen, begann Yuki erneut, mit Stäben zu spielen. Er hat $n$ Stäbe, wobei der $i$-te die Länge $a_i$ hat. Er möchte mindestens $3$ davon auswählen, sodass diese Stäbe ein nicht entartetes konvexes Vieleck$^*$ bilden können.
Da Yuki jedoch nicht viel über Geometrie weiß, weiß er nicht, wie er die Stäbe auswählen soll. Als guter Freund von Yuki musst du ihm helfen, eine Teilmenge von Stäben zu finden, sodass:
Die Teilmenge mindestens $3$ Stäbe enthält und die Anzahl der Stäbe so groß wie möglich ist;
Für jede aus dieser Teilmenge ausgewählte Teilmenge von mindestens $3$ Stäben diese Stäbe ein nicht entartetes konvexes Vieleck bilden können.
Oder melde, dass keine solche Teilmenge existiert.
$^*$: Ein nicht entartetes konvexes Vieleck ist ein Vieleck, dessen Seitenlängen alle größer als null sind, bei dem keine drei Eckpunkte auf einer Geraden liegen und dessen Innenwinkel alle strikt kleiner als $180^\circ$ sind.
Eingabe
Diese Aufgabe enthält mehrere Testfälle.
Die erste Zeile enthält eine positive ganze Zahl $t$ ($1 \le t \le 10^5$), die Anzahl der Testfälle.
Für jeden Testfall:
Die erste Zeile enthält eine positive ganze Zahl $n$ ($3 \le n \le 5 \cdot 10^5$).
Die zweite Zeile enthält $n$ positive ganze Zahlen $a_1,\ldots,a_n$ ($1 \le a_i \le 10^9$).
Es ist garantiert, dass die Summe von $n$ über alle Testfälle höchstens $5 \cdot 10^5$ beträgt.
Ausgabe
Gib für jeden Testfall eine Zeile aus:
Falls keine solche Teilmenge existiert, gib eine einzelne ganze Zahl $0$ aus.
Falls eine solche Teilmenge existiert, gib zuerst eine ganze Zahl $k$ aus, die Größe der gefundenen Teilmenge, gefolgt von $k$ ganzen Zahlen $b_1,\ldots,b_k$, den Längen der $k$ Stäbe in deiner Teilmenge.
Beispiele
Eingabe 1
3 4 6 9 2 6 3 4 4 9 6 3 1 4 6 5 9
Ausgabe 1
3 6 2 6 0 4 3 4 5 6
Hinweis
Für den ersten Testfall:
$\{6,2,6\}$ ist eine gültige Teilmenge; da $2+6>6$ gilt, können diese $3$ Stäbe ein nicht entartetes Dreieck bilden; es ist leicht zu beweisen, dass keine größere gültige Teilmenge existiert.
$\{6,6,9\}$ ist ebenfalls eine gültige Teilmenge.
Für den zweiten Testfall:
- Es lässt sich beweisen, dass keine gültige Teilmenge existiert.
Für den dritten Testfall:
$\{3,4,5,6\}$ ist eine gültige Teilmenge; in diesem Fall hat Yuki $5$ Möglichkeiten, Stäbe auszuwählen: $\{3,4,5\}$, $\{3,4,6\}$, $\{3,5,6\}$, $\{4,5,6\}$, $\{3,4,5,6\}$. Jede Auswahl kann ein nicht entartetes konvexes Vieleck bilden; es ist leicht zu beweisen, dass keine größere gültige Teilmenge existiert.
$\{3,4,5,6,9\}$ ist keine gültige Teilmenge, weil die Stäbe mit den Längen $3,4,9$ kein nicht entartetes Dreieck bilden können.
$\{3,5,6\}$ ist keine gültige Teilmenge, weil eine größere gültige Teilmenge existiert.