Problem: Daniel has a string s, consisting of lowercase English letters and period signs (characters '.'). Let's define the operation of replacement as the following sequence of steps: find a substring ".." (two consecutive periods) in string s, of all occurrences of the substring let's choose the first one, and replace this substring with string ".". In other words, during the replacement operation, the first two consecutive periods are replaced by one. If string s contains no two consecutive periods, then nothing happens.

Let's define f(s) as the minimum number of operations of replacement to perform, so that the string does not have any two consecutive periods left.

You need to process m queries, the i-th results in that the character at position xi (1 ≤ xi ≤ n) of string s is assigned value ci. After each operation you have to calculate and output the value of f(s).

Help Daniel to process all queries.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) the length of the string and the number of queries.

The second line contains string s, consisting of n lowercase English letters and period signs.

The following m lines contain the descriptions of queries. The i-th line contains integer xi and ci (1 ≤ xi ≤ n, ci — a lowercas English letter or a period sign), describing the query of assigning symbol ci to position xi.

Output

Print m numbers, one per line, the i-th of these numbers must be equal to the value of f(s) after performing the i-th assignment.

Examples

Input

10 3
.b..bz....
1 h
3 c
9 f


Output

4
3
1


Input

4 4
.cc.
2 .
3 .
2 a
1 a


Output

1
3
1
1

Note

Note to the first sample test (replaced periods are enclosed in square brackets).

The original string is ".b..bz....".

  * after the first query f(hb..bz....) = 4 ("hb[..]bz...."  →  "hb.bz[..].."  →  "hb.bz[..]."  →  "hb.bz[..]"  →  "hb.bz.")
  * after the second query f(hbс.bz....) = 3 ("hbс.bz[..].."  →  "hbс.bz[..]."  →  "hbс.bz[..]"  →  "hbс.bz.")
  * after the third query f(hbс.bz..f.) = 1 ("hbс.bz[..]f."  →  "hbс.bz.f.")



Note to the second sample test.

The original string is ".cc.".

  * after the first query: f(..c.) = 1 ("[..]c."  →  ".c.")
  * after the second query: f(....) = 3 ("[..].."  →  "[..]."  →  "[..]"  →  ".")
  * after the third query: f(.a..) = 1 (".a[..]"  →  ".a.")
  * after the fourth query: f(aa..) = 1 ("aa[..]"  →  "aa.")

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

public class C {

	static class Interval implements Comparable<Interval> {
		int l, r;

		public Interval(int l, int r) {
			this.l = l;
			this.r = r;
		}

		@Override
		public int compareTo(Interval o) {
			if (o.l >= this.l && o.l <= this.r)
				return 0;
			if (this.l >= o.l && this.l <= o.r)
				return 0;

			return new Integer(this.l).compareTo(o.l);
		}

		public Interval[] split(int splitPoint) {
			return new Interval[] { new Interval(this.l, splitPoint - 1), new Interval(splitPoint + 1, this.r) };
		}

		public Interval add(Interval another) {
			if (another.r < this.l) {
				return new Interval(another.l, this.r);
			} else {
				return new Interval(this.l, another.r);
			}
		}

		public long getMoves() {
			return this.r - this.l;
		}

		public boolean isValid() {
			return this.l <= this.r;
		}
	}

	static String solve(int n, int m, char[] s, int[] qp, char[] qc) {
		StringBuilder sb = new StringBuilder();

		long currentSum = 0;
		TreeSet<Interval> tree = new TreeSet<C.Interval>();
		int cs = -1;
		for (int i = 0; i < s.length; i++) {
			if (cs == -1) {
				if (s[i] == '.') {
					cs = i;
				}
			} else {
				if (s[i] != '.') {

					Interval ni = new Interval(cs, i - 1);
					tree.add(ni);
					currentSum += ni.getMoves();

					cs = -1;
				}
			}
		}
		if (cs != -1) {
			Interval ni = new Interval(cs, s.length - 1);
			tree.add(ni);
			currentSum += ni.getMoves();
		}

		for (int i = 0; i < m; i++) {
			int pos = qp[i];
			char c = qc[i];
			if (s[pos] == c) {
				sb.append(currentSum);
				sb.append(System.lineSeparator());
				continue;
			}

			if (s[pos] == '.') {
				Interval current = null;
				Interval ln = tree.lower(new Interval(pos, pos));
				if (ln == null) {
					current = tree.first();
				} else {
					current = tree.higher(ln);
				}
				currentSum -= current.getMoves();
				tree.remove(current);
				if (current.getMoves() > 0) {
					Interval[] two = current.split(pos);
					if (two[0].isValid()) {
						tree.add(two[0]);
						currentSum += two[0].getMoves();
					}

					if (two[1].isValid()) {
						tree.add(two[1]);
						currentSum += two[1].getMoves();
					}
				}
			} else if (c == '.') {				
				Interval complete = new Interval(pos, pos);

				Interval ln = tree.lower(complete);
				if (ln != null && ln.r + 1 == complete.l) {
					tree.remove(ln);
					complete = complete.add(ln);
					currentSum -= ln.getMoves();
				}

				Interval rn = tree.higher(new Interval(pos, pos));
				if (rn != null && rn.l - 1 == complete.r) {
					tree.remove(rn);
					complete = complete.add(rn);
					currentSum -= rn.getMoves();
				}

				tree.add(complete);
				currentSum += complete.getMoves();
			}

			s[pos] = c;

			sb.append(currentSum);
			sb.append(System.lineSeparator());
		}

		return sb.toString();
	}

	static String solveBF(int n, int m, char[] s, int[] qp, char[] qc) {
		StringBuilder sb = new StringBuilder();		
		for (int i = 0; i < qp.length; i++) {
			s[qp[i]] = qc[i];
			long currentSum = 0;
			List<Character> chars = new ArrayList<Character>();
			for (int j = 0; j < s.length; j++) {
				chars.add(s[j]);
			}
			
			while(true) {
				int ind = -1;
				for (int j = 0; j < chars.size() - 1; j++) {
					if (chars.get(j) == '.' && chars.get(j + 1) == '.')
						ind = j;
				}
				if (ind == -1) break;
				chars.remove(ind);
				currentSum++;
			}
			
			sb.append(currentSum);
			sb.append(System.lineSeparator());
		}

		return sb.toString();
	}

	static class Input {
		public int n, m;
		public char[] s;
		public int[] qp;
		public char[] qc;
		private static Random r = new Random();

		public Input() {
			this.n = r.nextInt(1000) + 1;
			this.m = r.nextInt(10) + 1;
			s = new char[n];
			for (int i = 0; i < s.length; i++) {
				s[i] = r.nextDouble() < 0.5 ? '.' : (char) ('a' + r.nextInt(26));
			}
			this.qp = new int[m];
			this.qc = new char[m];
			for (int i = 0; i < this.m; i++) {
				this.qp[i] = r.nextInt(this.n);
				this.qc[i] = r.nextDouble() < 0.5 ? '.' : (char) ('a' + r.nextInt(26));
			}
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			sb.append(n + " " + m);
			sb.append(System.lineSeparator());
			sb.append(this.s);
			sb.append(System.lineSeparator());
			for (int i = 0; i < qc.length; i++) {
				sb.append((this.qp[i] + 1) + " " + this.qc[i]);
				if (i != qc.length - 1)
					sb.append(System.lineSeparator());
			}

			return sb.toString();
		}
		
		public Input clone() {
			Input c = new Input();
			c.n = this.n;
			c.m = this.m;
			c.s = Arrays.copyOf(this.s, this.s.length);
			c.qp = Arrays.copyOf(this.qp, this.qp.length);
			c.qc = Arrays.copyOf(this.qc, this.qc.length);
			
			return c;
		}
	}

	public static void main(String[] args) throws Exception {
		int[] l = readIntArray();
		int n = l[0];
		int m = l[1];

		char[] s = br.readLine().toCharArray();

		int[] qi = new int[m];
		char[] qc = new char[m];

		for (int i = 0; i < m; i++) {
			String[] v = br.readLine().split(" ");
			int pos = Integer.valueOf(v[0]) - 1;
			char c = v[1].charAt(0);
			qi[i] = pos;
			qc[i] = c;
		}
		
		System.out.println(solve(n,m,s,qi,qc));
		
//		for (int i = 0; i < 10000000; i++) {
//
//			Input pi = new Input();
//			Input pi2 = pi.clone();
//
//			String sol = solve(pi.n, pi.m, pi.s, pi.qp, pi.qc);
//			String solBF = solveBF(pi2.n, pi2.m, pi2.s, pi2.qp, pi2.qc);
//
//			if (!sol.equals(solBF)) {
//				System.out.println("ERROR********************");
//				
//				System.out.println(pi.toString());				
//				
//				System.out.println(sol);
//				System.out.println(solBF);
//			
//				return;
//			}					
//		}		
	}

	static void append(StringBuilder sb, int val) {
		if (sb.length() > 0) {
			sb.append('\n');
		}

		sb.append(val);
	}

	static InputStreamReader isr = new InputStreamReader(System.in);
	static BufferedReader br = new BufferedReader(isr);
	static StringBuilder sb = new StringBuilder();

	static String readNextToken() throws IOException {
		sb.setLength(0);
		char c = ' ';
		do {
			c = ((char) br.read());
			if (Character.isWhitespace(c)) {
				if (sb.length() > 0) {
					break;
				}
			} else {
				sb.append(c);
			}
		} while (true);

		return sb.toString();
	}

	static int ni() throws Exception {
		return Integer.parseInt(readNextToken());
	}

	static long nl() throws Exception {
		return Long.parseLong(readNextToken());
	}

	static int[] readIntArray() throws IOException {

		String[] v = br.readLine().split(" ");
		int[] ans = new int[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Integer.valueOf(v[i]);
		}

		return ans;
	}

	static long[] readLongArray() throws IOException {
		String[] v = br.readLine().split(" ");
		long[] ans = new long[v.length];

		for (int i = 0; i < ans.length; i++) {
			ans[i] = Long.valueOf(v[i]);
		}

		return ans;
	}

	static <T> void print(List<T> v) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < v.size(); i++) {
			if (sb.length() > 0) {
				sb.append(' ');
			}

			sb.append(v.get(i));
		}

		System.out.println(sb);
	}
}