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

문제

단어가 N개 있는 데이터베이스가 있다.

이 데이터베이스에서 어떤 단어를 찾을 때 사용하는 알고리즘은 상당히 원시적이다.

이 알고리즘은 단어 W와 데이터베이스에 있는 단어를 하나씩 비교한다. 단어를 비교할 때는, 각 단어의 가장 앞에서부터 다른 문자가 나오거나, 한 단어의 끝이 나올 때 까지 하나씩 비교한다. 만약, 단어 W를 찾으면 이 알고리즘은 그 즉시 종료된다.

단어의 길이는 단어를 검색하기 전에 알 수 없으므로, 마지막 글자도 비교를 해야 단어가 끝났다는 것을 알게 된다. 즉, abc와 abcd가 있을 때, abc의 4번째 글자와 abcd의 4번째 글자를 비교할 때 단어가 서로 다르다는 것을 알 수 있는 것이다. 마찬가지로 단어가 같은 것도 마지막 글자 다음 글자를 비교해야 알 수 있다. abc와 abc가 있을 때, abc의 4번째 글자와 abc의 4번째 글자가 모두 없는 것으로 같으므로 단어를 찾았다는 뜻이다.

단어 목록이 주어지고, 검색하려고 하는 단어가 주어졌을 때, 몇 번 비교만에 단어를 찾을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 30,000)

다음 N개의 줄에는 데이터베이스에 있는 단어가 주어진다. 단어를 검색할 때, 입력으로 주어진 단어 순서를 그대로 사용해야 한다. 또한, 모든 단어는 다르다.

다음 줄에는 검색하려고 하는 단어의 개수 Q가 주어진다. (1 ≤ Q ≤ 30,000)

다음 Q개 줄에는 검색하려고 하는 단어가 주어진다.

모든 단어는 알파벳 소문자로 이루어져 있고, 길이는 30보다 작다.

출력

Q개 줄에 걸쳐, 각 단어를 검색하는데 필요한 비교의 수를 출력한다.

예제 입력 1

5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija

예제 출력 1

12
10
16
7

예제 입력 2

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

예제 출력 2

8
29
14

krampus를 검색하려면 데이터베이스에 있는 단어의 첫 번째 글자만 비교하면 되므로 8번만 비교하면 된다. 

malnar를 검색하려면, 처음 3단어는 3번, 뒤의 5단어는 4번 검색하면 되므로 29번 비교하면 된다.

majmun을 검색하려면, 14번 검색하면 된다. 첫 번째 단어 "majmunica"와 7번 비교를 하고, 길이가 다르므로 다음 단어와 비교한다. 다음 단어에서 7번 비교를 하면 되므로 14번이다. 단어를 찾은 후에는 더이상 검색을 하지 않으므로 더 검색할 단어는 없다.

W3sicHJvYmxlbV9pZCI6IjI5OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjQgXHVhYzgwXHVjMGM5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZThcdWM1YjRcdWFjMDAgTlx1YWMxYyBcdWM3ODhcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwXHViY2EwXHVjNzc0XHVjMmE0XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNFx1YzVkMFx1YzExYyBcdWM1YjRcdWI1YTQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MzZVx1Yzc0NCBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0MCBcdWMwYzFcdWIyZjlcdWQ3ODggXHVjNmQwXHVjMmRjXHVjODAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YjJlOFx1YzViNCBXXHVjNjQwIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWJlNDRcdWFkNTBcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWFjMDEgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWIwOThcdWM2MjRcdWFjNzBcdWIwOTgsIFx1ZDU1YyBcdWIyZThcdWM1YjRcdWM3NTggXHViMDVkXHVjNzc0IFx1YjA5OFx1YzYyYyBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViMmU4XHVjNWI0IFdcdWI5N2MgXHVjYzNlXHVjNzNjXHViYTc0IFx1Yzc3NCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDAgXHVhZGY4IFx1Yzk4OVx1YzJkYyBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNTRjIFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDBcdWM3OTBcdWIzYzQgXHViZTQ0XHVhZDUwXHViOTdjIFx1ZDU3NFx1YzU3YyBcdWIyZThcdWM1YjRcdWFjMDAgXHViMDVkXHViMGFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM5ODksIGFiY1x1YzY0MCBhYmNkXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIGFiY1x1Yzc1OCA0XHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YzY0MCBhYmNkXHVjNzU4IDRcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU2MCBcdWI1NGMgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjIFx1YjJlOFx1YzViNFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhYzgzXHViM2M0IFx1YjljOFx1YzljMFx1YjljOSBcdWFlMDBcdWM3OTAgXHViMmU0XHVjNzRjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWJlNDRcdWFkNTBcdWQ1NzRcdWM1N2MgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIGFiY1x1YzY0MCBhYmNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YywgYWJjXHVjNzU4IDRcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVjNjQwIGFiY1x1Yzc1OCA0XHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjNWM2XHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFjMTlcdWM3M2NcdWJiYzBcdWI4NWMgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2MzZVx1YzU1OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWFjODBcdWMwYzlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhODcgXHViYzg4IFx1YmU0NFx1YWQ1MFx1YjljY1x1YzVkMCBcdWIyZThcdWM1YjRcdWI5N2MgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4XHVjNWI0XHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU2MCBcdWI1NGMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMmU4XHVjNWI0IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0XHViMjk0IFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjODBcdWMwYzlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMTggUVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUSAmbGU7IDMwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWM4MFx1YzBjOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAzMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UVx1YWMxYyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWFjMDEgXHViMmU4XHVjNWI0XHViOTdjIFx1YWM4MFx1YzBjOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViZTQ0XHVhZDUwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPmtyYW1wdXNcdWI5N2MgXHVhYzgwXHVjMGM5XHVkNTU4XHViODI0XHViYTc0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YmNhMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViOWNjIFx1YmU0NFx1YWQ1MFx1ZDU1OFx1YmE3NCBcdWI0MThcdWJiYzBcdWI4NWMgOFx1YmM4OFx1YjljYyBcdWJlNDRcdWFkNTBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5tYWxuYXJcdWI5N2MgXHVhYzgwXHVjMGM5XHVkNTU4XHViODI0XHViYTc0LCBcdWNjOThcdWM3NGMgM1x1YjJlOFx1YzViNFx1YjI5NCAzXHViYzg4LCBcdWI0YTRcdWM3NTggNVx1YjJlOFx1YzViNFx1YjI5NCA0XHViYzg4IFx1YWM4MFx1YzBjOVx1ZDU1OFx1YmE3NCBcdWI0MThcdWJiYzBcdWI4NWMgMjlcdWJjODggXHViZTQ0XHVhZDUwXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+bWFqbXVuXHVjNzQ0IFx1YWM4MFx1YzBjOVx1ZDU1OFx1YjgyNFx1YmE3NCwgMTRcdWJjODggXHVhYzgwXHVjMGM5XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWIyZThcdWM1YjQgJnF1b3Q7bWFqbXVuaWNhJnF1b3Q7XHVjNjQwIDdcdWJjODggXHViZTQ0XHVhZDUwXHViOTdjIFx1ZDU1OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YjJlNFx1Yjk3NFx1YmJjMFx1Yjg1YyBcdWIyZTRcdWM3NGMgXHViMmU4XHVjNWI0XHVjNjQwIFx1YmU0NFx1YWQ1MFx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIFx1YjJlOFx1YzViNFx1YzVkMFx1YzExYyA3XHViYzg4IFx1YmU0NFx1YWQ1MFx1Yjk3YyBcdWQ1NThcdWJhNzQgXHViNDE4XHViYmMwXHViODVjIDE0XHViYzg4XHVjNzc0XHViMmU0LiBcdWIyZThcdWM1YjRcdWI5N2MgXHVjYzNlXHVjNzQwIFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWIzNTRcdWM3NzRcdWMwYzEgXHVhYzgwXHVjMGM5XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJiYzBcdWI4NWMgXHViMzU0IFx1YWM4MFx1YzBjOVx1ZDU2MCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI5OTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCQVpBIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbG9uZ2VzdCBjb21tb24gcHJlZml4IG9mIHR3byB3b3JkcyBpcyB0aGUgbG9uZ2VzdCB3b3JkIHRoYXQgYm90aCB3b3JkcyBzdGFydCB3aXRoLiBGb3IgZXhhbXBsZSwgdGhlIGxvbmdlc3QgY29tbW9uIHByZWZpeCBvZiB0aGUgd29yZHMgJnF1b3Q7aWRlbnRpdHkmcXVvdDsgYW5kICZxdW90O2lkZWFsaXN0aWMmcXVvdDsgaXMgdGhlIHdvcmQgJnF1b3Q7aWRlJnF1b3Q7LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGRhdGFiYXNlIGNvbnRhaW5zIE4gd29yZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBhbGdvcml0aG0gdG8gc2VhcmNoIGZvciBhIHF1ZXJ5IHdvcmQgVyBpbiB0aGUgZGF0YWJhc2UgaXMgcHJpbWl0aXZlLiBJdCBjb21wYXJlcyB0aGUgd29yZCBXIG9uZSBieSBvbmUgd2l0aCBlYWNoIHdvcmQgaW4gdGhlIGRhdGFiYXNlLiBUd28gd29yZHMgYXJlIGNvbXBhcmVkIGxldHRlciBieSBsZXR0ZXIgdW50aWwgYSBsZXR0ZXIgaW4gd2hpY2ggdGhleSBkaWZmZXIgaXMgZm91bmQgb3IgdW50aWwgdGhlIGVuZCBvZiBvbmUgb2YgdGhlIHdvcmRzIGlzIHJlYWNoZWQgKGl0IGlzIHRoZW4gZXN0YWJsaXNoZWQgZWl0aGVyIHRoYXQgdGhlIHdvcmRzIGFyZSBlcXVhbCBvciB0aGF0IG9uZSBpcyBsb25nZXIgdGhhbiB0aGUgb3RoZXIpLiBXaGVuIHRoZSBhbGdvcml0aG0gZmluZHMgdGhlIHdvcmQgVyBpbiB0aGUgZGF0YWJhc2UsIGl0IHRlcm1pbmF0ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFuYWx5c2luZyB0aGUgYWxnb3JpdGhtIHNob3dzIHRoYXQgdGhlIG51bWJlciBvZiBzdGVwcyBuZWVkZWQgdG8gZmluZCBhIHdvcmQgVyBpcyBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHdvcmRzIFcgaXMgY29tcGFyZWQgdG8sIHBsdXMgdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiB0aGUgbG9uZ2VzdCBjb21tb24gcHJlZml4ZXMgb2YgVyBhbmQgZWFjaCBvZiB0aGUgd29yZHMgaXQgd2FzIGNvbXBhcmVkIHRvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2Ygc3RlcHMgdGhlIGFsZ29yaXRobSB1c2VzIHRvIGZpbmQgZWFjaCBvZiB0aGUgUSBxdWVyeSB3b3Jkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAzMDAwMCksIHRoZSBudW1iZXIgb2Ygd29yZHMgaW4gdGhlIGRhdGFiYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHNpbmdsZSB3b3JkIGZyb20gdGhlIGRhdGFiYXNlLiBUaGUgd29yZHMgYXJlIGdpdmVuIGluIHRoZSBvcmRlciB0aGUgYWxnb3JpdGhtIGNvbXBhcmVzIHRoZW0gdG8gYSBxdWVyeSB3b3JkLiBBbGwgd29yZHMgaW4gdGhlIGRhdGFiYXNlIHdpbGwgYmUgZGlzdGluY3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIFEgKDEgJmxlOyBRICZsZTsgMzAwMDApLCB0aGUgbnVtYmVyIG9mIHdvcmRzIHNlYXJjaGVkIGZvci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFEgbGluZXMgY29udGFpbnMgYSBzaW5nbGUgcXVlcnkgd29yZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIHdvcmRzIGluIHRoZSBpbnB1dCB3aWxsIGJlIHN0cmluZ3Mgb2YgbGVzcyB0aGFuIDMwIGxvd2VyY2FzZSBsZXR0ZXJzIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciBwZXIgbGluZSBmb3IgZWFjaCBxdWVyeSB3b3JkLCB0aGUgbnVtYmVyIG9mIHN0ZXBzIHRoZSBhbGdvcml0aG0gdXNlcyB3aGVuIHNlYXJjaGluZyBmb3IgdGhlIHdvcmQuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBzZWNvbmQgZXhhbXBsZSwgdGhlIG51bWJlciBvZiBzdGVwcyB0byBzZWFyY2ggZm9yIHRoZSB3b3JkICZxdW90O2tyYW1wdXMmcXVvdDsgaXMgOCBiZWNhdXNlIHRoZSBhbGdvcml0aG0gb25seSBuZWVkcyB0byBjb21wYXJlIGl0cyBmaXJzdCBsZXR0ZXIgdG8gZWFjaCB3b3JkIGluIHRoZSBkYXRhYmFzZS48XC9wPlxyXG5cclxuPHA+V2hlbiBzZWFyY2hpbmcgZm9yIHRoZSB3b3JkICZxdW90O21hbG5hciZxdW90Oywgd2UgbmVlZCB0aHJlZSBzdGVwcyBmb3IgZWFjaCBvZiB0aGUgZmlyc3QgdGhyZWUgd29yZHMsIGFuZCBmb3VyIHN0ZXBzIGZvciBlYWNoIG9mIHRoZSByZW1haW5pbmcgZml2ZSB3b3JkcywgZm9yIGEgdG90YWwgb2YgMjkgc3RlcHMuPFwvcD5cclxuXHJcbjxwPlRvIGZpbmQgdGhlIHdvcmQgJnF1b3Q7bWFqbXVuJnF1b3Q7IHdlIHVzZSBhIHRvdGFsIG9mIDE0IHN0ZXBzLiBGb3IgdGhlIGZpcnN0IHdvcmQgaW4gdGhlIGRhdGFiYXNlLCB3ZSBoYXZlIHNpeCBzdWNjZXNzZnVsIGNvbXBhcmlzb25zIGFuZCBvbmUgc3RlcCBpbiB3aGljaCB3ZSBkZXRlcm1pbmUgdGhhdCB0aGUgd29yZCAmcXVvdDttYWptdW5pY2EmcXVvdDsgaXMgbG9uZ2VyIHRoYW4gdGhlIHF1ZXJ5IHdvcmQuIEZvciB0aGUgc2Vjb25kIHdvcmQsIHdlIGFsc28gaGF2ZSBzaXggc3VjY2Vzc2Z1bCBjb21wYXJpc29ucyBhbmQgYSBmaW5hbCBzdGVwIGluIHdoaWNoIGl0IGlzIGVzdGFibGlzaGVkIHRoYXQgdGhlIHdvcmRzIGFyZSBlcXVhbC4gQWZ0ZXIgZmluZGluZyB0aGUgd29yZCwgdGhlIGFsZ29yaXRobSB0ZXJtaW5hdGVzIHdpdGggZ3JlYXQgam95LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #5 6번