乌龟仙人又来为难高皓光了，为了避免成为法尸，请你完成下面这道题。
给出一个长度为 n 的 \texttt{01} 串（只包含 \texttt{0,1} 的字符串），再给出 m 个互不相交的区间 [l_i,r_i]。形式化地，对于所有 1 到 n 的整数，其至多被包含在一个区间中。
你可以进行若干次操作，每次操作可以任意选择一个区间 [L,R]，将区间 [L,R] 内的所有 \texttt{0} 都变成 \texttt{1}，同时所有 \texttt{1} 都变成 \texttt{0}。
求让所有给定的区间中，每一个区间内 \texttt{0},\texttt{1} 数量都相同的最少操作次数。无解输出 -1。
第一行两个整数 n,m。
第二行一个长度为 n 的 \texttt{01} 串。
接下来 m 行，每行两个整数 l_i,r_i，表示一个区间。保证这些区间互不相交。
一行一个整数表示最小的操作次数，或者 -1 表示无解。
4 1 1011 1 4
1
操作区间 [3,3]，该串将变为 \texttt{1001}。此时区间 [1,4] 中恰有两个 \texttt{0},\texttt{1}，所以符合题目要求。可以证明这是最少的操作次数。
对于 100\% 的数据，1\le m\le n\le 2\times 10^6。保证 m 个区间互不相交。
| 测试点 | n\le | m\le |
|---|---|---|
| 1\sim 2 | 10 | n |
| 3\sim 4 | 500 | n |
| 5\sim 6 | 2\times 10^6 | 1 |
| 7\sim 10 | 2\times 10^6 | n |
luogu