E-不平衡的字符串_第十八届同济大学程序设计竞赛暨高校网络友谊赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

Miaoyao认为平衡的字符串是最美的。但是强大的lhl322对字符串有着更为挑剔的审美。他认为，美观的字符串中应当有一个字符出现次数足够多，这样才显得整齐；但如果全是一种字符又会非常单调。

给出一个长度为n的字符串S，以及m个约束。第i个约束要求字符串中字符 $s_i$ 个数与串长之比k满足 $\frac{a}{b}<k \le \frac{c}{d}\$ 。

lhl322认为，字符串只有至少满足了这m个约束中的一个，才是美观的。他想要知道S有多少个子串是美观的。

第一行一个整数n，表示字符串S的长度。
接下来一行n个字符，即字符串S。保证S只包含小写字母。
接下来一行一个整数m，表示约束个数。
接下来m行，每行包括一个小写字母s及四个整数a,b,c,d，表示存在一个约束，要求s在串中出现比例处在 之间。保证。
对于同一个字符，不会有两个不同的约束。

一个整数，表示至少满足一个约束的子串个数。

示例1

复制

6
aabaab
2
a 1 2 1 1
b 1 2 1 1

复制

对于样例中所给出的字符串，它共有21个子串。其中，只有ab、ba、baab、ab这四个子串不满足任意一个约束，其余17个子串均符合题意。


保证S只包含小写字母。
保证对于同一个字符，不会有两个不同的约束。
保证，。