题目描述

给定一个仅由 0/1 组成的二进制字符串 $S$，长度为 $N$。有 $M$ 次操作，每次操作给定区间 $[l,r]$，将该区间内所有字符取反（即与 1 异或）：

$S_i \;\gets\; S_i \oplus 1,\quad l \le i \le r.$

所有操作执行完毕后，输出最终的二进制字符串。要求整体时间复杂度 $O(N+M)$。

输入格式

N M
S
l_1 r_1
…
l_M r_M

• 第一行两个整数 $N, M$（$1\le N,M\le10^6$）。
• 第二行一个长度为 $N$ 的字符串 $S$，仅包含 0 和 1。
• 接下来 $M$ 行，每行两个整数 $l,r$（$1\le l\le r\le N$），表示一次翻转操作。

输出格式

输出一个长度为 $N$ 的二进制字符串，为所有操作执行后的结果。

样例

5 2
01010
2 3
3 4

00000

数据范围