Greedy

James Bond has always been saved by new gadgets designed by a whole team at MI-6. Few people wonder how the geniuses of that department spend their time.

Q is one of the people who supply Bond with new weapons and keep the MI-6 computer network secure. When Q gets bored, he solves programming olympiad problems. His method is somewhat unusual.

Q knows that in real-life problems, all input data is fairly random and uniformly distributed over the values it can take. He also knows that real problems often have a solution that is some kind of greedy algorithm.

When Q gets a new olympiad problem, he first writes a solution right after reading the statement. It gives correct answers for small parameters but does not fit the time limit. Then he generates many tests completely at random, gets their answers from that solution, and builds a greedy algorithm that passes these tests and runs in the required time. He submits the new solution to the server and gets Accepted.

Yesterday Petya solved the following problem.

You are given a string of digits from 1 to 9 and an integer $x > 9$. Split this string into the smallest possible number of substrings such that each substring, read as a decimal number $y$, satisfies $y \le x$.

Q wrote a greedy that gave correct answers on his tests and ran in $O(n)$, where $n$ is the length of the string. When he finished reading the statement, he found an extra requirement. The problem also asks to process queries that change one digit of the string, and after each query the new answer must be printed. Q's greedy is too slow for these limits. He thought for five more minutes, wrote a faster greedy, and got Accepted.

Solve this same problem.

The first line contains a string of digits from 1 to 9 of length $n \le 10^5$.

The second line contains two integers $m$ and $x$ ($0 \le m \le 10^5$, $10 \le x \le 10^9$), where $m$ is the number of single-digit change queries and $x$ is the bound that every substring must not exceed.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le 9$). The digit at position $a_i$ is changed to $b_i$.

Print the minimum number of substrings for the original string on the first line.

Then print the answer after each of the $m$ queries is applied, one answer per line.