시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB267454122.527%

문제

정인이의 경고도 실패로 끝났다. (3029번

정인이는 폭발 계획을 가장 친한 친구 재환이에게만 말했는데, 알고보니 재환이는 상근이의 동생이었던 것이다. 피는 물보다 진하다는 말처럼 재환이는 정인이와의 우정 대신 상근이와의 우애를 선택하기로 했다. 테러 소식을 들은 상근이는 마을회관의 정원 희원에 저수지를 만든 뒤, 강산강의 물을 모두 이 곳에 보관하기로 했었다.

속임수와 나트륨 폭탄 계획이 모두 실패한 정인이는 좀 더 조직적으로 움직이기로 했다.

정인이는 물이 말라 버린 강산강위를 걸으며 자신과 뜻을 함께할 동료를 모으기 시작했다.

상근이도 더이상 방관하지 않기로 했다.

이제 정인이와 상근이의 전쟁이 시작된다.

정인이는 모든 재산을 상근이에게 몰수당했기 때문에, 일단 돈을 먼저 모으기로 했다.

더이상 창영마을에서 안전한 활동을 할 수 없는 정인이는 근처 삼덕마을로 잠시 이동해 돈을 모으려고 한다.

삼덕마을은 크게 3마을로 이루어져 있는데, 가장 윗쪽 마을은 상덕, 중간 마을은 중덕, 아랫마을은 하덕이다. 정인이는 상덕으로 이동해 잠시 아르바이트를 하기로 했다.

주말에는 창영마을과 삼덕마을 주민이 서로 어우러져서 도로에 은을 던지는 행사를 한다. 이 행사는 래은이라고하며, 상근이는 이 행사를 매우 좋아한다. 따라서, 정인이는 자신의 위치를 노출시킬 수 있는 위험을 최소화하려고 한다. 따라서 집에서 TV를 볼 것이다.

안타깝게도 정인이 집의 TV는 스포츠채널만 나온다. 신기하게도 이 채널에선 테니스 경기만 방송한다.

테니스 경기가 시작하기 전에, 선수들은 간단하게 코트 위에서 몸을 풀고 있다. 이때, 방송에선 두 선수의 전적을 화면에 보여준다.

정인이는 아무 생각 없이 TV를 보던 중에, 이 전적이 가끔 올바르지 않은 결과를 포함한다는 것을 알게되었다. 영리한 정인이는 이 사실을 경찰에 알려 불법 스포츠 도박 포상금을 받으려고 한다.

테니스 경기는 세트로 이루어져 있고, 세트는 게임으로 이루어져 있다. 또한 아래와 같은 규칙을 따른다.

1. 세트를 승리하려면, 6게임 또는 그 이상을 이겼고, 적어도 상대편보다 두 게임 이상을 이겨야 한다.

2. 만약 첫 번째 또는 두 번째 세트의 결과가 6:6이라면, 세트의 승자를 가리기 위한 게임 한 판을 진행한다.

3. 2 세트를 먼저 이긴 사람이 테니스 경기의 승자이다.

경기 결과가 올바르려면, 위의 규칙을 따라서 테니스를 진행할 수 있어야 하며, 경기의 승자를 가려낼 수 있어야 한다. 또한, 승자를 가려낸 이후에는 더 이상 게임을 진행하지 않는다.

입력으로 주어진 테니스 경기 결과가 올바른지 아닌지 구하는 프로그램을 작성하시오.

또한, 로저 페더러(입력에선 federer)가 세트에서 패하는 경우는 없다. 따라서, 페더러가 패하는 세트가 있는 경기 결과는 올바르지 않은 것이다.

입력

첫째 줄에는 시합을 펼치는 두 선수의 이름이 공백으로 구분되어 주어진다. 이름은 알파벳 소문자로 이루어져 있으며, 최대 20글자이다. 두 선수의 이름이 같은 경우는 없다.

둘째 줄에는 이전에 두 선수가 서로 대결했던 경기의 수 N이 주어진다. (1 ≤ N ≤ 50)

다음 N개의 줄에는 테니스 경기의 결과가 입력으로 주어진다. 각 결과는 1~5세트 결과를 포함하고, 각 세트의 결과는 공백으로 구분되어져 있다.

세트의 결과는 "A:B" 형식으로 되어있다. A는 입력에서 첫 번째 선수가 승리한 게임의 수와 B는 두 번째 선수가 승리한 게임의 수이며, 두 수 모두 0보다 크거나 같고, 99보다 작거나 같은 자연수이다.

출력

각 경기 결과에 대해서, 올바른 결과이면 "da"를, 그렇지 않다면 "ne"를 출력한다.

예제 입력 1

sampras agassi
6
6:2 6:4
3:6 7:5 2:6
6:5 7:4
7:6 7:6
6:2 3:6
6:2 1:6 6:8

예제 출력 1

da
da
ne
da
ne
da

예제 입력 2

federer roddick
1
2:6 4:6

예제 출력 2

ne
W3sicHJvYmxlbV9pZCI6IjMwMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxNGNcdWIyYzhcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWFjYmRcdWFjZTBcdWIzYzQgXHVjMmU0XHVkMzI4XHViODVjIFx1YjA1ZFx1YjBhY1x1YjJlNC4gKDxhIGhyZWY9XCJodHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC9wcm9ibGVtXC8zMDI5XCI+MzAyOVx1YmM4ODxcL2E+KSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVkM2VkXHViYzFjIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjZTVjXHVkNTVjIFx1Y2U1Y1x1YWQ2YyBcdWM3YWNcdWQ2NThcdWM3NzRcdWM1ZDBcdWFjOGNcdWI5Y2MgXHViOWQwXHVkNTg4XHViMjk0XHViMzcwLCBcdWM1NGNcdWFjZTBcdWJjZjRcdWIyYzggXHVjN2FjXHVkNjU4XHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWIzZDlcdWMwZGRcdWM3NzRcdWM1YzhcdWIzNTggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ1M2NcdWIyOTQgXHViYjNjXHViY2Y0XHViMmU0IFx1YzljNFx1ZDU1OFx1YjJlNFx1YjI5NCBcdWI5ZDBcdWNjOThcdWI3ZmMgXHVjN2FjXHVkNjU4XHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzY0MFx1Yzc1OCBcdWM2YjBcdWM4MTUgXHViMzAwXHVjMmUwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MFx1Yzc1OCBcdWM2YjBcdWM1NjBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVkMTRjXHViN2VjIFx1YzE4Y1x1YzJkZFx1Yzc0NCBcdWI0ZTRcdWM3NDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjljOFx1Yzc0NFx1ZDY4Y1x1YWQwMFx1Yzc1OCBcdWM4MTVcdWM2ZDAgXHVkNzZjXHVjNmQwXHVjNWQwIFx1YzgwMFx1YzIxOFx1YzljMFx1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHViNGE0LCBcdWFjMTVcdWMwYjBcdWFjMTVcdWM3NTggXHViYjNjXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWM3NzQgXHVhY2YzXHVjNWQwIFx1YmNmNFx1YWQwMFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4ZFx1Yzc4NFx1YzIxOFx1YzY0MCBcdWIwOThcdWQyYjhcdWI5NjggXHVkM2VkXHVkMGM0IFx1YWNjNFx1ZDY4ZFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjMmU0XHVkMzI4XHVkNTVjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM4ODAgXHViMzU0IFx1Yzg3MFx1YzljMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHViYjNjXHVjNzc0IFx1YjlkMFx1Yjc3YyBcdWJjODRcdWI5YjAgXHVhYzE1XHVjMGIwXHVhYzE1XHVjNzA0XHViOTdjIFx1YWM3OFx1YzczY1x1YmE3MCBcdWM3OTBcdWMyZTBcdWFjZmMgXHViNzNiXHVjNzQ0IFx1ZDU2OFx1YWVkOFx1ZDU2MCBcdWIzZDlcdWI4Y2NcdWI5N2MgXHViYWE4XHVjNzNjXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViM2M0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWJjMjlcdWFkMDBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YzY0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjODA0XHVjN2MxXHVjNzc0IFx1YzJkY1x1Yzc5MVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM3YWNcdWMwYjBcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YmFiMFx1YzIxOFx1YjJmOVx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3Y1x1YjJlOCBcdWIzYzhcdWM3NDQgXHViYTNjXHVjODAwIFx1YmFhOFx1YzczY1x1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjM1NFx1Yzc3NFx1YzBjMSBcdWNjM2RcdWM2MDFcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHVjNTQ4XHVjODA0XHVkNTVjIFx1ZDY1Y1x1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVhZGZjXHVjYzk4IFx1YzBiY1x1YjM1NVx1YjljOFx1Yzc0NFx1Yjg1YyBcdWM3YTBcdWMyZGMgXHVjNzc0XHViM2Q5XHVkNTc0IFx1YjNjOFx1Yzc0NCBcdWJhYThcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYmNcdWIzNTVcdWI5YzhcdWM3NDRcdWM3NDAgXHVkMDZjXHVhYzhjIDNcdWI5YzhcdWM3NDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhYzAwXHVjN2E1IFx1YzcxN1x1Y2FiZCBcdWI5YzhcdWM3NDRcdWM3NDAgXHVjMGMxXHViMzU1LCBcdWM5MTFcdWFjMDQgXHViOWM4XHVjNzQ0XHVjNzQwIFx1YzkxMVx1YjM1NSwgXHVjNTQ0XHViN2FiXHViOWM4XHVjNzQ0XHVjNzQwIFx1ZDU1OFx1YjM1NVx1Yzc3NFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1YzBjMVx1YjM1NVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NzQgXHVjN2EwXHVjMmRjIFx1YzU0NFx1Yjk3NFx1YmMxNFx1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWI5ZDBcdWM1ZDBcdWIyOTQgXHVjYzNkXHVjNjAxXHViOWM4XHVjNzQ0XHVhY2ZjIFx1YzBiY1x1YjM1NVx1YjljOFx1Yzc0NCBcdWM4ZmNcdWJiZmNcdWM3NzQgXHVjMTFjXHViODVjIFx1YzViNFx1YzZiMFx1YjdlY1x1YzgzOFx1YzExYyBcdWIzYzRcdWI4NWNcdWM1ZDAgXHVjNzQwXHVjNzQ0IFx1YjM1OFx1YzljMFx1YjI5NCBcdWQ1ODlcdWMwYWNcdWI5N2MgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVkNTg5XHVjMGFjXHViMjk0IFx1Yjc5OFx1Yzc0MFx1Yzc3NFx1Yjc3Y1x1YWNlMFx1ZDU1OFx1YmE3MCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWQ1ODlcdWMwYWNcdWI5N2MgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIxNzhcdWNkOWNcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWQ1ZDhcdWM3NDQgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzlkMVx1YzVkMFx1YzExYyBUVlx1Yjk3YyBcdWJjZmMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVjODE1XHVjNzc4XHVjNzc0IFx1YzlkMVx1Yzc1OCBUVlx1YjI5NCBcdWMyYTRcdWQzZWNcdWNlMjBcdWNjNDRcdWIxMTBcdWI5Y2MgXHViMDk4XHVjNjI4XHViMmU0LiBcdWMyZTBcdWFlMzBcdWQ1NThcdWFjOGNcdWIzYzQgXHVjNzc0IFx1Y2M0NFx1YjExMFx1YzVkMFx1YzEyMCBcdWQxNGNcdWIyYzhcdWMyYTQgXHVhY2JkXHVhZTMwXHViOWNjIFx1YmMyOVx1YzFhMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHViMmM4XHVjMmE0IFx1YWNiZFx1YWUzMFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwLCBcdWMxMjBcdWMyMThcdWI0ZTRcdWM3NDAgXHVhYzA0XHViMmU4XHVkNTU4XHVhYzhjIFx1Y2Y1NFx1ZDJiOCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHViYWI4XHVjNzQ0IFx1ZDQ4MFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYzI5XHVjMWExXHVjNWQwXHVjMTIwIFx1YjQ1MCBcdWMxMjBcdWMyMThcdWM3NTggXHVjODA0XHVjODAxXHVjNzQ0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWJjZjRcdWM1ZWNcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWJiMzQgXHVjMGRkXHVhYzAxIFx1YzVjNlx1Yzc3NCBUVlx1Yjk3YyBcdWJjZjRcdWIzNTggXHVjOTExXHVjNWQwLCBcdWM3NzQgXHVjODA0XHVjODAxXHVjNzc0IFx1YWMwMFx1YjA1NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC4gXHVjNjAxXHViOWFjXHVkNTVjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YWNiZFx1Y2MzMFx1YzVkMCBcdWM1NGNcdWI4MjQgXHViZDg4XHViYzk1IFx1YzJhNFx1ZDNlY1x1Y2UyMCBcdWIzYzRcdWJjMTUgXHVkM2VjXHVjMGMxXHVhZTA4XHVjNzQ0IFx1YmMxYlx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YjJjOFx1YzJhNCBcdWFjYmRcdWFlMzBcdWIyOTQgXHVjMTM4XHVkMmI4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWFjOGNcdWM3ODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MS4gXHVjMTM4XHVkMmI4XHViOTdjIFx1YzJiOVx1YjlhY1x1ZDU1OFx1YjgyNFx1YmE3NCwgNlx1YWM4Y1x1Yzc4NCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc0NCBcdWM3NzRcdWFjYmNcdWFjZTAsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWMwYzFcdWIzMDBcdWQzYjhcdWJjZjRcdWIyZTQgXHViNDUwIFx1YWM4Y1x1Yzc4NCBcdWM3NzRcdWMwYzFcdWM3NDQgXHVjNzc0XHVhY2E4XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Mi4gXHViOWNjXHVjNTdkIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViNjEwXHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMTM4XHVkMmI4XHVjNzU4IFx1YWNiMFx1YWNmY1x1YWMwMCA2OjZcdWM3NzRcdWI3N2NcdWJhNzQsIFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWMyYjlcdWM3OTBcdWI5N2MgXHVhYzAwXHViOWFjXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFjOGNcdWM3ODQgXHVkNTVjIFx1ZDMxMFx1Yzc0NCBcdWM5YzRcdWQ1ODlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjMuIDIgXHVjMTM4XHVkMmI4XHViOTdjIFx1YmEzY1x1YzgwMCBcdWM3NzRcdWFlMzQgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDE0Y1x1YjJjOFx1YzJhNCBcdWFjYmRcdWFlMzBcdWM3NTggXHVjMmI5XHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYmRcdWFlMzAgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3NFx1YjgyNFx1YmE3NCwgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkMTRjXHViMmM4XHVjMmE0XHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzJiOVx1Yzc5MFx1Yjk3YyBcdWFjMDBcdWI4MjRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjMmI5XHVjNzkwXHViOTdjIFx1YWMwMFx1YjgyNFx1YjBiOCBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjOWM0XHVkNTg5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQxNGNcdWIyYzhcdWMyYTQgXHVhY2JkXHVhZTMwIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzhcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWI2MTBcdWQ1NWMsIFx1Yjg1Y1x1YzgwMCBcdWQzOThcdWIzNTRcdWI3ZWMoXHVjNzg1XHViODI1XHVjNWQwXHVjMTIwIGZlZGVyZXIpXHVhYzAwIFx1YzEzOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWQzMjhcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWQzOThcdWIzNTRcdWI3ZWNcdWFjMDAgXHVkMzI4XHVkNTU4XHViMjk0IFx1YzEzOFx1ZDJiOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVhZTMwIFx1YWNiMFx1YWNmY1x1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRjXHVkNTY5XHVjNzQ0IFx1ZDNiY1x1Y2U1OFx1YjI5NCBcdWI0NTAgXHVjMTIwXHVjMjE4XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjZDVjXHViMzAwIDIwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjMTIwXHVjMjE4XHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHViNDUwIFx1YzEyMFx1YzIxOFx1YWMwMCBcdWMxMWNcdWI4NWMgXHViMzAwXHVhY2IwXHVkNTg4XHViMzU4IFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHViMmM4XHVjMmE0IFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YWNiMFx1YWNmY1x1YjI5NCAxfjVcdWMxMzhcdWQyYjggXHVhY2IwXHVhY2ZjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCwgXHVhYzAxIFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWIyOTQgJnF1b3Q7QTpCJnF1b3Q7IFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIEFcdWIyOTQgXHVjNzg1XHViODI1XHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMTIwXHVjMjE4XHVhYzAwIFx1YzJiOVx1YjlhY1x1ZDU1YyBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMjE4XHVjNjQwIEJcdWIyOTQgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMxMjBcdWMyMThcdWFjMDAgXHVjMmI5XHViOWFjXHVkNTVjIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWMyMThcdWM3NzRcdWJhNzAsIFx1YjQ1MCBcdWMyMTggXHViYWE4XHViNDUwIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgOTlcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YWNiZFx1YWUzMCBcdWFjYjBcdWFjZmNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhY2IwXHVhY2ZjXHVjNzc0XHViYTc0ICZxdW90O2RhJnF1b3Q7XHViOTdjLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0ICZxdW90O25lJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVEVOSVMiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIEJvcmtvJiMzOTtzIHNlY29uZCBwbGFuIG9mIHRha2luZyBvdmVyIHRoZSB2aWxsYWdlIGZlbGwgdGhyb3VnaCAoYmVjYXVzZSBNaXJrbyYjMzk7cyBicm90aGVyIFN0YW5rbyBkcmFuayBhbGwgdGhlIHdhdGVyKSwgeW91bmcgWnZvbmtvIGRlY2lkZWQgdG8gcmVsYXggd2l0aCBzcG9ydHMuIEZvciB0aGlzIHB1cnBvc2UgaGUgc3RvY2tlZCB1cCBvbiBjYXJyb3QganVpY2UgYW5kIHBlYW51dHMsIGFuZCBkaXZlZCBvbnRvIHRoZSBjb3VjaCwgcmVhZHkgdG8gd2F0Y2ggdGhlIG5leHQgdGVubmlzIG1hdGNoIG9uIHRlbGV2aXNpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoaWxlIHRoZSB0d28gcGxheWVycyBhcmUgd2FybWluZyB1cCwgdGhlaXIgc3RhdGlzdGljcyBwb3AgdXAgb24gdGhlIHNjcmVlbi4gWnZvbmtvIG5vdGljZWQgdGhhdCB0aGUgbWF0Y2ggaGlzdG9yeSBvZiB0aGUgcGxheWVycyBjb250YWluZWQgaW52YWxpZCByZXN1bHRzLiBIZSBoYWQgYSBicmlsbGlhbnQgaWRlYSB3aGVyZSB5b3Ugd3JpdGUgaGltIGEgcHJvZ3JhbSB0aGF0IGNoZWNrcyB0aGUgdmFsaWRpdHkgb2YgcmVzdWx0cywgd2hpY2ggaGUgd2lsbCB0aGVuIHNlbGwgdG8gdGhlIHJlY29yZCBrZWVwZXJzIGFuZCBlbmpveSBhIGxlaXN1cmVseSBsaWZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHRlbm5pcyBtYXRjaCBjb25zaXN0cyBvZiBzZXRzLCBlYWNoIHNldCBjb25zaXN0aW5nIG9mIGdhbWVzLiBUaGUgZm9sbG93aW5nIHJ1bGVzIGFwcGx5OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkEgcGxheWVyIHdpbnMgYSBzZXQgaWYgaGUgaGFzIDYgb3IgbW9yZSBnYW1lcyBhbmQgYXQgbGVhc3QgdHdvIGdhbWVzIG1vcmUgdGhhbiBoaXMgb3Bwb25lbnQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkFkZGl0aW9uYWxseSwgaWYgdGhlIHJlc3VsdCBpcyA2OjYgaW4gdGhlIGZpcnN0IG9yIHNlY29uZCBzZXQgKGJ1dCBub3QgdGhlIHRoaXJkIHNldCksIGEgc2luZ2xlIGZpbmFsIGdhbWUgaXMgcGxheWVkIHRvIGRldGVybWluZSB0aGUgd2lubmVyIG9mIHRoZSBzZXQgKHRoZSB0aWUtYnJlYWsgZ2FtZSkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBtYXRjaCBlbmRzIHdoZW4gZWl0aGVyIHBsYXllciBoYXMgd29uIDIgc2V0cy4gVGhhdCBwbGF5ZXIgaXMgdGhlIHdpbm5lci4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIG1hdGNoIHJlc3VsdCBpcyB2YWxpZCBpZiBhIG1hdGNoIGNvdWxkIGhhdmUgYmVlbiBwbGF5ZWQgYnkgdGhlIGFib3ZlIHJ1bGVzIGFuZCBlbmRlZCBpbiB0aGUgcmVzdWx0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BZGRpdGlvbmFsbHksIGlmIG9uZSBvZiB0aGUgcGxheWVycyBpcyBSb2dlciBGZWRlcmVyIChkZXNpZ25hdGVkIGFzICZxdW90O2ZlZGVyZXImcXVvdDsgaW4gdGhlIGlucHV0KSwgdGhlbiBhIHJlc3VsdCBpbiB3aGljaCBoZSBoYXMgbG9zdCBhIHNldCBjYW4mIzM5O3QgYmUgdmFsaWQgKFp2b25rbyBrbm93cyBGZWRlcmVyIGlzIGZyb20gb3V0ZXIgc3BhY2UpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjaGVja3MgdGhlIHZhbGlkaXR5IG9mIGFsbCBtYXRjaGVzIGJldHdlZW4gdHdvIHBsYXllcnMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgbmFtZXMgb2YgdGhlIHR3byBwbGF5ZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gQm90aCBuYW1lcyB3aWxsIGJlIHN0cmluZ3Mgb2YgYXQgbW9zdCAyMCBsb3dlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldC4gVGhlIG5hbWVzIHdpbGwgYmUgZGlmZmVyZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwKSwgaG93IG1hbnkgbWF0Y2hlcyB0aGUgdHdvIHBsYXllcnMgaGF2ZSBwbGF5ZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRoZSByZXN1bHQgb2YgYSBzaW5nbGUgbWF0Y2gsIGNvbXBvc2VkIG9mIHRoZSByZXN1bHRzIG9mIGEgbnVtYmVyIG9mIHNldHMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIEVhY2ggbWF0Y2ggcmVzdWx0IHdpbGwgY29udGFpbiBiZXR3ZWVuIDEgYW5kIDUgc2V0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzZXQgaXMgZ2l2ZW4gaW4gdGhlIGZvcm1hdCAmcXVvdDtBOkImcXVvdDssIHdoZXJlIEEgYW5kIEIgYXJlIGdhbWVzIHdvbiBieSBlYWNoIHBsYXllci4gVGhlc2UgbnVtYmVycyB3aWxsIGJlIGludGVnZXJzIGJldHdlZW4gMCBhbmQgOTkgKGluY2x1c2l2ZSkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbWF0Y2gsIGluIHRoZSBvcmRlciB0aGV5JiMzOTtyZSBnaXZlbiBpbiB0aGUgaW5wdXQsIG91dHB1dCAmcXVvdDtkYSZxdW90OyBpZiB0aGUgcmVzdWx0IGlzIHZhbGlkLCBvciAmcXVvdDtuZSZxdW90OyBpZiBpdCBpc24mIzM5O3QuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #5 3번