Жадность

Джеймса Бонда всегда выручали новые гаджеты, которые проектирует целая команда в МИ-6. Но мало кто задумывался над тем, как проводят время гении из этого отдела...

Q --- один из тех людей, которые обеспечивают Бонда новым оружеем и следят за безопасностью сети компьютеров МИ-6. А когда Q становится скучно, он решает олимпиадные задачи по программированию. Однако, его метод решения задач несколько необычен.

Q знает, что в задачах из реальной жизни, с которыми он сталкивается каждый день, все входные данные достаточно случайные и равномерно распределены среди значений, которые они вообще могут принимать. Кроме того он знает, что в реальных задачах достаточно часто решением является некая разновидность <<жадного алгоритма>>.

Решая очередную олимпиадную задачу, Q сразу же после прочтения условия пишет решение, которое выдает правильные ответы для небольших начальных параметров, но при этом не укладывается в ограничения по времени. После этого он генерирует некоторое количество тестов абсолютно случайным образом, получает для них ответы с помощью уже написанного решения и пытается построить жадный алгоритм, проходящий эти тесты и работающий за корректное время. Затем Q отправляет новое решение на сервер и получает <<Accepted>>.

Вчера Петя решал очередную задачу со следующим условием:

Вам дана строчка, состоящая из цифр от одного до девяти, а также некоторое число $x > 9$. Необходимо разбить эту строку на наименьшее количество подстрок таких, что для каждой из них выполняется некоторое свойство. А именно, если считать, что подстрока является записью некоторого числа $y$ в десятичной системе счисления, то $y \le x$.

Даже не дочитав условие до конца, Q уже написал жадность, которая выдавала правильные ответы на сгенерированные им тесты. Его программа работала за $O(n)$, где $n$ --- длина строки, и он был собой очень доволен. Однако, когда Q дочитал условие до конца, его настигло жестокое разочарование. Кроме того, что Q уже реализовал, в условии просили обрабатывать запросы вида <<изменить некоторую цифру в строке>>, и после обработки каждого такого запроса необходимо было вывести новый ответ.

Q понял, что с ограничениями, данными в условии, его жадность работает очень долго. Он подумал еще пять минут, написал жадное решение, которое работало существенно быстрее старого, и получил <<Accepted>>.

Вам предлагается решить эту же задачу!

В первой строке входного файла находятся строка, состоящая из цифр от одного до девяти длиной не более $10^5$. В следующей строке записано два числа $m$ и $x$ ($0 \le m \le 10^5$, $10 \le x \le 10^9$) --- количество запросов изменения одного символа, а также число, которое подстроки из получающегося разбиения не должны превосходить. Следующие $m$ строк содержат по два числа $a_i$ и $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le 9$) --- номер цифры, которую надо изменить, а также ее новое значение.

В первой строке выходного файла выведите минимальное количество подстрок, на которое можно разбить данную строку, соблюдая условие задачи. В следующих $m$ строках для каждого запроса выведите ответ, получающийся после обработки этого запроса.