题目描述

给定一个字符串 S 以及若干组询问，每个询问包含两个区间 (La​,Ra​), (Lb​,Rb​)，你需要判定 SLa​​,SLa​+1​,…,SRa​​ 与 SLb​​,SLb​+1​,…,SRb​​ 去重后有多少个位置上的字符是不同的。

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

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

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

输入格式

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

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

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

输出格式

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

样例

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

0
1
2

说明/提示

【评测用例规模与约定】

对于 40% 的评测用例，∣S∣≤10, m=1。

对于 60% 的评测用例，∣S∣,m ≤ 5000。

对于 100% 的评测用例，$1≤∣S∣$,$m≤10^5$, $1≤La​≤Ra​≤∣S∣$, $1≤Lb​≤Rb​≤∣S∣$。