# 告示牌识别

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

村里的旧存档丢失了告示牌的文字含义，但仍保留了字符序列。为了比较书写习惯，管理员想统计只在某一块告示牌上出现、而不会出现在其他告示牌上的片段。

## 形式化问题描述

给定 $n$ 个非空小写字母字符串。字符串 $s_i$ 的一次子串出现由下标区间 $[l,r]$ 唯一确定。

如果这段子串的内容在其他所有字符串 $s_j$（$j\ne i$）中都不出现，就称这次出现为独有子串。**同一字符串中不同位置的出现分别计数，即使内容相同**。若内容还出现在其他字符串中，它在所有字符串中的出现都不独有。

对每个询问 $[L,R]$ ，输出所有字符串中长度在该闭区间内的独有子串出现次数之和。

## 输入格式

第一行两个整数 $n,q$ .接下来 $n$ 行，每行一个字符串。接下来 $q$ 行，每行两个整数 $L,R$ .

## 输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

## 样例 1

### 输入

```text
2 1
aababab
bbaabaa
2 10
```

### 输出

```text
24
```

## 样例 2

### 输入

```text
2 3
aaa
b
1 1
2 3
4 10000000000
```

### 输出

```text
4
3
0
```

## 样例 3

### 输入

```text
2 1
aaa
aaa
1 3
```

### 输出

```text
0
```

## 样例解释

样例 2 中，`aaa` 的三个 `a` 和 `b` 的一个 `b` 都独有，因此长度为 $1$ 的答案是 $4$ .长度为 $2$ 的 `aa` 出现两次，长度为 $3$ 的 `aaa` 出现一次。样例 3 中两串相同，没有独有子串。

## 数据范围与保证

所有数据满足 $1\le n,q\le5$ ，每个字符串长度在 $[1,50000]$ 内，仅含 `a` 到 `z` ，且 $1\le L\le R\le10^{10}$ .不同字符串可以相同。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |