Patrik loves to study words in the English language. He especially loves words that contain exactly $N$ letters. When he sees such a word, he instantly starts observing $Q$ of its subwords and for each of those subwords he determines whether all of its letters are distinct. If that is the case for each of the $Q$ subwords, then he considers the original word to be perfect.

Krešimir doesn't love studying English words, he loves to throw snowballs at Patrik instead. On a cold, winter morning, he was walking around town carrying exactly $N$ snowballs and stumbled upon Patrik who was observing a giant $N$-lettered word that was written on the wall by some hooligans. What a coincidence…

Krešimir fiercely threw the first snowball in Patrik's direction, but Patrik skillfully dodged the snowball so it hit and completely covered the $p_1$-st letter of the word on a wall. In a similar manner, Krešimir failed to hit Patrik with the next $N-1$ snowballs. More precisely, his $i$-th snowball missed Patrik and completely covered the $p_i$-th letter of the word on a wall. Interestingly enough, after Krešimir threw all of the snowballs, the entire word was covered in snow.

Patrik glanced at the completely covered word and concluded that it was perfect. Therefore, he needed to slightly alter his definition of a perfect word. The word is perfect if none of the $Q$ subwords contain two equal letters that are not covered in snow. Now he wants to know after which snowball (possibly zero) did the word on the wall become perfect.

Input

The first line contains a word that consists of $N$ $(1\le N\le {10}^5)$ lowercase letters from the English alphabet.

The second line contains an integer $Q$ $(1\le Q\le {10}^5)$ from the task description.

The $i$-th of the next $Q$ lines contains two integers $a_i$ and $b_i$ $(1\le a_i\le b_i\le N)$ which denote that the $i$-th of the $Q$ subwords from the task description spans from $a_i$-th to the $b_i$-th letter of the word on a wall.

The next line contains $N$ different integers $p_i$ $(1\le p_i\le N)$ from the task description.

Output

In the only line you should output after which snowball (possibly zero) did the word on the wall become perfect.

Scoring

In test cases worth a total of $14$ points, it will hold $1\le N,Q\le 500$.

In test cases worth additional $21$ points, it will hold $1\le N,Q\le 3000$.

In test cases worth additional $14$ points, the word will only contain letters a.

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

Explanation for Sample Output 2

The state of the word on the wall after each thrown snowball is:

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

Sample Input 3

abcd
1
1 4
1 2 3 4

Sample Output 3

0