U138101 字符串水题

小 H 出了一道字符串水题，但他想要你帮他秒掉。 具体地，小 H 手上有一个数字串 S 。 于是他问出了 q 个问题，每个问题中包含另一个数字串 T 和两个非负整数 l, r ；他希望你对于 T 的每个在 S 中出 现过的、在 T 中出现位置不同的子串，确定当中有多少个子串，各位上的数字之和在 [l, r] 范围内。（即 T 中有两 个位置出现相同的子串，亦算作两个）

无

无

数据范围 对于 30% 的数据，|S|, q, Σ|T| ≤ 10^3； 对于 100% 的数据，1 ≤ |S|, q, Σ|T| ≤ 2 × 10^5, 0 ≤ l, r ≤ 9|T|。 #### 样例解释 对于第一个问题，有以下子串符合条件： 12,3 ，其各位数字和均为 3 。 对于第二个问题，有以下子串符合条件： 2,23,3,3,3 ，其各位数字和分别为 2,5,3,3,3 。 对于第三个问题，有以下子串符合条件： 23 ，其各位数字和为 5