Školica je dečija igra naročito popularna kod učenica i učenika u osnovnoškolskom uzrastu. Igra se odvija skakutanjem na jednoj ili obe noge kroz šemu iscrtanu na tlu. Praktična je za igranje u školskom dvorištu ili na igralištu.

Šema za igru

Školica je popularna širom sveta, pa se šema kroz koju igrač skakuće razlikuje od zemlje do zemlje. Za potrebe ovog zadatka će se koristiti takozvana niz-šema. Možete je zamisliti kao niz uzastopnih kredom nacrtanih polja numerisanih od ~1~ do ~N~ ili jednostavno pogledati sliku.

Slika školice sa N=8 polja:

Pravila igre

Anja i Ema su se dogovorile da igraju prosto proširenu varijaciju skakutanja gde su dozvoljeni samo skokovi veličine iz skupa prostih brojeva. Početna pozicija je u zamišljenom polju broj ~0~, a pri svakom skoku se može skočiti napred ili nazad prost broj polja u okviru date šeme (sa polja ~i~ moguć je skok na polje ~i-p~ ukoliko važi ~1 \le i-p \le N~ ili skok na polje ~i+p~ ukoliko važi ~1 \le i+p \le N~, gde je ~p~ prost broj). Potrebno je da igrač prođe svih ~N~ polja na ovaj način tako što ni u jedno polje neće stati dvaput i pritom može da završi skakutanje u bilo kom polju.

Pomozite Anji i Emi da pronađu način da odskakuću.

Opis ulaza

U prvoj i jednoj liniji standardnog ulaza nalazi se broj ~N~ (~1 \le N \le 10^5~) koji označava broj polja šeme školice.

Opis izlaza

U prvoj liniji standardnog izlaza ispisati da li je moguće odskakutati celu šemu na gore opisani način: ~DA~ ukoliko jeste, ~NE~ ukoliko nije. U drugoj liniji (ukoliko postoji rešenje) ispisati ~N~ brojeva koji označavaju redne brojeve polja redosledom kako se na koje skače u skladu sa pravilima igre. Ukoliko postoji više načina za odskakutati, ispisati bilo koji.

Primer

8

DA
3 1 8 5 7 2 4 6

1

NE

Objašnjenje test primera:

Veličine napravljenih skokova su, redom: 3, 2, 7, 3, 2, 5, 2, 2 i svi su iz skupa prostih brojeva. Takođe, svako polje je posećeno tačno jedanput.

Slika jednog od mogućih skakutanja koje je po pravilima igre:

Ograničenja i podzadaci

~1 \le N \le 10^5~

Test primeri su podeljeni u 3 disjunktne grupe:

• U test primerima vrednim 30 poena: ~1 \le N \le 50~
  
• U test primerima vrednim 20 poena: ~1 \le N \le 10^3~
  
• U test primerima vrednim 50 poena: Nema dodatnih ograničenja.