시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 45 17 12 46.154%

문제

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+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWIyOTQgXHVkNTVjIEROQSBcdWJkODRcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWNlMFx1Y2NkMCBcdWIyZTRcdWI5NzggRE5BIFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0LCBBQSAmcmFycjsgVENBICZyYXJyOyBUQUdBICZyYXJyOyBUQVQgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NDBcdWFlMzBcdWM3NTggXHVjNWYwXHVhZDZjXHVjMmU0XHVjNWQwXHViMjk0IEROQSBcdWJkODRcdWM3OTBcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjk3YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YmQ4NFx1Yzc5MFx1Yjg1YyBcdWFjZTBcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEROQSBcdWJkODRcdWM3OTBcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmQ4NFx1Yzc5MFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBETkEgXHViZDg0XHVjNzkwXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViZDg0XHVjNzkwXHViMjk0ICYjMzk7QSYjMzk7LCAmIzM5O0MmIzM5OywgJiMzOTtHJiMzOTssICYjMzk7VCYjMzk7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCA1MCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIE5cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM3NTggalx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWFjMDAgJiMzOTsxJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHViZDg0XHVjNzkwXHViOTdjIGpcdWJjODhcdWM5ZjggXHViZDg0XHVjNzkwXHViODVjIFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YmE3MCwgJiMzOTswJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWNlMFx1Y2U2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMDYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR1RBIiwiZGVzY3JpcHRpb24iOiI8cD5EdWJyYXZrYSB0aGUgY2hlbWlzdCBleGFtaW5lcyBETkEgbW9sZWN1bGVzIGluIGhlciBsYWJvcmF0b3J5LiBFYWNoIEROQSBtb2xlY3VsZSBpcyByZXByZXNlbnRlZCB3aXRoIGEgc2VyaWVzIG9mIGNoYXJhY3RlcnMsIHdoZXJlIGVhY2ggY2hhcmFjdGVycyBpcyBmcm9tIHRoZSBzZXQgeyZsc3F1bztBJnJzcXVvOywgJmxzcXVvO0MmcnNxdW87LCAmbHNxdW87RyZyc3F1bzssICZsc3F1bztUJnJzcXVvO30uIFRoZXJlZm9yZSwgJmxzcXVvO0EmcnNxdW87LCAmbHNxdW87QVRHJnJzcXVvOyBhbmQgJmxzcXVvO0dUQSZyc3F1bzsgYXJlIHNlcmllcyBvZiBjaGFyYWN0ZXJzIHdoaWNoIHJlcHJlc2VudCBkaWZmZXJlbnQgRE5BIG1vbGVjdWxlcy48XC9wPlxyXG5cclxuPHA+RHVicmF2a2EgY2FuIHBlcmZvcm0gdGhlIGZvbGxvd2luZyBtdXRhdGlvbnMgKGFsdGVyYXRpb25zKSBpbiBhbnkgcGFydCBvZiB0aGUgRE5BIG1vbGVjdWxlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgJmhhcnI7IFRDICh0aGVyZWZvcmUsIHRoZSBjaGFyYWN0ZXIgJmxzcXVvO0EmcnNxdW87IGNhbiBiZSByZXBsYWNlZCB3aXRoJmxzcXVvO1RDJnJzcXVvOyBhbmQgdmljZSB2ZXJzYSk8XC9saT5cclxuXHQ8bGk+QyAmaGFycjsgQUc8XC9saT5cclxuXHQ8bGk+RyAmaGFycjsgQ1Q8XC9saT5cclxuXHQ8bGk+VCAmaGFycjsgR0E8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5EdWJyYXZrYSB0ZW5kcyB0byB0YWtlIGEgY2VydGFpbiBtb2xlY3VsZSBhbmQgYWx0ZXIgaXQgYnkgc3VjY2Vzc2l2ZWx5IGFwcGx5aW5nIHRoZXNlIG11dGF0aW9ucy4gVGhpcyByZXN1bHRzIGluIGEgZGlmZmVyZW50IG1vbGVjdWxlLCBmb3IgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHA+QUEgJnJhcnI7IFRDQSAmcmFycjsgVEFHQSAmcmFycjsgVEFULjxcL3A+XHJcblxyXG48cD5EdWJyYXZrYSBjdXJyZW50bHkgaGFzIE4gbW9sZWN1bGVzIGluIGhlciBsYWJvcmF0b3J5LiBXcml0ZSBhIHByb2dyYW1tZSB0aGF0IHdpbGwsIGZvciBlYWNoIHBhaXIgb2YgZ2l2ZW4gbW9sZWN1bGVzLCBkZXRlcm1pbmUgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBlbmQgdXAgd2l0aCB0aGUgc2Vjb25kIG1vbGVjdWxlIHdoZW4gc3RhcnRpbmcgZnJvbSB0aGUgZmlyc3QgbW9sZWN1bGUgYnkgYXBwbHlpbmcgdGhlIG1lbnRpb25lZCBtdXRhdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgbW9sZWN1bGVzLiBUaGUgbW9sZWN1bGVzIGFyZSBtYXJrZWQgd2l0aCBudW1iZXJzIGZyb20gMSB0byBOLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBtb2xlY3VsZXMgJm5kYXNoOyBzZXJpZXMgb2YgY2hhcmFjdGVycyB3aGVyZSBlYWNoIGNoYXJhY3RlciBpcyBhbiB1cHBlcmNhc2UgbGV0dGVyICZsc3F1bztBJnJzcXVvOywgJmxzcXVvO0MmcnNxdW87LCAmbHNxdW87RyZyc3F1bzsgb3IgJmxzcXVvO1QmcnNxdW87LiBFYWNoIHNlcmllcyBvZiBjaGFyYWN0ZXJzIGNvbnNpc3RzIG9mIGF0IGxlYXN0IG9uZSBhbmQgYXQgbW9zdCA1MCAwMDAgY2hhcmFjdGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZXhhY3RseSBOIGNoYXJhY3RlcnMgaW4gZWFjaCBvZiBOIGxpbmVzLiBUaGUgai10aCBjaGFyYWN0ZXIgaW4gdGhlIGktdGggbGluZSBzaG91bGQgYmUgJmxzcXVvOzEmcnNxdW87IGlmIGl0JnJzcXVvO3MgcG9zc2libGUgdG8gZ2V0IG1vbGVjdWxlIGogZnJvbSB0aGUgbW9sZWN1bGUgaSwgb3RoZXJ3aXNlIGl0IHNob3VsZCBiZSAmbHNxdW87MCZyc3F1bzsuIFlvdSBtdXN0biZyc3F1bzt0IHByaW50IHNwYWNlcyBiZXR3ZWVuIGluZGl2aWR1YWwgY2hhcmFjdGVycyBpbiB0aGUgc2FtZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d