9542: 小塔的字符串

小塔是一位热衷于字符串研究的学者。最近她在研究字符串的前缀border特性时遇到了一个有趣的问题：给定一个字符串和多个查询，每个查询给出两个前缀，需要计算这两个前缀的所有公共border长度的两两异或平方和。这可以帮助她分析字符串前缀之间的相似性特征。

给定一个长度为$n$的字符串$S$，和$m$次询问。每次询问给出两个前缀SpSp和SqSq即字符串$S$的前$p$个和前$q$个字符，要求：

1. 找出SpSp和SqSq的所有公共border长度。其中一个长度$x$是字符串的border当且仅当长度为$x$的前缀和长度为$x$的后缀相同（其中border长度需要小于原字符串的长度）。
2. 计算这些公共border长度两两异或的平方和

数学表达式为：∑x∈Bp∩Bq∑y∈Bp∩Bq(x⊕y)2x∈Bp∩Bq∑y∈Bp∩Bq∑(x⊕y)2其中BkBk表示SkSk的所有border长度集合，$\oplus$表示按位异或运算。

第一行包含整数$T$，表示测试数据组数。

每组数据包含：

• 第一行两个整数$n,m$
• 第二行一个字符串$S$，仅包含小写字母
• 接下来$m$行，每行两个整数$p,q$

数据范围：

• $1\le T\le 5$
• 1≤n,m≤1051≤n,m≤105
• ∑n≤5×105∑n≤5×105
• ∑m≤5×105∑m≤5×105
• $1\le p,q\le n$