乌龟仙人又来为难高皓光了，为了避免成为法尸，请你完成下面这道题。

给出一个长度为 $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` 表示无解。

## 说明/提示

### 样例 #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$|