Yuki — главный судья Международного чемпионата по выпуклым многоугольникам (ICPC). Он предложил для соревнования геометрическую задачу. Однако из-за недостатка опыта в геометрии ему не удалось сгенерировать корректные данные выпуклых многоугольников.
Чтобы доказать свои геометрические способности, Yuki снова начал играть с палочками. У него есть $n$ палочек, длина $i$-й из которых равна $a_i$. Он намерен выбрать не менее $3$ палочек так, чтобы из них можно было составить невырожденный выпуклый многоугольник$^*$.
Однако 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\}$ — недопустимое подмножество, поскольку существует большее допустимое подмножество.