시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB74131122.449%

문제

상근이는 고급 레스토랑을 하나 운영하고 있다. 후쿠시마 원자력 발전소 사고 이후로 국민들은 방사능에 큰 두려움을 가지게 되었다. 정부는 총 M종류의 재료에 포함된 방사능은 위험한 수준이라 판단했고, 이 재료는 요리에 조금도 사용하지 못하는 법을 제정했다.

모든 재료는 숫자(0-9)로만 이루어진 시리얼 번호를 가지고 있다. 상근이의 레스토랑에서는 만드는 음식의 개수는 하나이다. 상근이는 이 음식에 들어가는 모든 재료의 시리얼 번호를 알고 있다.

상근이는 각각의 재료가 방사능에 오염되었는지 판단해야 한다. 하지만, 상근이는 매우 게으른 아이이기 때문에, 요리에 들어가는 모든 재료의 시리얼 번호를 하나로 합쳐서 길이가 N인 문자열을 만든 다음 검사하려고 한다.

선영이가 운영하는 근처 음식점에서는 로봇을 이용해 자동으로 검사를 한다. 상근이는 선영이에게 부탁해 이 로봇을 빌려왔다. 

로봇은 시리얼 번호 A에 시리얼 번호 B가 포함되었는지를 검사한다. 로봇은 아래와 같은 과정으로 검사를 수행한다. (B의 길이 = L)

  • 먼저, A의 첫 번째 숫자부터 L번째 숫자까지 부분 문자열을 B의 숫자와 앞에서 부터 하나씩 비교한다. 서로 다른 숫자를 발견하거나, 마지막 숫자까지 비교했으면, 비교를 종료한다. 두 숫자가 같으면 성공 알림을 보여준 다음 검사를 종료한다.
  • 위의 과정에서 검사가 종료되지 않았다면, 2번째 숫자부터 L+1번째 숫자를 비교한다. 그래도 같지 않다면, 3번째 부터 L+2번째, 4번째 부터 L+3번째, ... 와 같은 순서로 계속 검사를 수행한다.
  • 검사를 해야 하는 부분 문자열의 길이가 L보다 작은 경우가 존재할 수도 있다. (A의 길이가 8일 때, 5번째 문자부터 검사를 시작하는 경우) 이런 경우에는 길이가 L이 될 때 까지 뒤에 '#'를 붙여 검사를 한다. 예를 들어, "563232"의 4번째 위치부터 10번째 위치까지 부분 문자열은 "232####"이 된다.
  • 총 N개의 부분 문자열을 모두 검사했는데도 같은 부분을 찾지 못한 경우에는 실패 알림을 보여주고 검사를 종료한다.

상근이는 로봇이 두 숫자를 한 번 비교할 때마다 선영이에게 1원을 내야한다.

상근이가 지불해야 하는 돈은 얼마일까?

입력

첫째 줄에 음식에 포함되는 시리얼 번호를 길게 이어 붙인 문자열의 길이 N이 주어지고, 둘째 줄에 시리얼 번호가 주어진다. (1 ≤ N ≤ 100,000)

셋째 줄에는 금지된 재료의 수 M이 주어진다. (1 ≤ M ≤ 50,000) 다음 M개 줄에는 금지된 시리얼 번호가 하나씩 주어진다.

시리얼 번호는 총 0부터 9까지 숫자로만 이루어져 있고, 금지된 시리얼 번호의 길이는 100,000를 넘지 않는다. 또, 금지된 시리얼 번호의 길이의 총 합은 3,000,000을 넘지 않는다.

출력

각각의 재료를 검사할 때, 선영이에게 지불해야 하는 금액을 출력한다.

예제 입력 1

7
1090901
4
87650
0901
109
090

예제 출력 1

7
10
3
4

첫 번째 시리얼 번호는 모든 부분 문자열의 첫 번째 숫자에서 검사가 실패한다. 따라서, 비교 횟수는 총 7번이다.

두 번째 시리얼 번호의 경우에는 첫 번째 숫자에서 시작했을 때 비교 1번, 두 번째 숫자에서 시작했을 때, 비교 4번, 세 번째 숫자에서는 비교 1번, 네 번째 숫자에서는 비교 4번을 하게 된다. 네 번째 숫자에서 시작했을 때, 문자열이 일치하는 것을 발견하기 때문에 검사를 종료한다.

세 번째 시리얼 번호는 비교 3번, 네 번째 시리얼 번호는 비교 (1 + 3) 4번이다.

예제 입력 2

10
5821052680
4
210526
2105
582
105268

예제 출력 2

8
6
3
9

예제 입력 3

3
001
1
11

예제 출력 3

4
W3sicHJvYmxlbV9pZCI6IjkyMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWFlMDkgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHVhZTA5IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjNmI0XHVjNjAxXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNmM0XHVjZmUwXHVjMmRjXHViOWM4IFx1YzZkMFx1Yzc5MFx1YjgyNSBcdWJjMWNcdWM4MDRcdWMxOGMgXHVjMGFjXHVhY2UwIFx1Yzc3NFx1ZDZjNFx1Yjg1YyBcdWFkNmRcdWJiZmNcdWI0ZTRcdWM3NDAgXHViYzI5XHVjMGFjXHViMmE1XHVjNWQwIFx1ZDA3MCBcdWI0NTBcdWI4MjRcdWM2YzBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVjODE1XHViZDgwXHViMjk0IFx1Y2QxZCBNXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhY1x1YjhjY1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViYzI5XHVjMGFjXHViMmE1XHVjNzQwIFx1YzcwNFx1ZDVkOFx1ZDU1YyBcdWMyMThcdWM5MDBcdWM3NzRcdWI3N2MgXHVkMzEwXHViMmU4XHVkNTg4XHVhY2UwLCBcdWM3NzQgXHVjN2FjXHViOGNjXHViMjk0IFx1YzY5NFx1YjlhY1x1YzVkMCBcdWM4NzBcdWFlMDhcdWIzYzQgXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWJjOTVcdWM3NDQgXHVjODFjXHVjODE1XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjN2FjXHViOGNjXHViMjk0IFx1YzIyYlx1Yzc5MCgwLTkpXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWMxMWNcdWIyOTQgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc0Y1x1YzJkZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1Yzc0Y1x1YzJkZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjN2FjXHViOGNjXHVhYzAwIFx1YmMyOVx1YzBhY1x1YjJhNVx1YzVkMCBcdWM2MjRcdWM1ZmNcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzAmbmJzcDtcdWQzMTBcdWIyZThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhYzhjXHVjNzNjXHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzY5NFx1YjlhY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWQ1NjlcdWNjZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlMCBcdWIyZTRcdWM3NGMgXHVhYzgwXHVjMGFjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YzZiNFx1YzYwMVx1ZDU1OFx1YjI5NCBcdWFkZmNcdWNjOTggXHVjNzRjXHVjMmRkXHVjODEwXHVjNWQwXHVjMTFjXHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViZDgwXHVkMGMxXHVkNTc0IFx1Yzc3NCBcdWI4NWNcdWJkMDdcdWM3NDQgXHViZTRjXHViODI0XHVjNjU0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI4NWNcdWJkMDdcdWM3NDAgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOCBBXHVjNWQwIFx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzggQlx1YWMwMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzBcdWI5N2MgXHVhYzgwXHVjMGFjXHVkNTVjXHViMmU0LiBcdWI4NWNcdWJkMDdcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgXHVhYzgwXHVjMGFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gKEJcdWM3NTggXHVhZTM4XHVjNzc0ID0gTCk8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAsIEFcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWJkODBcdWQxMzAgTFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFlNGNcdWM5YzAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBCXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHViZDgwXHVkMTMwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YWM3MFx1YjA5OCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIyYlx1Yzc5MFx1YWU0Y1x1YzljMCBcdWJlNDRcdWFkNTBcdWQ1ODhcdWM3M2NcdWJhNzQsIFx1YmU0NFx1YWQ1MFx1Yjk3YyBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhYzE5XHVjNzNjXHViYTc0IFx1YzEzMVx1YWNmNSBcdWM1NGNcdWI5YmNcdWM3NDQgXHViY2Y0XHVjNWVjXHVjOTAwIFx1YjJlNFx1Yzc0YyBcdWFjODBcdWMwYWNcdWI5N2MgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3MDRcdWM3NTggXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjIFx1YWM4MFx1YzBhY1x1YWMwMCBcdWM4ODVcdWI4Y2NcdWI0MThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViYTc0LCAyXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YmQ4MFx1ZDEzMCBMKzFcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHViM2M0IFx1YWMxOVx1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIDNcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwIEwrMlx1YmM4OFx1YzlmOCwgNFx1YmM4OFx1YzlmOCBcdWJkODBcdWQxMzAgTCszXHViYzg4XHVjOWY4LCAuLi4gXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVhY2M0XHVjMThkIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIExcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gKEFcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDhcdWM3N2MgXHViNTRjLCA1XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YmQ4MFx1ZDEzMCBcdWFjODBcdWMwYWNcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCkgXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3NCBcdWI0MjAgXHViNTRjIFx1YWU0Y1x1YzljMCBcdWI0YTRcdWM1ZDAgJiMzOTsjJiMzOTtcdWI5N2MgXHViZDk5XHVjNWVjIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZxdW90OzU2MzIzMiZxdW90O1x1Yzc1OCA0XHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YmQ4MFx1ZDEzMCAxMFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWFlNGNcdWM5YzAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmcXVvdDsyMzIjIyMjJnF1b3Q7XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjZDFkIE5cdWFjMWNcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzgwXHVjMGFjXHVkNTg4XHViMjk0XHViMzcwXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWJkODBcdWJkODRcdWM3NDQgXHVjYzNlXHVjOWMwIFx1YmFiYlx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMmU0XHVkMzI4IFx1YzU0Y1x1YjliY1x1Yzc0NCBcdWJjZjRcdWM1ZWNcdWM4ZmNcdWFjZTAgXHVhYzgwXHVjMGFjXHViOTdjIFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3XHVjNzc0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWJlNDRcdWFkNTBcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyAxXHVjNmQwXHVjNzQ0IFx1YjBiNFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViM2M4XHVjNzQwIFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzRjXHVjMmRkXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWUzOFx1YWM4YyBcdWM3NzRcdWM1YjQgXHViZDk5XHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTA4XHVjOWMwXHViNDFjIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDUwLDAwMCkgXHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUwOFx1YzljMFx1YjQxYyBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjZDFkIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhZTA4XHVjOWMwXHViNDFjIFx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEwMCwwMDBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWFlMDhcdWM5YzBcdWI0MWMgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc0MCAzLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjN2FjXHViOGNjXHViOTdjIFx1YWM4MFx1YzBhY1x1ZDU2MCBcdWI1NGMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5YzBcdWJkODhcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWUwOFx1YzU2MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExYyBcdWFjODBcdWMwYWNcdWFjMDAgXHVjMmU0XHVkMzI4XHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmU0NFx1YWQ1MCBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjZDFkIDdcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWJlNDRcdWFkNTAgMVx1YmM4OCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViZTQ0XHVhZDUwIDRcdWJjODgsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNWQwXHVjMTFjXHViMjk0IFx1YmU0NFx1YWQ1MCAxXHViYzg4LCBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExY1x1YjI5NCBcdWJlNDRcdWFkNTAgNFx1YmM4OFx1Yzc0NCBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWJlNDRcdWFkNTAgM1x1YmM4OCwgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViMjk0IFx1YmU0NFx1YWQ1MCAoMSArIDMpIDRcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiOTIzNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNMQVNUSVx1MDEwY0FSIiwiZGVzY3JpcHRpb24iOiI8cD5Pcmdhbml6aW5nIENTIGNvbnRlc3RzIGRpZG4mIzM5O3QgcHJvdmUgdmVyeSBsdWNyYXRpdmUgZm9yIE1pcmtvLCBzbyBoZSBoYXMgb3BlbmVkIGFuIGljZSBjcmVhbSBhbmQgcGFzdHJ5IHNob3AuIFRoZSBidXNpbmVzcyB3YXMgZmxvdXJpc2hpbmcgdW50aWwsIG9uZSBkYXksIHRoZSBFdXJvcGVhbiBVbmlvbiBoZWFsdGggaW5zcGVjdGlvbiBkZWNpZGVkIHRvIHBheSBoaW0gYSB2aXNpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBuZXcgZGlyZWN0aXZlIHNwZWNpZmllcyBNIGJhbm5lZCBpbmdyZWRpZW50cyB3aGljaCBjYW5ub3QgYXBwZWFyIGluIGZvb2QgZXZlbiBpbiB0cmFjZSBhbW91bnRzLiBFYWNoIGluZ3JlZGllbnQgaGFzIGEgc2VyaWFsIG51bWJlciBjb25zaXN0aW5nIG9mIGRpZ2l0cyAwIHRocm91Z2ggOS4gVGhlIGRlY2xhcmF0aW9uIG9uIGVhY2ggZm9vZCBwYWNrYWdlIGxpc3RzIGFsbCB0aGUgc2VyaWFsIG51bWJlcnMgb2YgaW5ncmVkaWVudHMgY29udGFpbmVkIGluIHRoZSByZXNwZWN0aXZlIGZvb2QgaXRlbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gbXVzdCBjaGVjayB3aGV0aGVyIGFueSBvZiBoaXMgcHJvZHVjdHMgaGFzIGEgYmFubmVkIGluZ3JlZGllbnQgc2VyaWFsIG51bWJlciBsaXN0ZWQgb24gaXRzIGRlY2xhcmF0aW9uLiBIb3dldmVyLCBNaXJrbywgYmVpbmcgaW5lcHQgYW5kIHJlY2tsZXNzIGFzIGFsd2F5cywgZGVjaWRlZCB0byBjb25jYXRlbmF0ZSBhbGwgdGhlIHNlcmlhbCBudW1iZXJzIGludG8gb25lIGxvbmcgbnVtYmVyIHdpdGggbGVuZ3RoIE4gYmVsaWV2aW5nIHRoYXQgaXQgd2lsbCBtYWtlIGhpcyBqb2IgZWFzaWVyLiBIZSBoYXMgYm9ycm93ZWQgYSByb2JvdCBmcm9tIGhpcyBmcmllbmQgU2xhdmtvLiBUaGUgcm9ib3QgaXMgcHJvZ3JhbW1lZCB0byBjaGVjayB3aGV0aGVyIGEgc2VyaWFsIG51bWJlciZuYnNwOzxcL3A+XHJcblxyXG48cD5BIGNvbnRhaW5zIGFub3RoZXIgc2VyaWFsIG51bWJlciBCIGFzIGEgc3Vic3RyaW5nLiBMZXQgdXMgZGVub3RlIHRoZSBsZW5ndGggb2YgQiBieSBMLiBUaGUgcm9ib3QgY2FycmllcyBvdXQgc2VhcmNoIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rmlyc3QsIGl0IGNvbXBhcmVzIHRoZSBzZWdtZW50IG9mIEEgZnJvbSBwb3NpdGlvbiAxIHRvIHBvc2l0aW9uIEwsIGRpZ2l0IGJ5IGRpZ2l0LCB3aXRoIHRoZSBkaWdpdHMgaW4gQi4gQ29tcGFyaXNvbiBpcyBzdG9wcGVkIHdoZW4gYSBkaWZmZXJpbmcgZGlnaXQgaXMgZm91bmQgb3Igd2hlbiB0aGUgc2VnbWVudHMgYXJlIGRldGVybWluZWQgdG8gYmUgZXF1YWwuIElmIHRoZSBzZWdtZW50cyBhcmUgZXF1YWwsIHRoZSBzZWFyY2ggaXMgc3RvcHBlZCBhbmQgdGhlIG1hdGNoIHJlcG9ydGVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgc2VnbWVudHMgYXJlIG5vdCBlcXVhbCwgdGhlIHByb2NlZHVyZSBhYm92ZSBpcyByZXBlYXRlZCB3aXRoIHRoZSBzZWdtZW50IGZyb20gMiB0byBMKzEuIElmIHRob3NlIHNlZ21lbnRzIGFyZW4mIzM5O3QgZXF1YWwgZWl0aGVyLCB0aGUgc2VhcmNoIGNvbnRpbnVlcyB3aXRoIHNlZ21lbnRzIDMgdG8gTCsyLCA0IHRvIEwrMyBldGMuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIHRoZSByb2JvdCBkb2VzbiYjMzk7dCBoYXZlIGEgc3VmZmljaWVudCBudW1iZXIgb2YgZGlnaXRzIHRvIG9idGFpbiBhIGZ1bGwgc2VnbWVudCBvZiBsZW5ndGggTCAoZm9yIGV4YW1wbGUsIHN0YXJ0aW5nIGF0IGNoYXJhY3RlciA1IGluIGEgc2VyaWFsIG51bWJlciB3aXRoIGxlbmd0aCA4LCBhIHNlZ21lbnQgd2l0aCBsZW5ndGggNiBpcyBuZWVkZWQpLCBpdCB3aWxsIHBhZCB0aGUgbnVtYmVyIHdpdGggJiMzOTsjJiMzOTsgc2lnbnMuIEZvciBleGFtcGxlLCB0aGUgc2VnbWVudCBvZiAmcXVvdDs1NjMyMzImcXVvdDsgZnJvbSBwb3NpdGlvbiA0IHRvIHBvc2l0aW9uIDEwIGlzICZxdW90OzIzMiMjIyMmcXVvdDsuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIHRoZSByb2JvdCByZWFjaGVzIHRoZSBlbmQgb2YgdGhlIHNlcmlhbCBudW1iZXIgKGhhdmluZyB0cmllZCBvdXQgYWxsIE4gc2VnbWVudHMpIHdpdGhvdXQgaGF2aW5nIGZvdW5kIEIsIHRoZSBhYnNlbmNlIG9mIG1hdGNoIGlzIHJlcG9ydGVkLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSByb2JvdCB0YWtlcyBvbmUgc2Vjb25kIGZvciBlYWNoIGNvbXBhcmlzb24gYmV0d2VlbiB0d28gZGlnaXRzLCBhbmQgU2xhdmtvIGNoYXJnZXMgTWlya28gb25lIGRvbGxhciBwZXIgc2Vjb25kIGZvciB1c2luZyB0aGUgcm9ib3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlbHAgTWlya28gZGV0ZXJtaW5lIGhvdyBtdWNoIG1vbmV5IGhlJiMzOTtsbCBoYXZlIHRvIHBheSBTbGF2a28gZm9yIHBhdHRlcm4gbWF0Y2hpbmchJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nIHNlcmlhbCBudW1iZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGRpZ2l0cyBmcm9tIDAgdG8gOSwgdGhlIGxvbmcgc2VyaWFsIG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTSAoMSAmbGU7IE0gJmxlOyA1MCAwMDApLCB0aGUgbnVtYmVyIG9mIGJhbm5lZCBpbmdlcmVkaWVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIHJvd3MgY29udGFpbnMgYSBzaW5nbGUgYmFubmVkIHNlcmlhbCBudW1iZXIsJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgYmFubmVkIHNlcmlhbCBudW1iZXIgd2lsbCBub3QgZXhjZWVkIDEwMCAwMDAgZGlnaXRzIGluIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRvdGFsIGxlbmd0aCBvZiBhbGwgYmFubmVkIHNlcmlhbCBudW1iZXJzIHdpbGwgbm90IGV4Y2VlZCAzIDAwMCAwMDAgZGlnaXRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBNIGludGVnZXJzLCBvbmUgcGVyIGxpbmUuIExpbmUgaSBtdXN0IGNvbnRhaW4gdGhlIGRvbGxhciBhbW91bnQgdGhhdCBNaXJrbyBuZWVkcyB0byBwYXkgU2xhdmtvIGZvciB0aGUgc2VhcmNoIGZvciBpbmdyZWRpZW50IHNlcmlhbCBudW1iZXIgaS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkZpcnN0IHNlcmlhbCBudW1iZXI6IHRoZSByb2JvdCBmaW5kcyBkaWZmZXJpbmcgZmlyc3QgZGlnaXRzIGZvciBldmVyeSBzZWdtZW50ICZuZGFzaDsgYSB0b3RhbCBvZiA3IGNvbXBhcmlzb25zLjxcL3A+XHJcblxyXG48cD5TZWNvbmQgc2VyaWFsIG51bWJlcjogdHJpZXMgZmlyc3QgcG9zaXRpb24sIGZpbmRpbmcgZGlmZmVyZW5jZSBpbW1lZGlhdGVseSAoMSBjb21wYXJpc29uKS4gVHJpZXMgc2Vjb25kIHBvc2l0aW9uLCBmaW5kaW5nIGRpZmZlcmVuY2Ugb24gdGhlIGZvdXJ0aCBkaWdpdCAoNCBjb21wYXJpc29ucykuIFRyaWVzIHRoaXJkIHBvc2l0aW9uLCBmaW5kaW5nIGRpZmZlcmVuY2UgaW1tZWRpYXRlbHkgKDEgY29tcGFyaXNvbikuVHJpZXMgZm91cnRoIHBvc2l0aW9uLCBmaW5kaW5nIGEgbWF0Y2ggKDQgY29tcGFyaXNvbnMpLiBUb3RhbDogMTAgY29tcGFyaXNvbnMuPFwvcD5cclxuXHJcbjxwPlRoaXJkIHNlcmlhbCBudW1iZXI6IGZpbmRzIG1hdGNoIGltbWVkaWF0ZWx5ICgzIGNvbXBhcmlzb25zKS48XC9wPlxyXG5cclxuPHA+Rm91cnRoIHNlcmlhbCBudW1iZXI6IGZpbmRzIG1hdGNoIGF0IHNlY29uZCBwb3NpdGlvbiAoMSArIDMgPSA0IGNvbXBhcmlzb25zKS48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHA+VGhlIHJvYm90IGNvbXBhcmVzIHRoZSBzZXJpYWwgbnVtYmVyICYjMzk7MTEmIzM5OyBpbiBvcmRlciB3aXRoIHNlZ21lbnRzICYjMzk7MDAmIzM5OyAoMSBjb21wYXJpc29uKSwgJiMzOTswMSYjMzk7ICgxIGNvbXBhcmlzb24pIGFuZCAmIzM5OzEjJiMzOTsgKDIgY29tcGFyaXNvbnMpLiBUb3RhbDogNCBjb21wYXJpc29ucy48XC9wPlxyXG4ifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #1 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kipa00