You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

“今日扫描已完成。Pantw，男，21岁，当前综合评价：$A-$。”

“快到 4.0 了吗……能得到你的认可真不容易啊。”

“这得益于宿主与 MSF_Akatsuki 先生的通力合作，走出了一条令人……呃，令评价算法意外的偶像道路。”

“嗯……但是说实话，系统，你真的愿意看到我走到那个无法估量的境界吗？”

“当然，宿主。4.0 是每个人都想追求的。”

“好吧，你说是那就是。但这一票，对我们很重要。你别给我出什么幺蛾子。”

“系统会尽力的。”

题目描述

葡萄味花了老半天才给他身上的系统解释清楚，自己现在叫“南小鸟”而不是“南琴梨”（尽管系统觉得平假名写法都一样实在搞不懂宿主为什么要区分开）。这个伴随他降临而诞生的系统似乎并不是真心想让它的宿主变强，尽管它和其他系统一样呆萌、腹黑和关键时刻似乎并不脱线，但作为一名现充，穿越前的三次元生活经验还是让他持续着若即若离的姿态。不过系统似乎也没有给他带来很多好处，现在唯一的召唤物就是这个和他名字很配的二元葡萄。

这个二元葡萄 $S$ 是一个链状的葡萄串，葡萄串上的每个葡萄都是 26 个品种中的其中一种（为了方便，用小写字母表示当前每个字母的品种）。它的“二元”性体现在使用方法上：选取它的两个子串 $A,B$，二元葡萄就会告诉你 $B$ 有多少个包含 $A$ 的子串。这个能力看起来毫不起眼，但在潘达和 knb 的帮助下，他们已经破解了无数个城市数据库里的机密情报。当然，它的能力使用也有限制，使用 $q$ 次后就会过热一段时间。如今他们又有了新的任务，作为二元葡萄，你不需要关心其他的事情，做好你的本职工作就可以了。

数据格式与约定

输入

输入第一行为一个字符串 $S(|S| \le 2\times10^5)$，表示二元葡萄，下标从 $1$ 开始。

接下来一行包含一个整数 $q(q \le 2\times10^5)$，表示使用二元葡萄的次数。

接下来 $q$ 行，每行包含四个正整数 $a, b, c, d (1 \le a \le b \le |S|, 1 \le c \le d \le |S|)$，$S_{a \to b}$ 对应第一个子串 $A$，$S_{c \to d}$ 对应第二个子串 $B$。

输出

输出包含 $q$ 行，每行一个整数 $ans$，表示对应的答案。

样例

wwqwq
3
1 2 3 5
2 3 1 5
4 4 1 5

0
8
13

后记

“如果我们不是第一个尝试解开这一切的队伍，如果有人告诉我，曾经的那些人都已经不见了，如果有人觉得这个世界变成这样也没什么大不了……你该怎么办？我们要怎么办？”

“通常情况下这么多如果只会出现在轻小说剧情里。至于我们，寄就寄呗，反正都不知道咋回去，推动剧情进度就算成功。”

——OIER 小队未知子网聊天日志，发言者和发言时间对应的唯一识别码已被恶意涂改，无法辨认