Kolmijako

• Time limit: 1.00 s
• Memory limit: 512 MB

Tehtäväsi on jakaa luvut $1,2,\dots,n$ kolmeen joukkoon niin, että joukon $2$ lukujen summa on yhden suurempi kuin joukon $1$ lukujen summa ja yhden pienempi kuin joukon $3$ lukujen summa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Tulosta yksi rivi, jolla on $n$ lukua $g_1\ g_2\ \dots\ g_n$. Luku $g_k$ ilmaisee, mihin joukkoon luku $k$ kuuluu.

Jos ratkaisua ei ole olemassa, tulosta IMPOSSIBLE.

Esimerkki 1

Syöte:
8

Tuloste:
1 3 1 2 3 3 1 2

Selitys: Tässä ratkaisussa joukot ovat $\{1,3,7\}$, $\{4,8\}$ ja $\{2,5,6\}$ ja summat vastaavasti $11$, $12$ ja $13$.

Esimerkki 2

Syöte:
4

Tuloste:
IMPOSSIBLE

Osatehtävä 1 (22 pistettä)

• $3 \le n \le 10$
  

Osatehtävä 2 (78 pistettä)

• $3 \le n \le 100$