Šeštadieninė informatikos olimpiadininkų mokykla

Burtininkai ruošiasi komandiniam žaidimui. Jam jie turi pasiskirstyti į dvi vienodos galios komandas. Kiekvienas burtininkas turi galią, matuojamą sveikaisiais skaičiais. Kiekviena komanda išsirenka kurį nors iš daugiausiai galios turinčių jos narių komandos kapitonu. Burtininkų komandos galia yra lygi visų jos narių galių sumai, komandos kapitono galią padvigubinus.

Paskirstikite burtininkų grupę į dvi komandas taip, kad jų galia būtų vienoda.

Pradiniai duomenys

Pirmoje eilutėje – burtininkų kiekis (). Antroje eilutėje – sveikųjų skaičių (). -ojo burtininko galia yra .

Rezultatai

Jeigu burtininkų neįmanoma paskirstyti į dvi vienodos galios komandas, išveskite vieną eilutę su skaičiumi . Priešingu atveju, pirmoje eilutėje išveskite gautą komandos galią, bei kitose keturiose eilutėse – komandų sudėtis.

Komandų sudėtis aprašoma dviejose eilutėmis – pirmoje jų įrašomas komandos narių skaičius , o antroje – tarpais atskirti skaičių, žymintys tos komandos burtininkų numerius.

Burtininkai sunumeruoti nuo 1 iki jų galios pateikimo pradiniuose duomenyse tvarka. Kiekvienas burtininkas turi būti priskirtas lygiai vienai iš komandų. Jei yra keli sprendiniai, išveskite bet kurį.

Pavyzdžiai

5
1 2 3 4 5

12
2
2 5
3
1 3 4

4
8 6 7 1

-1

6
4 5 8 6 8 3

24
4
2 6 1 4
2
3 5