Patrik loves to study words in the English language. He especially loves words that contain exactly letters. When he sees such a word, he instantly starts observing 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 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 snowballs and stumbled upon Patrik who was observing a giant -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 -st letter of the word on a wall. In a similar manner, Krešimir failed to hit Patrik with the next snowballs. More precisely, his -th snowball missed Patrik and completely covered the -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 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 lowercase letters from the English alphabet.
The second line contains an integer from the task description.
The -th of the next lines contains two integers and which denote that the -th of the subwords from the task description spans from -th to the -th letter of the word on a wall.
The next line contains different integers 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 points, it will hold .
In test cases worth additional points, it will hold .
In test cases worth additional 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
Comments