Patrik 喜欢研究英文单词。他特别喜欢恰好包含 $N$ 个字母的单词。当他看到这样一个单词时，他会立即开始观察它的 $Q$ 个子串，并对于其中的每一个子串，判断其所有字母是否互不相同。如果这 $Q$ 个子串中的每一个都满足该条件，那么他就认为原单词是“完美”的。

Krešimir 不喜欢研究英文单词，相反，他喜欢向 Patrik 扔雪球。在一个寒冷的冬日早晨，他带着恰好 $N$ 个雪球在镇上散步，偶遇了正在观察墙上由一些流氓写下的一个巨大的 $N$ 字母单词的 Patrik。真是太巧了……

Krešimir 猛烈地向 Patrik 的方向扔出了第一个雪球，但 Patrik 敏捷地躲过了雪球，于是雪球击中并完全覆盖了墙上单词的第 $p_1$ 个字母。类似地，Krešimir 接下来的 $N - 1$ 个雪球也没能击中 Patrik。更具体地说，他的第 $i$ 个雪球没有打中 Patrik，而是完全覆盖了墙上单词的第 $p_i$ 个字母。有趣的是，在 Krešimir 扔完所有的雪球后，整个单词都被雪覆盖了。

Patrik 看了看被完全覆盖的单词，并得出结论它是完美的。因此，他需要稍微修改一下他对完美单词的定义。如果这 $Q$ 个子串中，没有任何一个子串包含两个未被雪覆盖的相同字母，那么这个单词就是完美的。现在他想知道，在扔出第几个雪球（可能为零）之后，墙上的单词变得完美了。

输入格式

第一行包含一个由 $N$（$1 \le N \le 10^5$）个英文小写字母组成的单词。

第二行包含一个整数 $Q$（$1 \le Q \le 10^5$），表示子串的数量。

接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le b_i \le N$），表示第 $i$ 个子串在墙上单词中的范围是从第 $a_i$ 个字母到第 $b_i$ 个字母。

最后一行包含 $N$ 个互不相同的整数 $p_i$（$1 \le p_i \le N$），表示雪球击中的字母位置。

输出格式

输出唯一的一行，包含一个整数，表示在扔出第几个雪球（可能为零）之后，墙上的单词变得完美。

子任务

• 在占总分 14 分的测试数据中，满足 $1 \le N, Q \le 500$。
• 在另外占总分 21 分的测试数据中，满足 $1 \le N, Q \le 3000$。
• 在另外占总分 14 分的测试数据中，单词仅包含字母 'a'。

样例

输入样例 1

aaaaa
2
1 2
4 5
2 4 1 5 3

输出样例 1

2

输入样例 2

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

输出样例 2

5

输入样例 3

abcd
1
1 4
1 2 3 4

输出样例 3

0

说明

样例 2 解释

每次扔出雪球后，墙上单词的状态如下（被雪覆盖的字母用 * 表示）：

abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********