시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 57 11 9 20.930%

문제

상근이는 고급 레스토랑을 하나 운영하고 있다. 후쿠시마 원자력 발전소 사고 이후로 국민들은 방사능에 큰 두려움을 가지게 되었다. 정부는 총 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번이다.

W3sicHJvYmxlbV9pZCI6IjkyMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWFlMDkgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhY2UwXHVhZTA5IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjNmI0XHVjNjAxXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNmM0XHVjZmUwXHVjMmRjXHViOWM4IFx1YzZkMFx1Yzc5MFx1YjgyNSBcdWJjMWNcdWM4MDRcdWMxOGMgXHVjMGFjXHVhY2UwIFx1Yzc3NFx1ZDZjNFx1Yjg1YyBcdWFkNmRcdWJiZmNcdWI0ZTRcdWM3NDAgXHViYzI5XHVjMGFjXHViMmE1XHVjNWQwIFx1ZDA3MCBcdWI0NTBcdWI4MjRcdWM2YzBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVjODE1XHViZDgwXHViMjk0IFx1Y2QxZCBNXHVjODg1XHViOTU4XHVjNzU4IFx1YzdhY1x1YjhjY1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHViYzI5XHVjMGFjXHViMmE1XHVjNzQwIFx1YzcwNFx1ZDVkOFx1ZDU1YyBcdWMyMThcdWM5MDBcdWM3NzRcdWI3N2MgXHVkMzEwXHViMmU4XHVkNTg4XHVhY2UwLCBcdWM3NzQgXHVjN2FjXHViOGNjXHViMjk0IFx1YzY5NFx1YjlhY1x1YzVkMCBcdWM4NzBcdWFlMDhcdWIzYzQgXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWJjOTVcdWM3NDQgXHVjODFjXHVjODE1XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjN2FjXHViOGNjXHViMjk0IFx1YzIyYlx1Yzc5MCgwLTkpXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWMxMWNcdWIyOTQgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc0Y1x1YzJkZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1Yzc0Y1x1YzJkZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjN2FjXHViOGNjXHVhYzAwIFx1YmMyOVx1YzBhY1x1YjJhNVx1YzVkMCBcdWM2MjRcdWM1ZmNcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzAmbmJzcDtcdWQzMTBcdWIyZThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhYzhjXHVjNzNjXHViOTc4IFx1YzU0NFx1Yzc3NFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzY5NFx1YjlhY1x1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWQ1NjlcdWNjZDBcdWMxMWMgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlMCBcdWIyZTRcdWM3NGMgXHVhYzgwXHVjMGFjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHVhYzAwIFx1YzZiNFx1YzYwMVx1ZDU1OFx1YjI5NCBcdWFkZmNcdWNjOTggXHVjNzRjXHVjMmRkXHVjODEwXHVjNWQwXHVjMTFjXHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNzkwXHViM2Q5XHVjNzNjXHViODVjIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMjBcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViZDgwXHVkMGMxXHVkNTc0IFx1Yzc3NCBcdWI4NWNcdWJkMDdcdWM3NDQgXHViZTRjXHViODI0XHVjNjU0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI4NWNcdWJkMDdcdWM3NDAgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOCBBXHVjNWQwIFx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzggQlx1YWMwMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YzhcdWIyOTRcdWM5YzBcdWI5N2MgXHVhYzgwXHVjMGFjXHVkNTVjXHViMmU0LiBcdWI4NWNcdWJkMDdcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3M2NcdWI4NWMgXHVhYzgwXHVjMGFjXHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gKEJcdWM3NTggXHVhZTM4XHVjNzc0ID0gTCk8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAsIEFcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWJkODBcdWQxMzAgTFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFlNGNcdWM5YzAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBCXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM1NWVcdWM1ZDBcdWMxMWMgXHViZDgwXHVkMTMwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU1OFx1YWM3MFx1YjA5OCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIyYlx1Yzc5MFx1YWU0Y1x1YzljMCBcdWJlNDRcdWFkNTBcdWQ1ODhcdWM3M2NcdWJhNzQsIFx1YmU0NFx1YWQ1MFx1Yjk3YyBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhYzE5XHVjNzNjXHViYTc0IFx1YzEzMVx1YWNmNSBcdWM1NGNcdWI5YmNcdWM3NDQgXHViY2Y0XHVjNWVjXHVjOTAwIFx1YjJlNFx1Yzc0YyBcdWFjODBcdWMwYWNcdWI5N2MgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3MDRcdWM3NTggXHVhY2ZjXHVjODE1XHVjNWQwXHVjMTFjIFx1YWM4MFx1YzBhY1x1YWMwMCBcdWM4ODVcdWI4Y2NcdWI0MThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHViYTc0LCAyXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YmQ4MFx1ZDEzMCBMKzFcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHViM2M0IFx1YWMxOVx1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIDNcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwIEwrMlx1YmM4OFx1YzlmOCwgNFx1YmM4OFx1YzlmOCBcdWJkODBcdWQxMzAgTCszXHViYzg4XHVjOWY4LCAuLi4gXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVhY2M0XHVjMThkIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWMyMThcdWQ1ODlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIExcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gKEFcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDhcdWM3N2MgXHViNTRjLCA1XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1YmQ4MFx1ZDEzMCBcdWFjODBcdWMwYWNcdWI5N2MgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCkgXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTFx1Yzc3NCBcdWI0MjAgXHViNTRjIFx1YWU0Y1x1YzljMCBcdWI0YTRcdWM1ZDAgJiMzOTsjJiMzOTtcdWI5N2MgXHViZDk5XHVjNWVjIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICZxdW90OzU2MzIzMiZxdW90O1x1Yzc1OCA0XHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YmQ4MFx1ZDEzMCAxMFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWFlNGNcdWM5YzAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmcXVvdDsyMzIjIyMjJnF1b3Q7XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjZDFkIE5cdWFjMWNcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWJhYThcdWI0NTAgXHVhYzgwXHVjMGFjXHVkNTg4XHViMjk0XHViMzcwXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWJkODBcdWJkODRcdWM3NDQgXHVjYzNlXHVjOWMwIFx1YmFiYlx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjMmU0XHVkMzI4IFx1YzU0Y1x1YjliY1x1Yzc0NCBcdWJjZjRcdWM1ZWNcdWM4ZmNcdWFjZTAgXHVhYzgwXHVjMGFjXHViOTdjIFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3XHVjNzc0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWJlNDRcdWFkNTBcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyAxXHVjNmQwXHVjNzQ0IFx1YjBiNFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzljMFx1YmQ4OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViM2M4XHVjNzQwIFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzRjXHVjMmRkXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViOTdjIFx1YWUzOFx1YWM4YyBcdWM3NzRcdWM1YjQgXHViZDk5XHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTA4XHVjOWMwXHViNDFjIFx1YzdhY1x1YjhjY1x1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTSAmbGU7IDUwLDAwMCkgXHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUwOFx1YzljMFx1YjQxYyBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjZDFkIDBcdWJkODBcdWQxMzAgOVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhZTA4XHVjOWMwXHViNDFjIFx1YzJkY1x1YjlhY1x1YzViYyBcdWJjODhcdWQ2MzhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDEwMCwwMDBcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWFlMDhcdWM5YzBcdWI0MWMgXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDFkIFx1ZDU2OVx1Yzc0MCAzLDAwMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjN2FjXHViOGNjXHViOTdjIFx1YWM4MFx1YzBhY1x1ZDU2MCBcdWI1NGMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM5YzBcdWJkODhcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWUwOFx1YzU2MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExYyBcdWFjODBcdWMwYWNcdWFjMDAgXHVjMmU0XHVkMzI4XHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmU0NFx1YWQ1MCBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjZDFkIDdcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWJlNDRcdWFkNTAgMVx1YmM4OCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHViZTQ0XHVhZDUwIDRcdWJjODgsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNWQwXHVjMTFjXHViMjk0IFx1YmU0NFx1YWQ1MCAxXHViYzg4LCBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExY1x1YjI5NCBcdWJlNDRcdWFkNTAgNFx1YmM4OFx1Yzc0NCBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWIxMjQgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YWM4MFx1YzBhY1x1Yjk3YyBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjMmRjXHViOWFjXHVjNWJjIFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWJlNDRcdWFkNTAgM1x1YmM4OCwgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWMyZGNcdWI5YWNcdWM1YmMgXHViYzg4XHVkNjM4XHViMjk0IFx1YmU0NFx1YWQ1MCAoMSArIDMpIDRcdWJjODhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MjM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0xBU1RJXHUwMTBjQVIiLCJkZXNjcmlwdGlvbiI6IjxwPk9yZ2FuaXppbmcgQ1MgY29udGVzdHMgZGlkbiYjMzk7dCBwcm92ZSB2ZXJ5IGx1Y3JhdGl2ZSBmb3IgTWlya28sIHNvIGhlIGhhcyBvcGVuZWQgYW4gaWNlIGNyZWFtIGFuZCBwYXN0cnkgc2hvcC4gVGhlIGJ1c2luZXNzIHdhcyBmbG91cmlzaGluZyB1bnRpbCwgb25lIGRheSwgdGhlIEV1cm9wZWFuIFVuaW9uIGhlYWx0aCBpbnNwZWN0aW9uIGRlY2lkZWQgdG8gcGF5IGhpbSBhIHZpc2l0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIG5ldyBkaXJlY3RpdmUgc3BlY2lmaWVzIE0gYmFubmVkIGluZ3JlZGllbnRzIHdoaWNoIGNhbm5vdCBhcHBlYXIgaW4gZm9vZCBldmVuIGluIHRyYWNlIGFtb3VudHMuIEVhY2ggaW5ncmVkaWVudCBoYXMgYSBzZXJpYWwgbnVtYmVyIGNvbnNpc3Rpbmcgb2YgZGlnaXRzIDAgdGhyb3VnaCA5LiBUaGUgZGVjbGFyYXRpb24gb24gZWFjaCBmb29kIHBhY2thZ2UgbGlzdHMgYWxsIHRoZSBzZXJpYWwgbnVtYmVycyBvZiBpbmdyZWRpZW50cyBjb250YWluZWQgaW4gdGhlIHJlc3BlY3RpdmUgZm9vZCBpdGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBtdXN0IGNoZWNrIHdoZXRoZXIgYW55IG9mIGhpcyBwcm9kdWN0cyBoYXMgYSBiYW5uZWQgaW5ncmVkaWVudCBzZXJpYWwgbnVtYmVyIGxpc3RlZCBvbiBpdHMgZGVjbGFyYXRpb24uIEhvd2V2ZXIsIE1pcmtvLCBiZWluZyBpbmVwdCBhbmQgcmVja2xlc3MgYXMgYWx3YXlzLCBkZWNpZGVkIHRvIGNvbmNhdGVuYXRlIGFsbCB0aGUgc2VyaWFsIG51bWJlcnMgaW50byBvbmUgbG9uZyBudW1iZXIgd2l0aCBsZW5ndGggTiBiZWxpZXZpbmcgdGhhdCBpdCB3aWxsIG1ha2UgaGlzIGpvYiBlYXNpZXIuIEhlIGhhcyBib3Jyb3dlZCBhIHJvYm90IGZyb20gaGlzIGZyaWVuZCBTbGF2a28uIFRoZSByb2JvdCBpcyBwcm9ncmFtbWVkIHRvIGNoZWNrIHdoZXRoZXIgYSBzZXJpYWwgbnVtYmVyJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgY29udGFpbnMgYW5vdGhlciBzZXJpYWwgbnVtYmVyIEIgYXMgYSBzdWJzdHJpbmcuIExldCB1cyBkZW5vdGUgdGhlIGxlbmd0aCBvZiBCIGJ5IEwuIFRoZSByb2JvdCBjYXJyaWVzIG91dCBzZWFyY2ggYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5GaXJzdCwgaXQgY29tcGFyZXMgdGhlIHNlZ21lbnQgb2YgQSBmcm9tIHBvc2l0aW9uIDEgdG8gcG9zaXRpb24gTCwgZGlnaXQgYnkgZGlnaXQsIHdpdGggdGhlIGRpZ2l0cyBpbiBCLiBDb21wYXJpc29uIGlzIHN0b3BwZWQgd2hlbiBhIGRpZmZlcmluZyBkaWdpdCBpcyBmb3VuZCBvciB3aGVuIHRoZSBzZWdtZW50cyBhcmUgZGV0ZXJtaW5lZCB0byBiZSBlcXVhbC4gSWYgdGhlIHNlZ21lbnRzIGFyZSBlcXVhbCwgdGhlIHNlYXJjaCBpcyBzdG9wcGVkIGFuZCB0aGUgbWF0Y2ggcmVwb3J0ZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIHRoZSBzZWdtZW50cyBhcmUgbm90IGVxdWFsLCB0aGUgcHJvY2VkdXJlIGFib3ZlIGlzIHJlcGVhdGVkIHdpdGggdGhlIHNlZ21lbnQgZnJvbSAyIHRvIEwrMS4gSWYgdGhvc2Ugc2VnbWVudHMgYXJlbiYjMzk7dCBlcXVhbCBlaXRoZXIsIHRoZSBzZWFyY2ggY29udGludWVzIHdpdGggc2VnbWVudHMgMyB0byBMKzIsIDQgdG8gTCszIGV0Yy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdGhlIHJvYm90IGRvZXNuJiMzOTt0IGhhdmUgYSBzdWZmaWNpZW50IG51bWJlciBvZiBkaWdpdHMgdG8gb2J0YWluIGEgZnVsbCBzZWdtZW50IG9mIGxlbmd0aCBMIChmb3IgZXhhbXBsZSwgc3RhcnRpbmcgYXQgY2hhcmFjdGVyIDUgaW4gYSBzZXJpYWwgbnVtYmVyIHdpdGggbGVuZ3RoIDgsIGEgc2VnbWVudCB3aXRoIGxlbmd0aCA2IGlzIG5lZWRlZCksIGl0IHdpbGwgcGFkIHRoZSBudW1iZXIgd2l0aCAmIzM5OyMmIzM5OyBzaWducy4gRm9yIGV4YW1wbGUsIHRoZSBzZWdtZW50IG9mICZxdW90OzU2MzIzMiZxdW90OyBmcm9tIHBvc2l0aW9uIDQgdG8gcG9zaXRpb24gMTAgaXMgJnF1b3Q7MjMyIyMjIyZxdW90Oy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgdGhlIHJvYm90IHJlYWNoZXMgdGhlIGVuZCBvZiB0aGUgc2VyaWFsIG51bWJlciAoaGF2aW5nIHRyaWVkIG91dCBhbGwgTiBzZWdtZW50cykgd2l0aG91dCBoYXZpbmcgZm91bmQgQiwgdGhlIGFic2VuY2Ugb2YgbWF0Y2ggaXMgcmVwb3J0ZWQuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHJvYm90IHRha2VzIG9uZSBzZWNvbmQgZm9yIGVhY2ggY29tcGFyaXNvbiBiZXR3ZWVuIHR3byBkaWdpdHMsIGFuZCBTbGF2a28gY2hhcmdlcyBNaXJrbyBvbmUgZG9sbGFyIHBlciBzZWNvbmQgZm9yIHVzaW5nIHRoZSByb2JvdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCBNaXJrbyBkZXRlcm1pbmUgaG93IG11Y2ggbW9uZXkgaGUmIzM5O2xsIGhhdmUgdG8gcGF5IFNsYXZrbyBmb3IgcGF0dGVybiBtYXRjaGluZyEmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIHRoZSBsZW5ndGggb2YgdGhlIGxvbmcgc2VyaWFsIG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gZGlnaXRzIGZyb20gMCB0byA5LCB0aGUgbG9uZyBzZXJpYWwgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBNICgxICZsZTsgTSAmbGU7IDUwIDAwMCksIHRoZSBudW1iZXIgb2YgYmFubmVkIGluZ2VyZWRpZW50cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE0gcm93cyBjb250YWlucyBhIHNpbmdsZSBiYW5uZWQgc2VyaWFsIG51bWJlciwmbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBiYW5uZWQgc2VyaWFsIG51bWJlciB3aWxsIG5vdCBleGNlZWQgMTAwIDAwMCBkaWdpdHMgaW4gbGVuZ3RoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdG90YWwgbGVuZ3RoIG9mIGFsbCBiYW5uZWQgc2VyaWFsIG51bWJlcnMgd2lsbCBub3QgZXhjZWVkIDMgMDAwIDAwMCBkaWdpdHMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE0gaW50ZWdlcnMsIG9uZSBwZXIgbGluZS4gTGluZSBpIG11c3QgY29udGFpbiB0aGUgZG9sbGFyIGFtb3VudCB0aGF0IE1pcmtvIG5lZWRzIHRvIHBheSBTbGF2a28gZm9yIHRoZSBzZWFyY2ggZm9yIGluZ3JlZGllbnQgc2VyaWFsIG51bWJlciBpLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5GaXJzdCBzZXJpYWwgbnVtYmVyOiB0aGUgcm9ib3QgZmluZHMgZGlmZmVyaW5nIGZpcnN0IGRpZ2l0cyBmb3IgZXZlcnkgc2VnbWVudCAmbmRhc2g7IGEgdG90YWwgb2YgNyBjb21wYXJpc29ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2Vjb25kIHNlcmlhbCBudW1iZXI6IHRyaWVzIGZpcnN0IHBvc2l0aW9uLCBmaW5kaW5nIGRpZmZlcmVuY2UgaW1tZWRpYXRlbHkgKDEgY29tcGFyaXNvbikuIFRyaWVzIHNlY29uZCBwb3NpdGlvbiwgZmluZGluZyBkaWZmZXJlbmNlIG9uIHRoZSBmb3VydGggZGlnaXQgKDQgY29tcGFyaXNvbnMpLiBUcmllcyB0aGlyZCBwb3NpdGlvbiwgZmluZGluZyBkaWZmZXJlbmNlIGltbWVkaWF0ZWx5ICgxIGNvbXBhcmlzb24pLlRyaWVzIGZvdXJ0aCBwb3NpdGlvbiwgZmluZGluZyBhIG1hdGNoICg0IGNvbXBhcmlzb25zKS4gVG90YWw6IDEwIGNvbXBhcmlzb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGlyZCBzZXJpYWwgbnVtYmVyOiBmaW5kcyBtYXRjaCBpbW1lZGlhdGVseSAoMyBjb21wYXJpc29ucykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvdXJ0aCBzZXJpYWwgbnVtYmVyOiBmaW5kcyBtYXRjaCBhdCBzZWNvbmQgcG9zaXRpb24gKDEgKyAzID0gNCBjb21wYXJpc29ucykuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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