Eunki's DNA Molecules

Time limit5sMemory limit256 MB

Summary

For every pair of N DNA strings, decide whether four two-way substring swaps can rewrite one into the other.

Problem

A DNA string uses A, C, G, T. Apply these bidirectional substring replacements:

For $N$ strings, output whether each pair can transform from the first to the second.

Line 1: $N$ ( $2 \le N \le 100$ ). Next $N$ DNA strings (length $\le 50\,000$ ).

$N$ lines of $N$ 0/1 chars; 1 at $(i,j)$ means string $i$ can become string $j$ .

Example 3

Input

4
AAA
CCC
TATA
CACA

Expected output