[COCI2019-2020#3] Grudanje

Patrik 热爱研究英语单词。他尤其喜欢正好包含 $N$ 个字母的单词。他看到满足这种条件的单词时，便立即开始分析这个单词的 $Q$ 个子单词。如果这 $Q$ 个子单词的字母各不相同，那么他称原单词为「完美单词」。 Krešimir 则不然，他则更喜欢朝 Patrik 扔雪球。在一个寒冷的冬天早晨，正当他在城中拿着 $N$ 个雪球游荡时，却突然撞到正在研究一个包含 $N$ 个字母的单词的 Patrik。 Krešimir 向 Patrik 扔出了他的 $N$ 个雪球，其中第 $i$ 个雪球正好不偏不倚地砸在单词的第 $p_i$ 个字母上。

Patrik 决定重新对「完美单词」作出定义：对于一个长度为 $N$ 的单词的 $Q$ 个子单词，如果所有的子单词的未被雪覆盖的字母部分没有重复，那么原单词被称为「完美单词」。 他想知道 Krešimir 在砸了几个雪球之后，原单词就成为了「完美单词」。

第一行包含一个只有小写英文字母的单词，其长度为 $N$。 第二行包含一个整数 $Q$。 接下来的 $Q$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。这表示第 $i$ 个子单词是从原单词的第 $a_i$ 个字母至第 $b_i$ 个字母连续截取而来。 接下来的一行，包含 $N$ 个互不相同的整数 $p_i$。

输出 Patrik 想要知道的答案，即输出在砸了几个（可能为 $0$）雪球之后，原单词才能成为「完美单词」。

aaaaa
2
1 2
4 5
2 4 1 5 3

2

abbabaab
3
1 3
4 7
3 5
6 3 5 1 4 2 7 8

5

abcd
1
1 4
1 2 3 4

0

#### 样例解释 第二个样例中的单词在分别被雪球砸掉之后的情况： ```plain abbab*ab ab*ab*ab ab*a**ab *b*a**ab *b****ab ******ab *******b ******** ``` #### 数据规模及约定 对于 $20\%$ 的数据，$1 \le N,Q \le 500$。 对于另外 $30\%$ 的数据，$1 \le N,Q \le 3000$。 对于另外 $20\%$ 的数据，原单词只包含字母 `a`。 对于 $100\%$ 的数据，$1 \le N,Q \le 10^5$，$1 \le a_i \le b_i \le N$，$1 \le p_i \le N$。 #### 说明 **本题分值按 COCI 原题设置，满分 $70$。** 由于平均下来每个测试点为 $2.5$ 分，因而将其中一半的测试点设置为 $2$ 分，另一半设置为 $3$ 分。 **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf) _T2 Grudanje_ 。**