시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 20 6 5 27.778%

문제

DNA 분자는 문자의 연속으로 나타낼 수 있으며, 각 글자는 {'A','C','G','T'} 중 하나이다. 즉, 'A', 'ATG', 'GTA'는 모두 서로 다른 DNA 분자를 나타낸다.

은기는 DNA 분자를 연구하는 화학자이고, DNA 분자를 다음과 같이 고칠 수 있다.

  • A ↔ TC (A는 TC로 변할 수 있고, 그 역으로 변할 수도 있다)
  • C ↔ AG
  • G ↔ CT
  • T ↔ GA

은기는 한 DNA 분자를 적절히 고쳐 다른 DNA 분자를 만드려고 한다. 예를 들면, AA → TCA → TAGA → TAT 이다.

은기의 연구실에는 DNA 분자가 N개 있다. 이 때, 가능한 모든 쌍에 대해서, 첫 번째 분자를 두 번째 분자로 고칠 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 DNA 분자의 수 N (2 ≤ N ≤ 100)이 주어진다. 분자는 입력으로 주어진 순서대로 1번부터 N번이다.

다음 N개 줄에는 DNA 분자가 한 줄에 하나씩 주어진다. 분자는 'A', 'C', 'G', 'T'로만 이루어져 있고, 길이는 50,000을 넘지 않는다.

출력

각 줄마다 N개의 문자를 N줄에 걸쳐서 출력한다. i번째 줄의 j번째 글자가 '1'인 경우에는 i번째 분자를 j번째 분자로 고칠 수 있다는 뜻이며, '0'인 경우에는 고칠 수 없다는 뜻이다.

예제 입력

4
AA
TAT
C
CGTAC

예제 출력

1100
1100
0011
0011

힌트