RNA Sequence Generator

You are given an RNA sequence that may contain the wildcard character N. Each occurrence of N can be replaced with any of the four nucleotides: A, C, G or U. Your task is to generate all possible valid RNA sequences by replacing each N accordingly. Finally, output all generated sequences in lexicographical order, each on a separate line.

More formally, if the input RNA sequence is of length \(n\) and has \(k\) wildcard characters, there are \(4^k\) possible sequences. You are required to compute and print them in sorted order.

inputFormat

The input consists of a single line containing an RNA sequence composed of the characters A, U, G, C and the wildcard N.

outputFormat

Output all possible RNA sequences derived from the input by replacing each N with one of A, C, G or U, sorted in lexicographical order. Each sequence should be printed on a separate line.

AUGC

AUGC