#1652. 复读程度

    ID: 1652 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1031来源:qoj.ac数据:公开样例字符串前缀和二分

复读程度

复读程度

题目描述

标题: 复读程度 - Problem - QOJ.ac

#5014. 复读程度

Statistics

The problem was used in the following contests:

题目描述

给定字符串 ,第 个字符被赋予两个权值:左权值 和右权值

定义一个子串 的左权值 为: 其在原串中各个匹配的左端点的左权值 和;右权值 为: 其在原串中各个匹配的右端点的右权值 和。这里 在 中所有的 匹配是 ,我们把这样的 和 分别叫做一个匹配的左右端点。

定义一个子串 的复读程度是它的左权值与右权值的乘积,即 。

次查询 ,令 ,即以 为所有满足 为 的前缀, 为 的后缀的 的集合。求 。

由于答案很大,你只需要输出答案对 取模后的结果。

输入格式

第一行两个正整数 ,表示字符串长度与查询次数。

第二行一个由小写字母构成的字符串 。

第三行 个整数 表示左权值。

第四行 个整数 表示右权值。

接下来 行,每行给出四个整数 ,表示一次查询。

输出格式

行,第 行输出第 次查询的答案对 取模后的结果。

样例数据

样例输入

6 5
ababcc
1 1 1 1 1 1
1 1 1 1 1 1
1 1 5 5
3 4 1 2
1 1 2 2
1 2 6 6
5 5 1 2

样例输出

4
9
9
4
0

子任务

保证 仅有小写字母构成。

  • subtask1(7pts):保证 。
  • subtask2(15pts):保证 。
  • subtask3(12pts):保证 。
  • subtask4(6pts): 保证 , 且对任意 ,有 。
  • subtask5(16pts):保证 在 中最多出现 5 次。
  • subtask6(21pts):保证 。
  • subtask7(23pts):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 5
ababcc
1 1 1 1 1 1
1 1 1 1 1 1
1 1 5 5
3 4 1 2
1 1 2 2
1 2 6 6
5 5 1 2
4
9
9
4
0