Uolevi on kehittänyt uuden ohjelmointikielen, jossa ohjelmassa on vain yksi muuttuja X. Ohjelman suorituksen alussa X:n arvo on 1. Kielessä on kolme komentoa:

• ADD: lisää X:n arvoon 3
• MUL: kerro X:n arvo 2:lla
• END: tulosta X:n arvo ja lopeta ohjelma

Tehtäväsi on etsiä lyhin ohjelma, joka tulostaa luvun n, tai todeta, että mitään tällaista ohjelmaa ei ole olemassa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku n.

Tuloste

Jos ohjelma on olemassa, tulosta ensin sen komentojen määrä ja sen jälkeen jokainen komento omalle rivilleen. Jos mahdollisia ohjelmia on useita, voit tulostaa niistä minkä tahansa.

Jos ohjelmaa ei ole olemassa, tulosta vain luku 0.

Esimerkki 1

Syöte:

10

Tuloste:

4
MUL
ADD
MUL
END

Esimerkki 2

Syöte:

12

Tuloste:

0

Osatehtävä 1 (21 pistettä)

• 1 \le n \le 100

Osatehtävä 2 (37 pistettä)

• 1 \le n \le 10^6

Osatehtävä 3 (42 pistettä)

• 1 \le n \le 10^{18}