子串去重

题号：NC307759
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个字符串 $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}$ 。
特别地，两个长度不同的子串中，较长串的多出的部分每个位置都视为不同。

输入描述:

输入第一行包含一个字符串 。
第二行包含一个整数 ，表示询问次数。
接下来  行，每行包含四个整数，表示一次询问。

输出描述:

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

示例1

输入

复制

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

输出

复制

0
1
2

备注:

对于 40% 的评测用例，, 。
对于 60% 的评测用例，。
对于 100% 的评测用例，, , 。