题目背景

题目描述

由于你让我看到了世界的绮丽，所以需要解决一道题目。

定义 $f(a,b)$ 为字符串 $a$ 在 $b$ 中出现的次数。

给出 $n$ 个只包含小写字母的字符串 $s_1,\dots,s_n$，$q$ 次询问 $l,r,L,R$，求：

输入格式

第一行输入两个正整数 $n,q$。

接下来 $n$ 行输入 $n$ 个只包含小写字母的字符串 $s_1,\dots,s_n$。

接下来 $q$ 行输入 $q$ 个询问 $l,r,L,R$。

输出格式

输出 $q$ 个正整数，为每个询问的答案。

5 5
a
ab
abab
ababab
b
1 5 4 5
3 5 4 5
1 5 2 4
1 5 3 5
2 4 3 4

13
7
22
20
9

提示

记 $m=\sum\limits_{i=1}^n|s_i|$。

对于 $100\%$ 的数据，满足 $1\le n,m,q\le 2\times 10^5$，$1\le l\le r\le n$，$1\le L\le R\le n$。