Reverse
题号：NC265536
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝在异世界游玩，这天他在异世界中发现了一个阵法，出于好奇小蓝进入了这个阵法，在阵法里小蓝获得了一个长度为 \mathit n 的 01 串，现在小蓝想要出去，但是阵法被下了禁制，小蓝必须要回答对若干次关于 01 串的问题才能解开阵法，具体来说，有 \mathit q 次询问，每次询问给出两个整数 \mathit l, \mathit r 表示一个区间，其中 \mathit l 为左端点， \mathit r 为右端点，表示将 \mathit s (下标从 \text 1 开始)串的区间 [ \mathit l, \mathit r] 翻转，问翻转后的整个 01 串中连续 \text 1 的段数有多少段，以小蓝的水平难以作答，请你帮他脱困。

每次询问独立。

输入描述:

第一行输入两个正整数 \mathit n, \mathit q (1\leq \mathit n \leq 10^6 , 1\leq \mathit q\leq 2·10^5) 。
第二行输入一个 01 字符串 \mathit s ，其中 \mathit s 的长度为 \mathit n 。
接下来 \mathit q 行，每行输入两个整数 \mathit l, \mathit r(1\leq \mathit l \leq \mathit r \leq \mathit n) 。

输出描述:

对于第 \mathit i 个询问，输出一个整数表示将区间 [ \mathit l, \mathit r] 翻转后，整个 01 串中连续 \text 1 的段数。
示例1

输入

复制 
5 2
01101
2 4
1 2

输出

复制 
1
3

说明

对于第一个操作，串会变成"00111"，在该串中有1段连续'1'。
对于第二个操作，串会变成"10101"，在该串中有3段连续'1'。

备注:

对于串 \mathit A ,设 \mathit A 的长度为 \mathit len ,若翻转 \mathit A 的 [ \mathit L, \mathit R] 区间，则 \mathit A 将由  \mathit A_1, \mathit A_2, \mathit A_3,..., \mathit A_{L-1}, \mathit A_L, \mathit A_{L+1},..., \mathit A_{R-1}, \mathit A_R, \mathit A_{R+1},..., \mathit A_{len}) 变为 \mathit A_1, \mathit A_2, \mathit A_3,..., \mathit A_{L-1}, \mathit A_R, \mathit A_{R-1},..., \mathit A_{L+1}, \mathit A_L, \mathit A_{R+1},..., \mathit A_{len}) 。