시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 39 13 13 39.394%

문제

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+PGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9XYWMlQzUlODJhd19TaWVycGklQzUlODRza2lcIj5XYWNcdTAxNDJhdyBTaWVycGlcdTAxNDRza2k8XC9hPlx1YjI5NCBcdWQzZjRcdWI3ODBcdWI0ZGMgXHVjMjE4XHVkNTU5XHVjNzkwXHVjNzc0XHViMmU0LiBcdWM1YjRcdWIyOTBcdWIwYTAgXHVhZGY4XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFkZjhcdWI5YWNcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNSBUXHViOTdjIFx1YWRmOFx1YjliMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMGJjXHVhYzAxXHVkNjE1IFx1YmNjMFx1Yzc1OCBcdWM5MTFcdWM4MTBcdWM3NDQgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1Y1x1YjJlNC4gXHVjMGM4XHViODZkXHVhYzhjIFx1YzBkZFx1YWUzNCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgVDEsIFQyLCBUMywgVDRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIFx1YzkxMSBcdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzc0IFx1ZDU3NFx1YjJmOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzA0XHVjNzU4IFx1YjJlOFx1YWNjNFx1Yjk3YyBcdWMwYmNcdWFjMDFcdWQ2MTUgVDEsIFQyLCBUM1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LiBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQwIFQxMSwgVDEyLCBUMTMsIFQxNCwgVDIxLCBUMjIsIFQyMywgVDI0LCBUMzEsIFQzMiwgVDMzLCBUMzRcdWFjMDAgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4xLCAyLCAzXHVjNzNjXHViODVjIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YzBkZFx1YWUzNCBcdWQ1MDRcdWI3OTlcdWQwYzhcdWM3NDQgPGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9TaWVycGluc2tpX3RyaWFuZ2xlXCI+U2llcnBpbnNraSBcdWMwYmNcdWFjMDFcdWQ2MTU8XC9hPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TaWVycGluc2tpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NnB4OyB3aWR0aDo0NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWFjMDFcdWQ2MTUgQlx1YWMwMCBcdWMwYmNcdWFjMDFcdWQ2MTUgQVx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwLCBBXHVjNzU4IFx1ZDU1YyBcdWJjYzAgXHVjODA0XHVjY2I0XHVhYzAwIEJcdWM3NTggXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWM3N2NcdWJkODBcdWM3N2MgXHViNTRjLCBBXHViMjk0IEJcdWM1ZDAgXHVhZTMwXHViMzAwXHVhY2UwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzBiY1x1YWMwMVx1ZDYxNSBUMjNcdWM3NDAgVDI0XHVjNjQwIFQ0XHVjNWQwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFQyXHVjNjQwIFQzMlx1YzVkMFx1YjI5NCBcdWFlMzBcdWIzMDBcdWFjZTAgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC4gKEFcdWFjMDAgQlx1YzVkMCBcdWFlMzBcdWIzMDBcdWFjZTAgXHVjNzg4XHViMmU0XHViMjk0IFx1YjlkMFx1Yzc0MCBCXHVhYzAwIEFcdWM1ZDAgXHVhZTMwXHViMzAwXHVhY2UwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI5ZDBcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+U2llcnBpbnNraSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNzdjXHViZDgwIFx1YzBiY1x1YWMwMVx1ZDYxNSBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgQVx1YWMwMCBcdWFlMzBcdWIzMDBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMwYmNcdWFjMDFcdWQ2MTUgQlx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGJjXHVhYzAxXHVkNjE1IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYmNcdWFjMDFcdWQ2MTUgQVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDAgMlx1YWUwMFx1Yzc5MFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCA1MFx1YWUwMFx1Yzc5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBiY1x1YWMwMVx1ZDYxNSBBXHVhYzAwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjNTQ0XHViYjM0IFx1YzIxY1x1YzExY1x1YjA5OCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IndhY2xhdyIsImRlc2NyaXB0aW9uIjoiPHA+V2FjbGF3IFNpZXJwaW5za2kgd2FzIGEgUG9saXNoIG1hdGhlbWF0aWNpYW4gd2hvIGxpa2VkIHBsYXlpbmcgd2l0aCB0cmlhbmdsZXMuIE9uZSBkYXkgaGUgc3RhcnRlZCBkcmF3aW5nIHRyaWFuZ2xlcyB1c2luZyB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5EcmF3IGFuIGVxdWlsYXRlcmFsIHRyaWFuZ2xlIFQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkNvbm5lY3QgdGhlIG1pZHBvaW50cyBvZiBpdHMgc2lkZXMgd2l0aCBsaW5lIHNlZ21lbnRzLiBEZW5vdGUgdGhlIG5ldyBlcXVpbGF0ZXJhbCB0cmlhbmdsZXMgd2l0aCBUMSwgVDIsIFQzIGFuZCBUNCwgYXMgaWxsdXN0cmF0ZWQgaW4gdGhlIGZpcnN0IGZpZ3VyZSBiZWxvdy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UmVwZWF0IHRoZSBwcmV2aW91cyBzdGVwIG9uIHRyaWFuZ2xlcyBUMSwgVDIgYW5kIFQzLiBOZXcgdHJpYW5nbGVzIGFyZTogVDExLCBUMTIsIFQxMywgVDE0LCBUMjEsIFQyMiwgVDIzLCBUMjQsIFQzMSwgVDMyLCBUMzMsIFQzNC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Q29udGludWUgdGhlIHByb2NlZHVyZSBvbiBhbGwgdHJpYW5nbGVzIGVuZGluZyBpbiAxLCAyIG9yIDMuIFRoZSByZXN1bHRpbmcgZnJhY3RhbCBpcyBjYWxsZWQgdGhlIFNpZXJwaW5za2kgdHJpYW5nbGUuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9TaWVycGluc2tpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NnB4OyB3aWR0aDo0NzVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5XZSBzYXkgdGhhdCBhIHRyaWFuZ2xlIEEgaXMgbGVhbmluZyBvbiB0aGUgdHJpYW5nbGUgQiBpZiBCIGRvZXMgbm90IGNvbnRhaW4gQSBhbmQgaWYgb25lIGVudGlyZSBzaWRlIG9mIEEgaXMgYSBwYXJ0IG9mIHNvbWUgc2lkZSBvZiBCLiBGb3IgZXhhbXBsZSwgdGhlIHRyaWFuZ2xlIFQyMyBpcyBsZWFuaW5nIG9uIFQyNCBhbmQgVDQsIGJ1dCBub3Qgb24gVDIgb3IgVDMyLiBOb3RlIHRoYXQgQSBsZWFuaW5nIG9uIEIgZG9lcyBub3QgaW1wbHkgdGhhdCBCIGlzIGxlYW5pbmcgb24gQS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgdHJpYW5nbGUgQSwgd2hpY2ggaXMgYSBwYXJ0IG9mIHRoZSBTaWVycGluc2tpIHRyaWFuZ2xlLCBmaW5kcyBhbGwgdHJpYW5nbGVzIEIgc3VjaCB0aGF0IEEgaXMgbGVhbmluZyBvbiBCLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIHJlcHJlc2VudGluZyB0aGUgZ2l2ZW4gdHJpYW5nbGUsIGFzIGRlc2NyaWJlZCBhYm92ZS4gVGhlIHNlcXVlbmNlIHdpbGwgY29udGFpbiBiZXR3ZWVuIDIgYW5kIDUwIGNoYXJhY3RlcnMsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYWxsIHRyaWFuZ2xlcyB0aGF0IHRoZSBnaXZlbiB0cmlhbmdsZSBpcyBsZWFuaW5nIG9uLCBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZSwgaW4gYW55IG9yZGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=