시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 29 13 9 39.130%

문제

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'인 경우에는 고칠 수 없다는 뜻이다.

예제 입력 1

4
AA
TAT
C
CGTAC

예제 출력 1

1100
1100
0011
0011

예제 입력 2

4
A
C
G
T

예제 출력 2

1000
0100
0010
0001

예제 입력 3

4
AAA
CCC
TATA
CACA

예제 출력 3

1111
1111
1111
1111
W3sicHJvYmxlbV9pZCI6IjEwMDYyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzQwXHVhZTMwXHVjNzU4IEROQSBcdWJkODRcdWM3OTAiLCJkZXNjcmlwdGlvbiI6IjxwPkROQSBcdWJkODRcdWM3OTBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YWUwMFx1Yzc5MFx1YjI5NCB7JiMzOTtBJiMzOTssJiMzOTtDJiMzOTssJiMzOTtHJiMzOTssJiMzOTtUJiMzOTt9IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgJiMzOTtBJiMzOTssICYjMzk7QVRHJiMzOTssICYjMzk7R1RBJiMzOTtcdWIyOTQgXHViYWE4XHViNDUwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggRE5BIFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc0MFx1YWUzMFx1YjI5NCBETkEgXHViZDg0XHVjNzkwXHViOTdjIFx1YzVmMFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ2NTRcdWQ1NTlcdWM3OTBcdWM3NzRcdWFjZTAsIEROQSBcdWJkODRcdWM3OTBcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BICZoYXJyOyBUQyAoQVx1YjI5NCBUQ1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YzVlZFx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+QyAmaGFycjsgQUc8XC9saT5cclxuXHQ8bGk+RyAmaGFycjsgQ1Q8XC9saT5cclxuXHQ8bGk+VCAmaGFycjsgR0E8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWIyOTQgXHVkNTVjIEROQSBcdWJkODRcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWNlMFx1Y2NkMCBcdWIyZTRcdWI5NzggRE5BIFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBBQSAmcmFycjsgVENBICZyYXJyOyBUQUdBICZyYXJyOyBUQVQgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWM3NTggXHVjNWYwXHVhZDZjXHVjMmU0XHVjNWQwXHViMjk0IEROQSBcdWJkODRcdWM3OTBcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHVjMzBkXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJkODRcdWM3OTBcdWI5N2MgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWJkODRcdWM3OTBcdWI4NWMgXHVhY2UwXHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBETkEgXHViZDg0XHVjNzkwXHVjNzU4IFx1YzIxOCBOICgyICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJkODRcdWM3OTBcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgRE5BIFx1YmQ4NFx1Yzc5MFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmQ4NFx1Yzc5MFx1YjI5NCAmIzM5O0EmIzM5OywgJiMzOTtDJiMzOTssICYjMzk7RyYjMzk7LCAmIzM5O1QmIzM5O1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFlMzhcdWM3NzRcdWIyOTQgNTAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBOXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNzU4IGpcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVhYzAwICYjMzk7MSYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjk3YyBqXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjg1YyBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWJhNzAsICYjMzk7MCYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAwNjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHVEEiLCJkZXNjcmlwdGlvbiI6IjxwPkR1YnJhdmthIHRoZSBjaGVtaXN0IGV4YW1pbmVzIEROQSBtb2xlY3VsZXMgaW4gaGVyIGxhYm9yYXRvcnkuIEVhY2ggRE5BIG1vbGVjdWxlIGlzIHJlcHJlc2VudGVkIHdpdGggYSBzZXJpZXMgb2YgY2hhcmFjdGVycywgd2hlcmUgZWFjaCBjaGFyYWN0ZXJzIGlzIGZyb20gdGhlIHNldCB7JmxzcXVvO0EmcnNxdW87LCAmbHNxdW87QyZyc3F1bzssICZsc3F1bztHJnJzcXVvOywgJmxzcXVvO1QmcnNxdW87fS4gVGhlcmVmb3JlLCAmbHNxdW87QSZyc3F1bzssICZsc3F1bztBVEcmcnNxdW87IGFuZCAmbHNxdW87R1RBJnJzcXVvOyBhcmUgc2VyaWVzIG9mIGNoYXJhY3RlcnMgd2hpY2ggcmVwcmVzZW50IGRpZmZlcmVudCBETkEgbW9sZWN1bGVzLjxcL3A+XHJcblxyXG48cD5EdWJyYXZrYSBjYW4gcGVyZm9ybSB0aGUgZm9sbG93aW5nIG11dGF0aW9ucyAoYWx0ZXJhdGlvbnMpIGluIGFueSBwYXJ0IG9mIHRoZSBETkEgbW9sZWN1bGU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSAmaGFycjsgVEMgKHRoZXJlZm9yZSwgdGhlIGNoYXJhY3RlciAmbHNxdW87QSZyc3F1bzsgY2FuIGJlIHJlcGxhY2VkIHdpdGgmbHNxdW87VEMmcnNxdW87IGFuZCB2aWNlIHZlcnNhKTxcL2xpPlxyXG5cdDxsaT5DICZoYXJyOyBBRzxcL2xpPlxyXG5cdDxsaT5HICZoYXJyOyBDVDxcL2xpPlxyXG5cdDxsaT5UICZoYXJyOyBHQTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkR1YnJhdmthIHRlbmRzIHRvIHRha2UgYSBjZXJ0YWluIG1vbGVjdWxlIGFuZCBhbHRlciBpdCBieSBzdWNjZXNzaXZlbHkgYXBwbHlpbmcgdGhlc2UgbXV0YXRpb25zLiBUaGlzIHJlc3VsdHMgaW4gYSBkaWZmZXJlbnQgbW9sZWN1bGUsIGZvciBleGFtcGxlOjxcL3A+XHJcblxyXG48cD5BQSAmcmFycjsgVENBICZyYXJyOyBUQUdBICZyYXJyOyBUQVQuPFwvcD5cclxuXHJcbjxwPkR1YnJhdmthIGN1cnJlbnRseSBoYXMgTiBtb2xlY3VsZXMgaW4gaGVyIGxhYm9yYXRvcnkuIFdyaXRlIGEgcHJvZ3JhbW1lIHRoYXQgd2lsbCwgZm9yIGVhY2ggcGFpciBvZiBnaXZlbiBtb2xlY3VsZXMsIGRldGVybWluZSB3aGV0aGVyIGl0IGlzIHBvc3NpYmxlIHRvIGVuZCB1cCB3aXRoIHRoZSBzZWNvbmQgbW9sZWN1bGUgd2hlbiBzdGFydGluZyBmcm9tIHRoZSBmaXJzdCBtb2xlY3VsZSBieSBhcHBseWluZyB0aGUgbWVudGlvbmVkIG11dGF0aW9ucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBtb2xlY3VsZXMuIFRoZSBtb2xlY3VsZXMgYXJlIG1hcmtlZCB3aXRoIG51bWJlcnMgZnJvbSAxIHRvIE4uPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIG1vbGVjdWxlcyAmbmRhc2g7IHNlcmllcyBvZiBjaGFyYWN0ZXJzIHdoZXJlIGVhY2ggY2hhcmFjdGVyIGlzIGFuIHVwcGVyY2FzZSBsZXR0ZXIgJmxzcXVvO0EmcnNxdW87LCAmbHNxdW87QyZyc3F1bzssICZsc3F1bztHJnJzcXVvOyBvciAmbHNxdW87VCZyc3F1bzsuIEVhY2ggc2VyaWVzIG9mIGNoYXJhY3RlcnMgY29uc2lzdHMgb2YgYXQgbGVhc3Qgb25lIGFuZCBhdCBtb3N0IDUwIDAwMCBjaGFyYWN0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBleGFjdGx5IE4gY2hhcmFjdGVycyBpbiBlYWNoIG9mIE4gbGluZXMuIFRoZSBqLXRoIGNoYXJhY3RlciBpbiB0aGUgaS10aCBsaW5lIHNob3VsZCBiZSAmbHNxdW87MSZyc3F1bzsgaWYgaXQmcnNxdW87cyBwb3NzaWJsZSB0byBnZXQgbW9sZWN1bGUgaiBmcm9tIHRoZSBtb2xlY3VsZSBpLCBvdGhlcndpc2UgaXQgc2hvdWxkIGJlICZsc3F1bzswJnJzcXVvOy4gWW91IG11c3RuJnJzcXVvO3QgcHJpbnQgc3BhY2VzIGJldHdlZW4gaW5kaXZpZHVhbCBjaGFyYWN0ZXJzIGluIHRoZSBzYW1lIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d