题目背景

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$）雪球之后，原单词才能成为「完美单词」。

样例 #1

样例输入 #1

aaaaa
2
1 2
4 5
2 4 1 5 3

样例输出 #1

2

样例 #2

样例输入 #2

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

样例输出 #2

5

样例 #3

样例输入 #3

abcd
1
1 4
1 2 3 4

样例输出 #3

0

提示

样例解释

第二个样例中的单词在分别被雪球砸掉之后的情况：

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$。