题目描述

定义F(U,V)为选择U的非空前缀S、V的非空后缀T，使ST为回文串的长度选择对数。给定A、B，将后缀和前缀均按长度从长到短编号：A_x=A[x..|A|]，B_y=B[1..|B|−y+1]。每次查询x,y，输出F(A_x,B_y)。不同前缀或后缀长度算不同方案，不按字符串值去重。

本题为一本通1694的公开本地训练修订版。

输入

第一行类型字符A/B/C，仅为兼容源数据的说明字段，不限制实际算法。随后A、B各一行，仅小写字母，长度1..8×10^5；接着Q及Q组x y，1≤Q≤10^5，1≤x≤|A|，1≤y≤|B|。

输出

每组查询输出一行精确64位整数。

输入样例

B
newionyzz
wyxioiwen
1
1 1

输出样例

16

修订说明

修复原文混用A/B和S/T的记号，明确第i长是从长到短，query1,1对应完整两串，与16方案样例一致；保留完整8e5/1e5范围，不依赖随机子任务。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：修复原文混用A/B和S/T的记号，明确第i长是从长到短，query1,1对应完整两串，与16方案样例一致；保留完整8e5/1e5范围，不依赖随机子任务。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1694。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。