DNA Molecule Transformation

Chemist Dubravka studies DNA molecules in her laboratory. A DNA molecule is represented by a string composed of characters from the set \(\{A, C, G, T\}\). For example, A, ATG and GTA represent different DNA molecules.

She can apply the following transformations on any part of a DNA molecule:

• \(A \leftrightarrow TC\)
• \(C \leftrightarrow AG\)
• \(G \leftrightarrow CT\)
• \(T \leftrightarrow GA\)

These transformations can be applied repeatedly. For instance, one valid transformation sequence is:

\(AA \rightarrow TCA \rightarrow TAGA \rightarrow TAT\)

Dubravka currently has \(N\) DNA molecules in her laboratory. Write a program that determines for every ordered pair of the given molecules whether it is possible to transform the first molecule into the second by applying these transformations. It turns out that, under these reversible transformations, any DNA molecule can be transformed into any other molecule composed solely of the characters A, C, G, and T.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 100\)), the number of DNA molecules. The following \(N\) lines each contain a non-empty string made up of the characters A, C, G, and T.

outputFormat

Output an \(N \times N\) matrix. The element in the \(i\)-th row and \(j\)-th column should be YES if the \(i\)-th molecule can be transformed into the \(j\)-th molecule by a sequence of the allowed transformations; otherwise output NO. Separate the answers in each row by a space.

sample

3
A
C
G

YES YES YES
YES YES YES
YES YES YES