题目描述

给定一个长度为 $n$ 的 $01$ 序列（即每个元素为 $0$ 或 $1$）。Tim 会进行 $q$ 次操作，每次选择一个区间 $[\ell, r]$，若区间内的下标 $i \in [\ell, r]$ 且 $i - \ell$ 为奇数，则将其位置上的数异或 $1$（即 $0$ 变 $1$，$1$ 变 $0$）。

你需要求出整个序列最终的和。

输入描述

第一行输入两个整数 $n, q$（$1 \le n, q \le 5 \times 10^5$），分别表示 $01$ 序列的长度与操作次数。

第二行输入一个长度为 $n$ 的 $01$ 序列 $s$，保证 $s_i \in \{0, 1\}$。

接下来 $q$ 行，每行两个整数 $\ell, r$（$1 \le \ell \le r \le n$），表示一次操作区间。

输出描述

输出一个整数，表示最终序列的和。

样例

样例 1

6 3
101010
1 1
1 2
2 5

2

样例 2

12 4
111111111111
1 12
2 12
3 9
4 8

6

注释

对于第二组测试用例，原序列为 111111111111，操作过程如下：

1. $\ell=1, r=12$，序列变为 101010101010；
2. $\ell=2, r=12$，序列变为 100000000000；
3. $\ell=3, r=9$，序列变为 100101010000；
4. $\ell=4, r=8$，序列变为 100111110000。

最终序列中 1 的个数为 $6$，因此答案为 $6$。