E. Новый год и старая подпоследовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка t называется красивой, если строка «2017» встречается в t в качестве подпоследовательности, а строка «2016» не встречается в t в качестве подпоследовательности. Например, строки «203434107» и «9220617» являются красивыми, а строки «20016», «1234» и «20167» не являются красивыми.

Уродством строки называется минимальное количество символов, которые надо удалить, чтобы получить красивую строку. Если получить красивую строку удаляя символы невозможно, то её уродство равняется  - 1.

У Лимака есть строка s длины n, символы которой пронумерованы от 1 до n. Также у него есть q запросов. В i-м запросе выведите уродство подстроки (непрерывной подпоследовательности) s начинающейся с позиции номер ai и заканчивающейся в позиции номер bi (включительно).

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

В первой строке входных данных записаны два числа n и q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — длина строки s и количество запросов соответственно.

Во второй строке записана строка s длины n. Каждый из символов этой строки является цифрой «0»–«9».

В i-й из последующих q строк записаны два целых числа ai и bi (1 ≤ ai ≤ bi ≤ n), описывающих подстроку из i-го запроса.

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

Для каждого запроса выведите уродство соответствующей подстроки.

Примеры
Входные данные
8 3
20166766
1 8
1 7
2 8
Выходные данные
4
3
-1
Входные данные
15 5
012016662091670
3 4
1 14
4 15
1 13
10 15
Выходные данные
-1
2
1
-1
-1
Входные данные
4 2
1234
2 4
1 2
Выходные данные
-1
-1
Примечание

Рассмотрим первый пример. Далее запись ugliness(t) означает уродство строки t.

  • В первом запросе ugliness(«20166766») = 4, потому что потребуется удалить все четыре шестёрки.
  • Во втором запросе ugliness(«2016676») = 3, поскольку потребуется удалить все три шестёрки.
  • В третьем запросе ugliness(«0166766») =  - 1, так как нельзя сделать данную строку красивый удалением какого-либо числа символов.

Во втором примере:

  • Во втором запросе ugliness(«01201666209167») = 2. Оптимальным ответом будет удалить первую цифру «2» и последнюю цифру «6», что даст строку «010166620917», которая является красивой.
  • В третьем запросе ugliness(«016662091670») = 1. Оптимальным ответом является удалить последнюю цифр «6», что даст красивую строку «01666209170».