Mamy do dyspozycji wagę szalkową. Waga znajduje się w stanie równowagi wtedy i tylko wtedy, gdy obie szalki są puste lub gdy sumy mas odważników na obu szalkach są takie same. W danym zbiorze odważników należy znaleźć takie dwa rozłączne podzbiory, aby po położeniu wszystkich odważników z jednego z nich na jednej szalce, natomiast wszystkich odważników z drugiego zbioru na drugiej szalce, waga znalazła się w stanie równowagi. Ponadto żądamy, aby na wadze znalazł się odważnik o jak największej masie.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego wag.in masy dostępnych odważników,
• wyznaczy dwa rozłączne zbiory odważników spełniające warunki zadania,
• zapisze wynik do pliku tekstowego wag.out.

Wejście

W pierwszym wierszu pliku tekstowego wag.in znajduje się jedna liczba całkowita n, 2<=n<=1 000, równa liczbie dostępnych odważników. W każdym z następnych n wierszy znajduje się po jednej dodatniej liczbie całkowitej równej masie jednego odważnika za zbioru dostępnych odważników. Można założyć, że łączna masa odważników nie przekracza 50 000.

Wyjście

W pierwszym wierszu pliku tekstowego wag.out należy zapisać dwie nieujemne liczby całkowite p i q oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę odważników w pierwszym i w drugim zbiorze. W drugim wierszu powinno się znaleźć p liczb całkowitych oddzielonych pojedynczymi odstępami. Powinny to być masy odważników z pierwszego zbioru. Natomiast w trzecim wierszu powinno zostać wypisanych q liczb całkowitych odzielonych pojedynczymi odstępami i równych masom odważników w drugim zbiorze.

Przykład

Dla danych pliku wejściowego wag.in:

4
1
1
2
7

poprawną odpowiedzią jest plik wyjściowy wag.out:

2 1
1 1
2

Komunikat podczas zawodów

Spośród wszystkich układów odważników, dla których waga jest w równowadze należy wybrać ten, który zawiera odważnik o maksymalnej możliwej masie. W przypadku wielu takich rozwiązań trzeba podać tylko jedno z nich.