partiții

Cerință

Să se împartă mulțimea numerelor naturale de la 1 la $n$ în două grupe așa încât suma elementelor dintr-o grupă să fie egală cu suma elementelor din cealaltă grupă.

Date de intrare

Pe prima linie a fișierului partitii.in se află un număr natural $n$.

Date de ieșire

Datele de ieșire se vor scrie în fișierul partitii.out astfel:

• pe prima linie se va afișa DA dacă este posibilă o astfel de partiționare a mulțimii inițiale și NU, în caz contrar;
• pe a doua linie se va scrie prima partiție, mai întâi numărul de elemente ale sale și apoi elementele, separate prin câte un spațiu;
• pe a treia linie se va scrie a doua partiție având elementele în ordine crescătoare, mai întâi numărul de elemente ale sale și apoi elementele, separate prin câte un spațiu;
  Dacă răspunsul este NU, liniile a doua și a treia nu mai apar.
  Orice variantă de partiționare pentru care sumele elementelor din cele două submulțimi sunt egale, și în care este folosit fiecare număr de la 1 la $n$ exact o dată, este considerată corectă.

Restricții și precizări

• $1 \leq n \leq 1\ 000\ 000$;

Exemplul 1

partitii.in

3

partitii.out

DA
2 1 2
1 3

Exemplul 2

partitii.in

8

partitii.out

DA
4 1 5 8 4
4 2 3 6 7

Exemplul 3

partitii.in

5

partitii.out

NU