시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 47 16 16 39.024%

문제

Wacław Sierpiński는 폴란드 수학자이다. 어느 날 그는 아래와 같은 방법으로 삼각형을 그리기로 했다.

  • 정삼각형 T를 그린다.
  • 삼각형 변의 중점을 서로 연결한다. 새롭게 생긴 정삼각형을 T1, T2, T3, T4라고 한다. 아래 그림 중 왼쪽 그림이 해당한다.
  • 위의 단계를 삼각형 T1, T2, T3에 대해서 반복한다. 새로운 삼각형은 T11, T12, T13, T14, T21, T22, T23, T24, T31, T32, T33, T34가 된다.
  • 1, 2, 3으로 끝나는 모든 삼각형에 대해서 이 방법을 반복한다. 이렇게 생긴 프랙탈을 Sierpinski 삼각형이라고 한다.

삼각형 B가 삼각형 A를 포함하지 않고, A의 한 변 전체가 B의 한 변의 일부일 때, A는 B에 기대고 있다고 한다. 예를 들어, 삼각형 T23은 T24와 T4에 기대고 있지만, T2와 T32에는 기대고 있지 않다. (A가 B에 기대고 있다는 말은 B가 A에 기대고 있다는 말을 포함하지 않는다)

Sierpinski 삼각형의 일부 삼각형 A가 주어진다. 이때, A가 기대고 있는 모든 삼각형 B를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 삼각형 A가 주어진다. 삼각형 A의 이름은 2글자보다 크거나 같고, 50글자보다 작거나 같다. 

출력

삼각형 A가 기대고 있는 모든 삼각형을 한 줄에 하나씩 출력한다. 출력하는 순서는 아무 순서나 상관없다.

예제 입력 1

T4

예제 출력 1

T1
T2
T3
W3sicHJvYmxlbV9pZCI6IjMxNTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJTaWVycGluc2tpIFx1YzBiY1x1YWMwMVx1ZDYxNSIsImRlc2NyaXB0aW9uIjoiPHA+PGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9XYWMlQzUlODJhd19TaWVycGklQzUlODRza2lcIj5XYWNcdTAxNDJhdyBTaWVycGlcdTAxNDRza2k8XC9hPlx1YjI5NCBcdWQzZjRcdWI3ODBcdWI0ZGMgXHVjMjE4XHVkNTU5XHVjNzkwXHVjNzc0XHViMmU0LiBcdWM1YjRcdWIyOTAgXHViMGEwIFx1YWRmOFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWFjXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTUgVFx1Yjk3YyBcdWFkZjhcdWI5YjBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzBiY1x1YWMwMVx1ZDYxNSBcdWJjYzBcdWM3NTggXHVjOTExXHVjODEwXHVjNzQ0IFx1YzExY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1YzBjOFx1Yjg2ZFx1YWM4YyBcdWMwZGRcdWFlMzQgXHVjODE1XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFQxLCBUMiwgVDMsIFQ0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliYyBcdWM5MTEgXHVjNjdjXHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc3NCBcdWQ1NzRcdWIyZjlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzcwNFx1Yzc1OCBcdWIyZThcdWFjYzRcdWI5N2MgXHVjMGJjXHVhYzAxXHVkNjE1IFQxLCBUMiwgVDNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC4gXHVjMGM4XHViODVjXHVjNmI0IFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0MCBUMTEsIFQxMiwgVDEzLCBUMTQsIFQyMSwgVDIyLCBUMjMsIFQyNCwgVDMxLCBUMzIsIFQzMywgVDM0XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+MSwgMiwgM1x1YzczY1x1Yjg1YyBcdWIwNWRcdWIwOThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMwZGRcdWFlMzQgXHVkNTA0XHViNzk5XHVkMGM4XHVjNzQ0IDxhIGhyZWY9XCJodHRwczpcL1wvZW4ud2lraXBlZGlhLm9yZ1wvd2lraVwvU2llcnBpbnNraV90cmlhbmdsZVwiPlNpZXJwaW5za2kgXHVjMGJjXHVhYzAxXHVkNjE1PFwvYT5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2llcnBpbnNraS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6NDc1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGJjXHVhYzAxXHVkNjE1IEJcdWFjMDAgXHVjMGJjXHVhYzAxXHVkNjE1IEFcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCwgQVx1Yzc1OCBcdWQ1NWMgXHViY2MwIFx1YzgwNFx1Y2NiNFx1YWMwMCBCXHVjNzU4IFx1ZDU1YyBcdWJjYzBcdWM3NTggXHVjNzdjXHViZDgwXHVjNzdjIFx1YjU0YywgQVx1YjI5NCBCXHVjNWQwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMwYmNcdWFjMDFcdWQ2MTUgVDIzXHVjNzQwIFQyNFx1YzY0MCBUNFx1YzVkMCBcdWFlMzBcdWIzMDBcdWFjZTAgXHVjNzg4XHVjOWMwXHViOWNjLCBUMlx1YzY0MCBUMzJcdWM1ZDBcdWIyOTQgXHVhZTMwXHViMzAwXHVhY2UwIFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIChBXHVhYzAwIEJcdWM1ZDAgXHVhZTMwXHViMzAwXHVhY2UwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI5ZDBcdWM3NDAgQlx1YWMwMCBBXHVjNWQwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWIyZTRcdWIyOTQgXHViOWQwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlNpZXJwaW5za2kgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1Yzc3Y1x1YmQ4MCBcdWMwYmNcdWFjMDFcdWQ2MTUgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgQVx1YWMwMCBcdWFlMzBcdWIzMDBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMwYmNcdWFjMDFcdWQ2MTUgQlx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTUgQVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgMlx1YWUwMFx1Yzc5MFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA1MFx1YWUwMFx1Yzc5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBiY1x1YWMwMVx1ZDYxNSBBXHVhYzAwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjNTQ0XHViYjM0IFx1YzIxY1x1YzExY1x1YjA5OCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IndhY2xhdyIsImRlc2NyaXB0aW9uIjoiPHA+V2FjbGF3IFNpZXJwaW5za2kgd2FzIGEgUG9saXNoIG1hdGhlbWF0aWNpYW4gd2hvIGxpa2VkIHBsYXlpbmcgd2l0aCB0cmlhbmdsZXMuIE9uZSBkYXkgaGUgc3RhcnRlZCBkcmF3aW5nIHRyaWFuZ2xlcyB1c2luZyB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5EcmF3IGFuIGVxdWlsYXRlcmFsIHRyaWFuZ2xlIFQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkNvbm5lY3QgdGhlIG1pZHBvaW50cyBvZiBpdHMgc2lkZXMgd2l0aCBsaW5lIHNlZ21lbnRzLiBEZW5vdGUgdGhlIG5ldyBlcXVpbGF0ZXJhbCB0cmlhbmdsZXMgd2l0aCBUMSwgVDIsIFQzIGFuZCBUNCwgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIGZpcnN0IGZpZ3VyZSBiZWxvdy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UmVwZWF0IHRoZSBwcmV2aW91cyBzdGVwIG9uIHRyaWFuZ2xlcyBUMSwgVDIgYW5kIFQzLiBOZXcgdHJpYW5nbGVzIGFyZTogVDExLCBUMTIsIFQxMywgVDE0LCBUMjEsIFQyMiwgVDIzLCBUMjQsIFQzMSwgVDMyLCBUMzMsIFQzNC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Q29udGludWUgdGhlIHByb2NlZHVyZSBvbiBhbGwgdHJpYW5nbGVzIGVuZGluZyBpbiAxLCAyIG9yIDMuIFRoZSByZXN1bHRpbmcgZnJhY3RhbCBpcyBjYWxsZWQgdGhlIFNpZXJwaW5za2kgdHJpYW5nbGUuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TaWVycGluc2tpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NnB4OyB3aWR0aDo0NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5XZSBzYXkgdGhhdCBhIHRyaWFuZ2xlIEEgaXMgbGVhbmluZyBvbiB0aGUgdHJpYW5nbGUgQiBpZiBCIGRvZXMgbm90IGNvbnRhaW4gQSBhbmQgaWYgb25lIGVudGlyZSBzaWRlIG9mIEEgaXMgYSBwYXJ0IG9mIHNvbWUgc2lkZSBvZiBCLiBGb3IgZXhhbXBsZSwgdGhlIHRyaWFuZ2xlIFQyMyBpcyBsZWFuaW5nIG9uIFQyNCBhbmQgVDQsIGJ1dCBub3Qgb24gVDIgb3IgVDMyLiBOb3RlIHRoYXQgQSBsZWFuaW5nIG9uIEIgZG9lcyBub3QgaW1wbHkgdGhhdCBCIGlzIGxlYW5pbmcgb24gQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgdHJpYW5nbGUgQSwgd2hpY2ggaXMgYSBwYXJ0IG9mIHRoZSBTaWVycGluc2tpIHRyaWFuZ2xlLCBmaW5kcyBhbGwgdHJpYW5nbGVzIEIgc3VjaCB0aGF0IEEgaXMgbGVhbmluZyBvbiBCLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyB0aGUgZ2l2ZW4gdHJpYW5nbGUsIGFzIGRlc2NyaWJlZCBhYm92ZS4gVGhlIHNlcXVlbmNlIHdpbGwgY29udGFpbiBiZXR3ZWVuIDIgYW5kIDUwIGNoYXJhY3RlcnMsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYWxsIHRyaWFuZ2xlcyB0aGF0IHRoZSBnaXZlbiB0cmlhbmdsZSBpcyBsZWFuaW5nIG9uLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZSwgaW4gYW55IG9yZGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=