H. Homo Programmius
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You recently passed the starters tryouts, tasted the pizza of champions after the final contest, and now proudly parade on campus with your ICPC T-shirt every day, monday through saturday (you wash it on sundays).

Your name is now among such legends as Leo Cupids, Gab the Handsome and Big Paul, congratulations!!!

But alas, it seems the times for celebration have come to an end.

You have begun to notice worrisome changes in your physiology.

Symptoms include shrimp posture when coding, social ineptitude and sleepless nights - trying to figure out the proof to a greedy solution.

Alarmed, you take a genetic exam and gasp at the results: doctors have identified sections of your DNA that are unlike any found in a normal human. You are now the world's first Homo Programmius!

Your task is to determine how far the mutations have developed.

Specifically, given a DNA string of size $$$n$$$, count how many contiguous segments contain at least one mutation. A mutated gene is marked as 1, while normal genes are written as $$$0$$$.

For example, the DNA string $$$[001]$$$ has 6 distinct segments: $$$[(0)01]$$$, $$$[0(0)1]$$$, $$$[00(1)]$$$, $$$[(00)1]$$$, $$$[0(01)]$$$, $$$[(001)]$$$. Only 3 of which contain at least one mutation: $$$[00(1)]$$$, $$$[0(01)]$$$ and $$$[(001)]$$$.

But beware! The mutations are unstable, such that any single position of your DNA might change from one instant to the next.

Input

The first line contains an integer $$$n$$$: the size of the DNA string ($$$1 \le n \le 10^5$$$).

The second line consists of a binary string $$$S$$$ of size $$$n$$$: the original DNA string ($$$S_i = \,\, '0' \,\, or \,\, S_i = \, '1'$$$).

The third line consists of an integer $$$m$$$: the number of modifications the DNA string will go through ($$$1 \le m \le 10^5$$$).

Each one of the next $$$m$$$ lines corresponds to a modification of the DNA string, consisting of an integer and a character: $$$pos$$$ $$$val$$$, meaning that $$$S_{pos}$$$ changes its value to $$$val$$$. ($$$1 \le pos \le n$$$, $$$val = \,'0' \,\, or \,\,val = \,'1'$$$).

Output

For each of the $$$m$$$ modification events, a single line-separated integer $$$x_i$$$ must be printed, such that $$$x_i$$$ is the number of segments with at least one mutation in the string, after the first $$$i$$$ modifications($$$ 1 \le i \le m)$$$.

Example
Input
5
01111
10
4 0
3 0
3 1
2 0
5 0
4 1
4 0
3 0
5 1
1 1
Output
13
11
13
11
9
11
9
0
5
9