【题目描述】

在一个古老的玛雅文明中，存在着一种神秘的仪式称为“拉达玛特克”。

在这个仪式中，祭司们会通过特殊符号序列（字符串 $t$）祈祷来向神灵传达他们的祈愿，然后神灵会告知他们字符串 $t$ 在某个特定字符串 $s$ 中的出现次数。

其中字符串 $t$ 是根据特定的宗教活动、天象、季节等因素 随机生成的，具体地，设 $a,b,c,d$ 为祭司们最后确定的参数，则他们首先计算 $x_{i+1}=(ax_i+b)%c$（特别地 $x_1=b%c$）。然后长度为 $d$ 的符号序列 $t$ 的第 $i$ ($1\le i\le d$) 个字符会被确定为第 $x_i%26+1$ 个小写字母。

据记载，玛雅文明共进行了 $m$ 次神秘的仪式，特定字符串 $s$ 以及每次仪式的参数都被完好地保存了下来，但神灵的回答却无从得知。作为一个考古学家，你能够使用你的编程技巧帮助恢复神灵的回复吗？

【输入格式】

输入的第一行包含一个字符串 s，保证 s 只包含小写字母。 第二行包含一个整数 m，表示查询的次数。 接下来的 m 行，每行包含四个 随机生成 的整数 a, b, c, d，表示含义如题面所述。

【输出格式】

输出 m 行，第 i 行表示第 i 个符号序列 ti 在给定符号序列 s 中出现的次数。

【样例数据】

cacbdcbcabcdcaaddabba
1
1 1 3 5

1

cababbbdadadcbbbcadddac
1
2 1 3 4

0

【数据范围】

1. 对于 $10%$ 的测试点，$1\le |s|\le 1000$, $1\le m\le 2000$；
2. 对于 $20%$ 的测试点，$1\le |s|\le 10^4$, $1\le m\le 10^5$；
3. 对于另外 $20%$ 的测试点，$m$ 个询问的 $d$ 之和没有限制（这部分数据有问题直接复制粘贴的有效数据所以 $d$ 之和超了）。
4. 对于另外 $20%$ 的测试点，保证所有询问的 $a=1$，且 $d$ 是 $c$ 的倍数；
5. 对于另外 $20%$ 的测试点，$m$ 个询问的 $d$ 最大值小于 500；
6. 对于所有测试点，$1\le |s|\le 5 × 10^4$, $1\le m\le 10^5$, $0\le a, b\le 500$,$1\le c\le 500$, $1\le d\le |s|$。