시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 14 14 35.897%

문제

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+U2llcnBpbnNraSBcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNzdjXHViZDgwIFx1YzBiY1x1YWMwMVx1ZDYxNSBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBBXHVhYzAwIFx1YWUzMFx1YjMwMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YzBiY1x1YWMwMVx1ZDYxNSBCXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYmNcdWFjMDFcdWQ2MTUgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzBiY1x1YWMwMVx1ZDYxNSBBXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCAyXHVhZTAwXHVjNzkwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDUwXHVhZTAwXHVjNzkwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGJjXHVhYzAxXHVkNjE1IEFcdWFjMDAgXHVhZTMwXHViMzAwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBcdWM1NDRcdWJiMzQgXHVjMjFjXHVjMTFjXHViMDk4IFx1YzBjMVx1YWQwMFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTU4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoid2FjbGF3IiwiZGVzY3JpcHRpb24iOiI8cD5XYWNsYXcgU2llcnBpbnNraSB3YXMgYSBQb2xpc2ggbWF0aGVtYXRpY2lhbiB3aG8gbGlrZWQgcGxheWluZyB3aXRoIHRyaWFuZ2xlcy4gT25lIGRheSBoZSBzdGFydGVkIGRyYXdpbmcgdHJpYW5nbGVzIHVzaW5nIHRoZSBmb2xsb3dpbmcgcHJvY2VkdXJlOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkRyYXcgYW4gZXF1aWxhdGVyYWwgdHJpYW5nbGUgVC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Q29ubmVjdCB0aGUgbWlkcG9pbnRzIG9mIGl0cyBzaWRlcyB3aXRoIGxpbmUgc2VnbWVudHMuIERlbm90ZSB0aGUgbmV3IGVxdWlsYXRlcmFsIHRyaWFuZ2xlcyB3aXRoIFQxLCBUMiwgVDMgYW5kIFQ0LCBhcyBpbGx1c3RyYXRlZCBpbiB0aGUgZmlyc3QgZmlndXJlIGJlbG93LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5SZXBlYXQgdGhlIHByZXZpb3VzIHN0ZXAgb24gdHJpYW5nbGVzIFQxLCBUMiBhbmQgVDMuIE5ldyB0cmlhbmdsZXMgYXJlOiBUMTEsIFQxMiwgVDEzLCBUMTQsIFQyMSwgVDIyLCBUMjMsIFQyNCwgVDMxLCBUMzIsIFQzMywgVDM0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5Db250aW51ZSB0aGUgcHJvY2VkdXJlIG9uIGFsbCB0cmlhbmdsZXMgZW5kaW5nIGluIDEsIDIgb3IgMy4gVGhlIHJlc3VsdGluZyBmcmFjdGFsIGlzIGNhbGxlZCB0aGUgU2llcnBpbnNraSB0cmlhbmdsZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NpZXJwaW5za2kucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg2cHg7IHdpZHRoOjQ3NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0IGEgdHJpYW5nbGUgQSBpcyBsZWFuaW5nIG9uIHRoZSB0cmlhbmdsZSBCIGlmIEIgZG9lcyBub3QgY29udGFpbiBBIGFuZCBpZiBvbmUgZW50aXJlIHNpZGUgb2YgQSBpcyBhIHBhcnQgb2Ygc29tZSBzaWRlIG9mIEIuIEZvciBleGFtcGxlLCB0aGUgdHJpYW5nbGUgVDIzIGlzIGxlYW5pbmcgb24gVDI0IGFuZCBUNCwgYnV0IG5vdCBvbiBUMiBvciBUMzIuIE5vdGUgdGhhdCBBIGxlYW5pbmcgb24gQiBkb2VzIG5vdCBpbXBseSB0aGF0IEIgaXMgbGVhbmluZyBvbiBBLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYSB0cmlhbmdsZSBBLCB3aGljaCBpcyBhIHBhcnQgb2YgdGhlIFNpZXJwaW5za2kgdHJpYW5nbGUsIGZpbmRzIGFsbCB0cmlhbmdsZXMgQiBzdWNoIHRoYXQgQSBpcyBsZWFuaW5nIG9uIEIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMgcmVwcmVzZW50aW5nIHRoZSBnaXZlbiB0cmlhbmdsZSwgYXMgZGVzY3JpYmVkIGFib3ZlLiBUaGUgc2VxdWVuY2Ugd2lsbCBjb250YWluIGJldHdlZW4gMiBhbmQgNTAgY2hhcmFjdGVycywgaW5jbHVzaXZlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhbGwgdHJpYW5nbGVzIHRoYXQgdGhlIGdpdmVuIHRyaWFuZ2xlIGlzIGxlYW5pbmcgb24sIGVhY2ggb24gYSBzZXBhcmF0ZSBsaW5lLCBpbiBhbnkgb3JkZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==