如果字符串“2017”作为子序列出现在 t 中,但字符串“2016”不作为子序列出现在 t 中,则称字符串 t 是好的。例如,字符串“203434107”和“9220617”很好,而字符串“20016”、“1234”和“20167”则不好。
字符串的丑陋程度是为了获得漂亮的字符串而需要删除的最少字符数。如果不可能通过删除字符来使字符串变得漂亮,那么它的丑陋度为 - 1。
Limak 有一个长度为 n 的字符串 s,字符索引为 1 到 n。他问你q个问题。在第 i 个查询中,您应该计算并打印 s 的子字符串(连续子序列)的丑陋性,该子字符串从索引 ai 开始,到索引 bi(含)结束。
输入
输入的第一行包含两个整数 n 和 q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000)——分别是字符串 s 的长度和查询的数量。
第二行包含长度为 n 的字符串 s。每个字符都是数字“0”–“9”之一。
接下来 q 行的第 i 行包含两个整数 ai 和 bi (1 ≤ ai ≤ bi ≤ n),描述第 i 个查询中的子字符串。
输出
对于每个查询,打印给定子字符串的丑陋程度。
示例
输入 #1
8 3 20166766 1 8 1 7 2 8
输出 #1
4 3 -1
输入 #2
15 5 012016662091670 3 4 1 14 4 15 1 13 10 15
输出 #2
-1 2 1 -1 -1
输入 #3
4 2 1234 2 4 1 2
输出 #3
-1 -1
注意
在第一个示例中:
- 在第一个查询中,丑陋(“20166766”) = 4,因为必须删除所有四个六。
- 在第二个查询中,丑陋(“2016676”) = 3,因为必须删除所有三个六。
- 在第三个查询中,丑陋(“0166766”) = - 1,因为不可能删除一些数字来获得漂亮的字符串。
在第二个示例中:
- 在第二个查询中,丑陋(“01201666209167”) = 2。最好删除第一个数字“2”和最后一个数字“6”,这会给出字符串“010166620917”,这很好。
- 在第三个查询中,丑陋(“016662091670”) = 1。最好删除最后一个数字“6”,这会给出一个漂亮的字符串“01666209170”。