题目背景

gzy是一个神仙OI选手。所以他是这道题的主人公。

题目描述

gzy有一个仅包含小写英文字母的字符串$S$。 gzy有$q$组询问,每组询问给出$[l,r]$,你需要将$S[l...r]$划分成若干个子串，使得这些子串中至少有两个相同的,且本质不同的种数最小。你需要回答这个种数最小是多少。如果不存在合法的划分方案,输出$-1$。

输入格式

输入的第一行包含两个正整数$n,q$。

接下来一行，一个长度为$n$的字符串$S$。

接下来$q$行，每行$2$个整数$l,r$，第$i$行表示第$i$组询问的$l,r$。

输出格式

输出$q$行，每行一个整数，第$i$行表示第$i$次询问的答案。

样例1输入

9 7
abcabcdce
1 6
4 7
5 9
6 9
1 9
3 6
4 4

样例1输出

1
-1
4
3
2
2
-1

样例1解释

考虑第一组询问。你将要划分的串为$s[1...6]$="abcabc"。

对于这个子串,有很多种合法的划分方案,例如:

"a"|"bc"|"a"|"bc",本质不同的子串有"a","bc"两种。

"a"|"b"|"c"|"a"|"b"|"c" ,本质不同的子串有"a","b","c"三种。

"abc"|"abc",本质不同的子串有"abc"一种,且容易验证这是最优解。

子任务

温馨提示

题目并不难。自古以来OI比赛T3最水，你一定能切掉此题！

时间限制：$3\text{s}$

空间限制：$512\text{MB}$