问题描述

给定一个长度为 n 的字符串 S，以及 m 次查询。

每次查询给出两个区间 [$l_1​,r_1$​] 和 [$l_2​,r_2$​]，要求判断子串 S[$l_1​,r_1$​] 和 S[$l_2​,r_2$​] 是否相等，并统计所有查询中相等的次数。

注意：

• 字符串下标从 1 开始。

• $n, m \le 2 \times 10^5$，子串长度总和可能很大。

输入格式

第一行两个整数 n, m，表示字符串长度和查询次数。
第二行一个长度为 n 的字符串 S。
接下来 m 行，每行四个整数 $l_1​,r_1​,l_2​,r_2$​，表示一次查询。

输出格式

一个整数，表示所有查询中两个子串相等的次数。

样例输入

10 3
abacabaaba
1 3 5 7
2 4 7 9
1 4 6 9

样例输出

1

样例解释

• 查询 1: "aba" 与 "aba" ✅

• 查询 2: "bac" 与 "aba" ❌

• 查询 3: "abac" 与 "aaba" ❌
  所以输出 1。

数据范围

• $n \le 2 \times 10^5, m \le 2 \times 10^5$

• 字符串由小写英文字母随机生成

• 查询区间长度平均为 $10 \sim 100$，但总子串数量巨大