시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 128 MB1633100.000%

문제

인터넷에 있는 정보의 양은 급속하게 증가하고 있다. 이런 정보의 폭발 시대에서는 찾으려고 하는 정보가 있는 웹 페이지만 들어가야 시간을 절약할 수 있다. 그러기 위해서 가장 중요한 검색 방법은 키워드 검색이다. 많은 검색 엔진은 키워드 검색을 사용할 수 있고, 키워드 검색을 통해서 유용한 정보를 포함하는 페이지에 접근할 수 있다.

키워드 검색에는 많은 변형이 있다. 만약 주어진 텍스트에서 문자열 하나를 찾는 경우에는 상당히 문제가 쉬워진다. 이러한 경우에는 여러 문자열에서 패턴을 찾거나 정규표현식을 이용해서 찾으면 된다.

이 문제는 문자열(기본 문자열)이 여러 개가 주어진다. 기본 문자열을 적절히 합쳐 한 문자열로 만든 뒤 이 문자열을 주어진 텍스트에서 찾아야 한다.

예를 들어, 기본 문자열이 aa, b, ccc일 때, 이 문자열을 합쳐서 만들 수 있는 문자열은 다음과 같이 6개가 있고, 각각을 텍스트에서 찾아야 한다. aabccc, aacccb, baaccc, bcccaa, cccaab, cccbaa

텍스트에는 이러한 문자열이 등장하는 횟수를 세야 한다. 즉, 텍스트에서 등장하는 문자열 위치의 개수를 세면 된다.

두 개 또는 그 이상의 문자열을 합친 것이 같을 수도 있다. 문제 설명을 조금 자세히 읽으면 이 경우를 어떻게 처리해야 하는지 알 수 있다. 예를 들어, 두 기본 문자열이 x와 xx일 때, 두 문자열을 합치면 둘 다 xxx가 된다. 문자열이 등장하는 위치의 개수를 세야하므로 이 경우에는 문자열 1개로 세면 된다.

문자열이 등장하는 구간이 겹칠 수도 있다. 예를 들어, xxxx에는 xxx가 두 번 등장한다. 이 경우에는 서로 다른 위치에서 등장하기 때문에, 두 가지로 계산한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 기본 문자열의 개수 n과 텍스트의 줄의 수 m이 주어진다. n은 1보다 크거나 같고, 12보다 작거나 같다.

다음 n개 줄은 기본 문자열이다. 이 문자열의 길이는 1보다 크거나 같고, 20보다 작거나 같다.

다음 m개 줄은 텍스트이다. 텍스트는 너무 길어질 수 있기 때문에, m줄로 나누어져 있다. 하지만, 줄바꿈은 텍스트의 일부가 아니며, 무시하고 검색을 해야 한다. 각 줄의 길이는 최대 100이며, 텍스트의 길이는 최대 5000이다. 텍스트는 비어있지 않다.

기본 문자열과 텍스트는 알파벳 소문자로만 이루어져 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

주의! 12!×5000은 231보다 매우 크다.

출력

각 테스트 케이스에 대해서, 문자열이 등장하는 위치의 개수를 출력한다.

예제 입력 1

3 1
aa
b
ccc
aabccczbaacccbaazaabbcccaa
3 1
a
b
c
cbbcbcbabaacabccaccbaacbccbcaaaccccbcbcbbcacbaacccaccbbcaacbbabbabaccc
3 4
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
0 0

예제 출력 1

5
12
197
W3sicHJvYmxlbV9pZCI6IjM4OTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYTRcdWM2Y2NcdWI0ZGMgXHVhYzgwXHVjMGM5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzhcdWQxMzBcdWIxMzdcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YmNmNFx1Yzc1OCBcdWM1OTFcdWM3NDAgXHVhZTA5XHVjMThkXHVkNTU4XHVhYzhjIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdmMCBcdWM4MTVcdWJjZjRcdWM3NTggXHVkM2VkXHViYzFjIFx1YzJkY1x1YjMwMFx1YzVkMFx1YzExY1x1YjI5NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjNmY5IFx1ZDM5OFx1Yzc3NFx1YzljMFx1YjljYyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWM1N2MgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzgwOFx1YzU3ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVhYzgwXHVjMGM5IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWQwYTRcdWM2Y2NcdWI0ZGMgXHVhYzgwXHVjMGM5XHVjNzc0XHViMmU0LiBcdWI5Y2VcdWM3NDAgXHVhYzgwXHVjMGM5IFx1YzVkNFx1YzljNFx1Yzc0MCBcdWQwYTRcdWM2Y2NcdWI0ZGMgXHVhYzgwXHVjMGM5XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQwYTRcdWM2Y2NcdWI0ZGMgXHVhYzgwXHVjMGM5XHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWM3MjBcdWM2YTlcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWQzOThcdWM3NzRcdWM5YzBcdWM1ZDAgXHVjODExXHVhZGZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVkMGE0XHVjNmNjXHViNGRjIFx1YWM4MFx1YzBjOVx1YzVkMFx1YjI5NCBcdWI5Y2VcdWM3NDAgXHViY2MwXHVkNjE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YzhmY1x1YzViNFx1YzljNCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHViYjM4XHVjNzkwXHVjNWY0IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzBjMVx1YjJmOVx1ZDc4OCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjMjZjXHVjNmNjXHVjOWM0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVkMzI4XHVkMTM0XHVjNzQ0IFx1Y2MzZVx1YWM3MFx1YjA5OCBcdWM4MTVcdWFkZGNcdWQ0NWNcdWQ2MDRcdWMyZGRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Y2MzZVx1YzczY1x1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQoXHVhZTMwXHViY2Y4IFx1YmIzOFx1Yzc5MFx1YzVmNClcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzMFx1YmNmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjODAxXHVjODA4XHVkNzg4IFx1ZDU2OVx1Y2NkMCBcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjljY1x1YjRlMCBcdWI0YTQgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkMTRkXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVhZTMwXHViY2Y4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBhYSwgYiwgY2NjXHVjNzdjIFx1YjU0YywgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQ1NjlcdWNjZDBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgNlx1YWMxY1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc0NCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjYzNlXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gYWFiY2NjLCBhYWNjY2IsIGJhYWNjYywgYmNjY2FhLCBjY2NhYWIsIGNjY2JhYTxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YzVkMFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjMTM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViNDUwIFx1YWMxYyBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVkNTY5XHVjZTVjIFx1YWM4M1x1Yzc3NCBcdWFjMTlcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1Yzc0NCBcdWM4NzBcdWFlMDggXHVjNzkwXHVjMTM4XHVkNzg4IFx1Yzc3ZFx1YzczY1x1YmE3NCBcdWM3NzQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzViNFx1YjViYlx1YWM4YyBcdWNjOThcdWI5YWNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWI0NTAgXHVhZTMwXHViY2Y4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCB4XHVjNjQwIHh4XHVjNzdjIFx1YjU0YywgXHViNDUwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQ1NjlcdWNlNThcdWJhNzQgXHViNDU4IFx1YjJlNCB4eHhcdWFjMDAgXHViNDFjXHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHVjNTdjXHVkNTU4XHViYmMwXHViODVjIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IDFcdWFjMWNcdWI4NWMgXHVjMTM4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWFjYjlcdWNlNjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgeHh4eFx1YzVkMFx1YjI5NCB4eHhcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNDUwIFx1YWMwMFx1YzljMFx1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTMwXHViY2Y4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWQxNGRcdWMyYTRcdWQyYjhcdWM3NTggXHVjOTA0XHVjNzU4IFx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEyXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNzQwIFx1YWUzMFx1YmNmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM3NDAgXHVkMTRkXHVjMmE0XHVkMmI4XHVjNzc0XHViMmU0LiBcdWQxNGRcdWMyYTRcdWQyYjhcdWIyOTQgXHViMTA4XHViYjM0IFx1YWUzOFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgbVx1YzkwNFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzkwNFx1YmMxNFx1YWZjOFx1Yzc0MCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM3NTggXHVjNzdjXHViZDgwXHVhYzAwIFx1YzU0NFx1YjJjOFx1YmE3MCwgXHViYjM0XHVjMmRjXHVkNTU4XHVhY2UwIFx1YWM4MFx1YzBjOVx1Yzc0NCBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVjNzc0XHViYTcwLCBcdWQxNGRcdWMyYTRcdWQyYjhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1MDAwXHVjNzc0XHViMmU0LiBcdWQxNGRcdWMyYTRcdWQyYjhcdWIyOTQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWFlMzBcdWJjZjggXHViYjM4XHVjNzkwXHVjNWY0XHVhY2ZjIFx1ZDE0ZFx1YzJhNFx1ZDJiOFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD48c3Ryb25nPlx1YzhmY1x1Yzc1OCE8XC9zdHJvbmc+IDEyISZ0aW1lczs1MDAwXHVjNzQwIDI8c3VwPjMxPFwvc3VwPlx1YmNmNFx1YjJlNCBcdWI5ZTRcdWM2YjAgXHVkMDZjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzODkxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VhcmNoIG9mIENvbmNhdGVuYXRlZCBTdHJpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgYW1vdW50IG9mIGluZm9ybWF0aW9uIG9uIHRoZSBXb3JsZCBXaWRlIFdlYiBpcyBncm93aW5nIHF1aXRlIHJhcGlkbHkuIEluIHRoaXMgaW5mb3JtYXRpb24gZXhwbG9zaW9uIGFnZSwgd2UgbXVzdCBzdXJ2aXZlIGJ5IGFjY2Vzc2luZyBvbmx5IHRoZSBXZWIgcGFnZXMgY29udGFpbmluZyBpbmZvcm1hdGlvbiByZWxldmFudCB0byBvdXIgb3duIG5lZWRzLiBPbmUgb2YgdGhlIGtleSB0ZWNobm9sb2dpZXMgZm9yIHRoaXMgcHVycG9zZSBpcyBrZXl3b3JkIHNlYXJjaC4gQnkgdXNpbmcgd2VsbC1rbm93biBzZWFyY2ggZW5naW5lcywgd2UgY2FuIGVhc2lseSBhY2Nlc3MgdGhvc2UgcGFnZXMgY29udGFpbmluZyB1c2VmdWwgaW5mb3JtYXRpb24gYWJvdXQgdGhlIHRvcGljIHdlIHdhbnQgdG8ga25vdy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIG1hbnkgdmFyaWF0aW9ucyBpbiBrZXl3b3JkIHNlYXJjaCBwcm9ibGVtcy4gSWYgYSBzaW5nbGUgc3RyaW5nIGlzIHNlYXJjaGVkIGluIGEgZ2l2ZW4gdGV4dCwgdGhlIHByb2JsZW0gaXMgcXVpdGUgZWFzeS4gSWYgdGhlIHBhdHRlcm4gdG8gYmUgc2VhcmNoZWQgY29uc2lzdHMgb2YgbXVsdGlwbGUgc3RyaW5ncywgb3IgaXMgZ2l2ZW4gYnkgc29tZSBwb3dlcmZ1bCBub3RhdGlvbiBzdWNoIGFzIHJlZ3VsYXIgZXhwcmVzc2lvbnMsIHRoZSB0YXNrIHJlcXVpcmVzIGVsYWJvcmF0ZSBhbGdvcml0aG1zIHRvIGFjY29tcGxpc2ggZWZmaWNpZW50bHkuPFwvcD5cclxuXHJcbjxwPkluIG91ciBwcm9ibGVtLCBhIG51bWJlciBvZiBzdHJpbmdzIChlbGVtZW50IHN0cmluZ3MpIGFyZSBnaXZlbiwgYnV0IHRoZXkgYXJlIG5vdCBkaXJlY3RseSBzZWFyY2hlZCBmb3IuIENvbmNhdGVuYXRpb25zIG9mIGFsbCB0aGUgZWxlbWVudCBzdHJpbmdzIGluIGFueSBvcmRlciBhcmUgdGhlIHRhcmdldHMgb2YgdGhlIHNlYXJjaCBoZXJlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhyZWUgZWxlbWVudCBzdHJpbmdzIGFhLCBiIGFuZCBjY2MgYXJlIGdpdmVuLiBJbiB0aGlzIGNhc2UsIHRoZSBmb2xsb3dpbmcgc2l4IGNvbmNhdGVuYXRlZCBzdHJpbmdzIGFyZSB0aGUgdGFyZ2V0cyBvZiB0aGUgc2VhcmNoLCBpLmUuIHRoZXkgc2hvdWxkIGJlIHNlYXJjaGVkIGluIHRoZSB0ZXh0LjxcL3A+XHJcblxyXG48cD5hYWJjY2M8YnIgXC8+XHJcbmFhY2NjYjxiciBcLz5cclxuYmFhY2NjPGJyIFwvPlxyXG5iY2NjYWE8YnIgXC8+XHJcbmNjY2FhYjxiciBcLz5cclxuY2NjYmFhPFwvcD5cclxuXHJcbjxwPlRoZSB0ZXh0IG1heSBjb250YWluIHNldmVyYWwgb2NjdXJyZW5jZXMgb2YgdGhlc2Ugc3RyaW5ncy4gWW91IGFyZSByZXF1ZXN0ZWQgdG8gY291bnQgdGhlIG51bWJlciBvZiBvY2N1cnJlbmNlcyBvZiB0aGVzZSBzdHJpbmdzLCBvciBzcGVha2luZyBtb3JlIHByZWNpc2VseSwgdGhlIG51bWJlciBvZiBwb3NpdGlvbnMgb2Ygb2NjdXJyZW5jZXMgaW4gdGhlIHRleHQuPFwvcD5cclxuXHJcbjxwPlR3byBvciBtb3JlIGNvbmNhdGVuYXRlZCBzdHJpbmdzIG1heSBiZSBpZGVudGljYWwuIEluIHN1Y2ggY2FzZXMsIGl0IGlzIG5lY2Vzc2FyeSB0byBjb25zaWRlciBzdWJ0bGUgYXNwZWN0cyBvZiB0aGUgYWJvdmUgcHJvYmxlbSBzdGF0ZW1lbnQuIEZvciBleGFtcGxlLCBpZiB0d28gZWxlbWVudCBzdHJpbmdzIGFyZSB4IGFuZCB4eCwgdGhlIHN0cmluZyB4eHggaXMgYW4gb2NjdXJyZW5jZSBvZiBib3RoIHRoZSBjb25jYXRlbmF0aW9uIG9mIHggYW5kIHh4IGFuZCB0aGF0IG9mIHh4IGFuZCB4LiBTaW5jZSB0aGUgbnVtYmVyIG9mIHBvc2l0aW9ucyBvZiBvY2N1cnJlbmNlcyBzaG91bGQgYmUgY291bnRlZCwgdGhpcyBjYXNlIGlzIGNvdW50ZWQgYXMgb25lLCBub3QgdHdvLjxcL3A+XHJcblxyXG48cD5Ud28gb2NjdXJyZW5jZXMgbWF5IG92ZXJsYXAuIEZvciBleGFtcGxlLCB0aGUgc3RyaW5nIHh4eHggaGFzIG9jY3VycmVuY2VzIG9mIHRoZSBjb25jYXRlbmF0aW9uIHh4eCBpbiB0d28gZGlcdWZiMDBlcmVudCBwb3NpdGlvbnMuIFRoaXMgY2FzZSBpcyBjb3VudGVkIGFzIHR3by48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBkYXRhc2V0cywgZWFjaCBnaXZpbmcgYSBzZXQgb2YgZWxlbWVudCBzdHJpbmdzIGFuZCBhIHRleHQuIFRoZSBmb3JtYXQgb2YgYSBkYXRhc2V0IGlzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4gbVxyXG5lPHN1Yj4xPFwvc3ViPlxyXG5lPHN1Yj4yPFwvc3ViPlxyXG4uLi5cclxuZTxzdWI+bjxcL3N1Yj5cclxudDxzdWI+MTxcL3N1Yj5cclxudDxzdWI+MjxcL3N1Yj5cclxuLi4uXHJcbnQ8c3ViPm08XC9zdWI+XHJcbjxcL3ByZT5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gbiBpcyB0aGUgbnVtYmVyIG9mIGVsZW1lbnQgc3RyaW5ncy4gbSBpcyB0aGUgbnVtYmVyIG9mIGxpbmVzIHVzZWQgdG8gcmVwcmVzZW50IHRoZSB0ZXh0LiBuIGlzIGJldHdlZW4gMSBhbmQgMTIsIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgZ2l2ZXMgYW4gZWxlbWVudCBzdHJpbmcuIFRoZSBsZW5ndGggKG51bWJlciBvZiBjaGFyYWN0ZXJzKSBvZiBhbiBlbGVtZW50IHN0cmluZyBpcyBiZXR3ZWVuIDEgYW5kIDIwLCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IG0gbGluZXMgYXMgYSB3aG9sZSBnaXZlIHRoZSB0ZXh0LiBTaW5jZSBpdCBpcyBub3QgZGVzaXJhYmxlIHRvIGhhdmUgYSB2ZXJ5IGxvbmcgbGluZSwgdGhlIHRleHQgaXMgc2VwYXJhdGVkIGludG8gbSBsaW5lcyBieSBuZXdsaW5lcywgYnV0IHRoZXNlIG5ld2xpbmVzIHNob3VsZCBiZSBpZ25vcmVkLiBUaGV5IGFyZSBub3QgcGFydHMgb2YgdGhlIHRleHQuIFRoZSBsZW5ndGggb2YgZWFjaCBvZiB0aGVzZSBsaW5lcyAobm90IGluY2x1ZGluZyB0aGUgbmV3bGluZSkgaXMgYmV0d2VlbiAxIGFuZCAxMDAsIGluY2x1c2l2ZS4gVGhlIGxlbmd0aCBvZiB0aGUgdGV4dCBpcyBiZXR3ZWVuIDEgYW5kIDUwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5DQVVUSU9OITxcL3N0cm9uZz4gQWx0aG91Z2ggdGhlIHNhbXBsZSBpbnB1dCBjb250YWlucyBvbmx5IHNtYWxsIGRhdGFzZXRzLCBub3RlIHRoYXQgMTIhICZ0aW1lczsgNTAwMCBpcyBmYXIgbGFyZ2VyIHRoYW4gMjMxLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0IGluIHRoZSBpbnB1dCwgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIG1hdGNoZWQgcG9zaXRpb25zIHNob3VsZCBiZSBvdXRwdXQuIEFuIG91dHB1dCBsaW5lIHNob3VsZCBub3QgY29udGFpbiBleHRyYSBjaGFyYWN0ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2008 in Aizu G번