탐욕법

제임스 본드는 늘 MI-6의 개발팀이 만든 새 장비 덕분에 위기를 넘겼다. 하지만 그 부서의 천재들이 평소에 시간을 어떻게 보내는지 궁금해하는 사람은 드물다.

Q는 본드에게 새 무기를 제공하고 MI-6 컴퓨터 네트워크의 보안을 지키는 사람이다. Q는 심심해지면 프로그래밍 올림피아드 문제를 푼다. 그의 방식은 조금 특이하다.

Q는 실생활 문제에서 입력 데이터가 꽤 무작위이고, 가능한 값들 사이에 고르게 분포한다고 믿는다. 또 실생활 문제의 해는 흔히 어떤 종류의 탐욕 알고리즘이라고도 생각한다.

Q는 새 올림피아드 문제를 받으면 문제를 읽자마자 먼저 풀이를 작성한다. 이 풀이는 작은 입력에서는 정답을 내지만 제한 시간에는 맞지 않는다. 다음으로 완전히 무작위인 테스트를 많이 만들고, 그 풀이로 정답을 구한 뒤, 이 테스트를 통과하고 제한 시간 안에 도는 탐욕 알고리즘을 만든다. 그렇게 만든 풀이를 서버에 제출하면 Accepted를 받는다.

어제 페챠는 다음 문제를 풀었다.

1부터 9까지의 숫자로 이루어진 문자열과 정수 $x > 9$가 주어진다. 이 문자열을 각 부분 문자열을 십진수 $y$로 읽었을 때 $y \le x$를 만족하도록, 가능한 한 적은 개수의 부분 문자열로 나누어라.

Q는 테스트에서 정답을 내고 $n$을 문자열의 길이라 할 때 $O(n)$에 동작하는 탐욕 알고리즘을 작성했다. 문제를 끝까지 읽어 보니 문자열의 한 숫자를 바꾸는 질의가 더 있었고, 질의를 처리할 때마다 새 답을 출력해야 했다. Q의 탐욕 알고리즘은 이 제한에서는 너무 느리다. 그는 5분을 더 고민한 끝에 훨씬 빠른 탐욕 알고리즘을 작성하고 Accepted를 받았다.

이제 같은 문제를 풀어라.

첫 줄에는 길이 $n \le 10^5$인, 1부터 9까지의 숫자로 이루어진 문자열이 주어진다.

둘째 줄에는 두 정수 $m$과 $x$ ($0 \le m \le 10^5$, $10 \le x \le 10^9$)가 주어진다. $m$은 한 자리 숫자를 바꾸는 질의의 개수이고, $x$는 부분 문자열이 넘지 말아야 할 값이다.

이어지는 $m$개의 줄에는 두 정수 $a_i$와 $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le 9$)가 주어진다. $a_i$번째 숫자를 $b_i$로 바꾼다는 뜻이다.

첫 줄에 원래 문자열을 나눌 때 부분 문자열의 최소 개수를 출력한다.

이어서 $m$개의 질의를 각각 적용한 뒤의 답을 한 줄에 하나씩 출력한다.