### 问题描述 莉莉有一个字符串蛋糕，该字符串 $s$ 由 $n$ 个小写字母组成。 现在有 $q$ 名顾客，每名顾客会给莉莉两个位置 $l,r$，表示位于位置 $l$ 与位置 $r$（包括 $l,r$）之间的子串是顾客需要的蛋糕部分。同时，顾客们还有一个要求。顾客希望莉莉能把他们需要的蛋糕部分再次切成若干段，使得至少有两个段的字符是完全相同的。 莉莉为一个顾客提供服务的成本与切分的段中不同的段的个数有关，一个不同的段需要的成本为 $x$。 请你告诉莉莉为顾客提供切蛋糕服务所需要的最小成本，或者告诉顾客他选择的蛋糕段无法满足其要求。 ### 输入格式 输入第一行包含两个整数 $n,x$，含义见上文。 第二行包含一个字符串 $s$，表示蛋糕。 第三行包含一个整数 $q$，表示顾客的个数。 接下来的 $q$ 行，每行包含两个整数 $l,r$，表示顾客提出的两个位置。 ### 输出格式 输出共 $q$ 行，每行输出一个整数，第 $i$ 行表示为第 $i$ 名顾客提供切蛋糕服务所需要的最小成本。若其选择的蛋糕段无法满足其要求，输出 $-1$。 ### 样例输入 ``` 9 3 abcabcdce 7 1 6 4 7 5 9 6 9 1 9 3 6 4 4 ``` ### 样例输出 ``` 3 -1 12 9 6 6 -1 ``` ### 评测数据规模 对于所有评测数据，$1\leq{n}\leq{2\times 10^5 },1\leq{q}\leq{2\times 10^5 },1\leq{l}\leq{r}\leq{n},1\leq{x}\leq{10^3 }$。