CF750E.New Year and Old Subsequence

A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn't occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice.

The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is  - 1.

Limak has a string s of length n, with characters indexed 1 through n. He asks you q queries. In the i-th query you should compute and print the ugliness of a substring (continuous subsequence) of s starting at the index a__i and ending at the index b__i (inclusive).

如果字符串“2017”在字符串 $t$ 中作为子序列出现，而字符串“2016”在 $t$ 中不作为子序列出现，则称字符串 $t$ 是优美的（nice）。例如，字符串 “203434107” 和 “9220617” 是优美的，而字符串 “20016”、“1234” 和 “20167” 则不是优美的。

一个字符串的**丑陋度（ugliness）**定义为：使其变为优美字符串所需删除的最少字符数。若无论如何删除字符都无法得到优美字符串，则其丑陋度为 $-1$。

Limak 有一个长度为 $n$ 的字符串 $s$，其字符下标从 $1$ 到 $n$。他向你提出 $q$ 个询问。对于第 $i$ 个询问，你需要计算并输出 $s$ 中从下标 $a_i$ 开始、到下标 $b_i$ 结束（含端点）的子串（连续子序列）的丑陋度。

The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.

The second line contains a string s of length n. Every character is one of digits '0'–'9'.

The i-th of next q lines contains two integers a__i and b__i (1 ≤ a__i ≤ b__i ≤ n), describing a substring in the i-th query.

输入的第一行包含两个整数 $n$ 和 $q$（$4 \leq n \leq 200\,000$，$1 \leq q \leq 200\,000$）——分别表示字符串 $s$ 的长度和查询次数。

第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符均为数字字符 '0'–'9' 之一。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i \leq b_i \leq n$），描述第 $i$ 个查询所对应的子串。

For each query print the ugliness of the given substring.

对于每个查询，输出给定子串的丑陋度。

In the first sample:

• In the first query, ugliness("20166766") = 4 because all four sixes must be removed.
• In the second query, ugliness("2016676") = 3 because all three sixes must be removed.
• In the third query, ugliness("0166766") =  - 1 because it's impossible to remove some digits to get a nice string.

In the second sample:

• In the second query, ugliness("01201666209167") = 2. It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice.
• In the third query, ugliness("016662091670") = 1. It's optimal to remove the last digit '6', what gives a nice string "01666209170".

在第一个样例中：

• 在第一个查询中，ugliness("20166766") = 4，因为必须移除全部四个 '6'。
• 在第二个查询中，ugliness("2016676") = 3，因为必须移除全部三个 '6'。
• 在第三个查询中，ugliness("0166766") = -1，因为无法通过移除若干位数字得到一个“优美”字符串。

在第二个样例中：

• 在第二个查询中，ugliness("01201666209167") = 2。最优策略是移除第一位数字 '2' 和最后一位数字 '6'，得到字符串 "010166620917"，该字符串是“优美”的。
• 在第三个查询中，ugliness("016662091670") = 1。最优策略是移除最后一位数字 '6'，得到“优美”字符串 "01666209170"。