Generisati sve moguće šifre za neki sistem koje zadovoljavaju sledeće kriterijume:

• Svaka šifra može koristiti samo karaktere A, B, C, 1, 2, 3, @ i $.
• Svaka šifra mora biti dužine n karaktera.
• Svaka šifra mora sadržati bar jedan specijalan simbol. Specijalni simboli su karakteri @ i $.
• Nema uzastopnih identičnih karaktera u šifri.

Napisati algoritam koji generiše sve moguće šifre dužine n koje zadovoljavaju gore navedene kriterijume.

Ulaz

Sa standardnog ulaza se unosi dužina šifre n (2 ≤ n ≤ 6).

Izlaz

Ispisati sve šifre dužine n koje zadovoljavaju navedena pravila. Ispisati šifre u leksikografski rastućem poretku.

Primer

Ulaz

2

Izlaz

$1
$2
$3
$@
$A
$B
$C
1$
1@
2$
2@
3$
3@
@$
@1
@2
@3
@A
@B
@C
A$
A@
B$
B@
C$
C@