题目描述

定义一个数字串满足性质$nice$当且仅当：该串包含子序列$2017$，且不包含子序列$2016$。

定义一个数字串的函数$ugliness$为：该串至少删去几个字符，可以使得剩余串满足性质$nice$；如果该串没有满足性质$nice$的子序列，则该串的$ugliness$是$-1$。

给定一个长度为$n$的字符串$t$，和$q$次询问，每次询问用$(l,r)$表示。对于每次询问，回答$ugliness(t[l,r])$。

输入格式

第一行输入两个整数$n,q$ ，其中$n$是字符串$s$的长度，$q$是询问的个数。

第二行输入完全由十进制数字组成的字符串$s$。

接下来的$n$行，每行输入两个整数$l,r$，描述一个询问。

输出格式

对于每个询问，输出一行答案。

输入输出样例 #1

输入 #1

8 3
20166766
1 8
1 7
2 8

输出 #1

4
3
-1

输入输出样例 #2

输入 #2

15 5
012016662091670
3 4
1 14
4 15
1 13
10 15

输出 #2

-1
2
1
-1
-1

输入输出样例 #3

输入 #3

4 2
1234
2 4
1 2

输出 #3

-1
-1

说明/提示

$$ 4 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq l \leq r \leq n $$