Words 1 X11585

Nucleic acid sequences are labeled over the alphabet $\{A,C,G,T\}$, and there are $4^n$ possible genomic sequences of length $n$. Amino acid sequences, on the other hand, are labeled over the alphabet $\{A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y\}$, and there are $20^n$ possible proteomic sequences of length $n$. An interesting problem is the generation of all the genomic sequences with $n$ nucleotides or all the proteomic sequences with $n$ amino acids, that is, the generation of all the words of length $n$ over an alphabet $\Sigma$.

Write code for the words problem. The program must implement and use the WORDS function in the pseudocode discussed in class, which is iterative and is not allowed to perform input/output operations. Make one submission with Python code and another submission with C++ code.

Input

The input is an integer $n$ and an alphabet $\Sigma$.

Output

The output is a sorted list of all the words of length $n$ over the alphabet $\Sigma$.