CF589C.Polycarp's Masterpiece

受乔安娜·罗琳及其《哈利·波特》幻想系列的成功启发，Polycarp 决定创作自己的杰作。他已经为他未来的畅销书取好了名字 —— 字符串 $s$。

Polycarp 在撰写主线故事时遇到了不少困难，于是决定成为文学界的“马列维奇”，创作属于自己的“黑方块”。

Polycarp 用了 $n$ 天来写作，每天写一章。他首先写下了字符串 $s$。在接下来的 $n$ 天里，每一天他都执行以下步骤：在第 $i$ 天，他把当前文本 $t$ 的第 $k_i$ 次循环移位的结果追加到右边。也就是说，每天他的作品内容长度都会翻倍。

一个字符串 $r$ 的循环移位定义为将 $r$ 最后的一个字符移动到字符串的最前面。例如，“masterpiece”的一次循环移位是“emasterpiec”。字符串 $r$ 的第 $i$ 次循环移位是指对 $r$ 连续执行 $i$ 次循环移位后的结果（比如“masterpiece”的第三次循环移位是“ecemasterpi”）。

经过 $n$ 天的辛勤创作，Polycarp 终于写下了一篇非常长的文本，堪称付出的努力。然而，这部作品内容实在太长，几乎无法对其进行任何分析。

请你帮助 Polycarp 回答 $m$ 个关于他作品的查询：对于第 $j$ 个查询，找出在自己的巨著的第 $l_{j}$ 位到第 $r_{j}$ 位（含）构成的子串中，字母 $c_{j}$ 出现了多少次。

第一行给出巨著的名字 —— 字符串 $s$。$s$ 仅包含小写拉丁字母，长度在 $1$ 到 $100$ 之间。

第二行包含两个整数 $n$ 和 $m$ $(1 \le n \le 10^5,\, 1 \le m \le 10^5)$ —— Polycarp 写作的天数和查询的个数。

下一行包含 $n$ 个整数 $k_i$ $(0 \le k_i \le 100)$ —— 第 $i$ 天所使用的循环移位次数。

接下来的 $m$ 行，每行包含两个整数 $l_j$、$r_j$ 和一个小写拉丁字母 $c_j$ —— 每个查询的描述。对于每个查询，你需要统计在巨著的第 $l_j$ 个位置到第 $r_j$ 个位置（含）组成的子串中，字母 $c_j$ 出现了多少次。位置从 $1$ 开始编号。保证 $1 \leq l_j \leq r_j \leq 10^{18}$ 且 $l_j$ 和 $r_j$ 都不会大于作品实际长度。

输出 $m$ 行，第 $j$ 行表示第 $j$ 个查询的答案。

由 ChatGPT 5 翻译