Problem Background

Patrik loves studying English words, especially those that contain exactly $N$ letters. When he encounters such words, he immediately begins analyzing their $Q$ subwords. If these $Q$ subwords have no repeating letters, he calls the original word a "perfect word."

Krešimir, on the other hand, prefers to throw snowballs at Patrik. One cold winter morning, while wandering the city with $N$ snowballs, he suddenly bumped into Patrik, who was studying a word containing $N$ letters.

Krešimir threw his $N$ snowballs at Patrik, with the $i$-th snowball hitting the $p_i$-th letter of the word.

Problem Description

Patrik has decided to redefine a "perfect word": For a word of length $N$ with $Q$ subwords, if all the uncovered letters of the subwords do not repeat, the original word is called a "perfect word."

He wants to know after how many snowball hits the original word becomes a "perfect word."

Input Format

The first line contains a word consisting of lowercase English letters, with a length of $N$.

The second line contains an integer $Q$.

The next $Q$ lines, the $i$-th line contains two integers $a_i$ and $b_i$. This indicates that the $i$-th subword is a continuous segment from the $a_i$-th to the $b_i$-th letter of the original word.

The next line contains $N$ distinct integers $p_i$.

Output Format

Output the answer Patrik wants to know, which is the number of snowball hits (possibly zero) after which the original word becomes a "perfect word."

Sample Input and Output

Sample Input #1

aaaaa
2
1 2
4 5
2 4 1 5 3

Sample Output #1

2

Sample Input #2

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

Sample Output #2

5

Sample Input #3

abcd
1
1 4
1 2 3 4

Sample Output #3

0

Notes

Sample Explanation

In the second sample, the word's state after being hit by snowballs:

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

Data Size and Constraints

For $20\%$ of the data, $1 \le N,Q \le 500$.

For another $30\%$ of the data, $1 \le N,Q \le 3000$.

For another $20\%$ of the data, the original word contains only the letter a.

For $100\%$ of the data, $1 \le N,Q \le 10^5$, $1 \le a_i \le b_i \le N$, $1 \le p_i \le N$.

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $70$.

Since each test case averages $2.5$ points, half of the test cases are set to $2$ points, and the other half to $3$ points.

The problem is translated from COCI2019-2020 CONTEST #3 T2 Grudanje.

见题面 Input 部分

见题面 Output 部分