Юки — Халықаралық дөңес көпбұрыштар чемпионатының (ICPC) бас төрешісі. Ол жарысқа геометриялық есеп ұсынды. Алайда геометриядағы тәжірибесінің аздығынан ол дұрыс дөңес көпбұрыш деректерін құрастыра алмады.
Өзінің геометриялық қабілетін дәлелдеу үшін Юки қайтадан таяқшалармен ойнай бастады. Онда $n$ таяқша бар, мұндағы $i$-ші таяқшаның ұзындығы $a_i$-ге тең. Ол осы таяқшалардан азғындалмаған дөңес көпбұрыш$^*$ құрауға болатындай кемінде $3$ таяқша таңдап алғысы келеді.
Бірақ Юки геометрияны жақсы білмегендіктен, таяқшаларды қалай таңдау керектігін білмейді. Юкидің жақсы досы ретінде сіз оған келесі шарттарды қанағаттандыратын таяқшалардың ішкі жиынын табуға көмектесуіңіз керек:
Ішкі жиында кемінде $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$ таяқшаның ұзындықтарын білдіретін $k$ бүтін сан $b_1,\ldots,b_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\}$ — жарамды ішкі жиын; бұл жағдайда Юкиде таяқшаларды таңдаудың $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\}$ жарамды ішкі жиын емес, өйткені одан үлкенірек жарамды ішкі жиын бар.