该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个字符串 $S$ 以及若干组询问，每个询问包含两个区间 $(L_a, R_a)$, $(L_b, R_b)$，你需要判定 $S_{L_a}, S_{L_a+1}, \ldots, S_{R_a}$ 与 $S_{L_b}, S_{L_b+1}, \ldots, S_{R_b}$ 去重后有多少个位置上的字符是不同的。

这里的去重指的是每个子串对于每种字符，只保留第一个出现的那个，后续出现的直接丢弃。

例如 $\tt{aabcbac}$ 在选中区间 $[1,5]$ 时，得到子串 $\tt{aabcb}$，去重后为 $\tt{abc}$，选中区间 $[3,6]$ 时得到 $\tt{bcba}$，去重后为 $\tt{bca}$。

特别地，两个长度不同的子串中，较长串的多出的部分每个位置都视为不同。

输入格式

输入第一行包含一个字符串 $S$。

第二行包含一个整数 $m$，表示询问次数。

接下来 $m$ 行，每行包含四个整数，表示一次询问。

输出格式

输出共 $m$ 行，每行一个整数对应每次询问的答案。

aabcbabacdab
3
1 1 2 2
1 10 6 9
4 7 9 12

0
1
2

数据范围

对于 40% 的评测用例，$|S| \leq 10$, $m = 1$。

对于 60% 的评测用例，$|S|, m \leq 5000$。

对于 100% 的评测用例，$1 \leq |S|, m \leq 10^5$, $1 \leq L_a \leq R_a \leq |S|$, $1 \leq L_b \leq R_b \leq |S|$。