H. Зигзаг
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть бинарная строка $$$a$$$ длины $$$n$$$, состоящая только из цифр $$$0$$$ и $$$1$$$.

Вам даны $$$q$$$ запросов. В $$$i$$$-м запросе даны два индекса $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$.

Пусть $$$s=a[l,r]$$$. Вам разрешено выполнять следующую операцию над $$$s$$$:

  1. Выберите два индекса $$$x$$$ и $$$y$$$ такие, что $$$1 \le x \le y \le |s|$$$. Пусть $$$t$$$  — подстрока $$$t = s[x, y]$$$. Тогда для всех $$$1 \le i \le |t| - 1$$$ должно выполняться условие $$$t_i \neq t_{i+1}$$$. Заметим, что $$$x = y$$$ всегда является допустимой подстрокой.
  2. Удалите подстроку $$$s[x, y]$$$ из $$$s$$$.

Для каждого из $$$q$$$ запросов найдите минимальное количество операций, необходимое для превращения $$$s$$$ в пустую строку.

Напомним, что для строки $$$s$$$, $$$s[l,r]$$$ обозначает подотрезок $$$s_l,s_{l+1},\ldots,s_r$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10 ^ 5$$$)  — длину бинарной строки $$$a$$$ и количество запросов соответственно.

Вторая строка содержит бинарную строку $$$a$$$ длины $$$n$$$ ($$$a_i \in \{0, 1\}$$$).

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$)  — обозначающие подстроку каждого запроса.

Выходные данные

Выведите $$$q$$$ строк, в $$$i$$$-й строке выведите минимальное количество операций, необходимых для $$$i$$$-го запроса.

Примеры
Входные данные
5 3
11011
2 4
1 5
3 5
Выходные данные
1
3
2
Входные данные
10 3
1001110110
1 10
2 5
5 10
Выходные данные
4
2
3
Примечание

В первом примере,

  1. Подстрока равна $$$\texttt{101}$$$, поэтому мы можем сделать одну операцию, чтобы сделать подстроку пустой.
  2. Подстрока равна $$$\texttt{11011}$$$, поэтому мы можем сделать одну операцию над $$$s[2, 4]$$$, чтобы получить $$$\texttt{11}$$$, а затем использовать еще две операции, чтобы сделать подстроку пустой.
  3. Подстрока  — $$$\texttt{011}$$$, поэтому мы можем сделать одну операцию над $$$s[1, 2]$$$, чтобы получить $$$\texttt{1}$$$, а затем использовать еще одну операцию, чтобы сделать подстроку пустой.