Bob is busy studying a word!

He currently has a word that contains \(N\) letters. He is very interested in the word and will ask \(Q\) questions about its "subwords" (a contiguous range of the letters) and determine whether it is interesting or not.

However, Anna does not like Bob's word and loves to cross out letters in Bob's word. Every time Bob looks away, she will cross out one of the letters that have not been crossed out yet. She continues to do this \(N - 1\) more times until the entire word is crossed out.

With everything crossed out, Bob needs to alter his definition of an interesting word. The word is interesting if none of the \(Q\) subwords contain two identical letters that have not been crossed out.

Now Bob has a new question: after which of Anna's crosses (possibly zero crosses) does the word start being interesting? As Bob is desperate for new friends, please help him out.

For this problem, Python users should submit their submissions in PyPy over CPython.

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)\), representing the number of subwords Bob is interested in.

The \(i\)-th of the next \(Q\) lines contains two integers \(L\) and \(R\) \((1 \le L \le R \le N)\) which denote that the \(i\)-th of the \(Q\) subwords is the substring from the \(L\)-th to the \(R\)-th letter of the word.

The next line contains a permutation of \(N\) integers \(p_i\) \((1 \le p_i \le N)\). The \(i\)-th integer in the permutation indicates that the \(p_i\)-th letter in the word was just crossed out by Anna.

Output

Output one integer, indicating after how many crosses (possibly zero crosses) did the word become interesting.

Subtasks

Note that you will not be required to pass the sample input to receive points for the subtasks. Additionally, you will not be required to pass subtask 1/2 in order to get points on subtask 3.

Subtask 1 [10%]

\(1 \le N, Q \le 500\)

Subtask 2 [20%]

\(1 \le N, Q \le 3000\)

Subtask 3 [15%]

The word will only contain the letter a.

Subtask 4 [55%]

No additional constraints.

Sample Input 1

aaaaa
2
1 2
4 5
2 4 1 5 3

Sample Output 1

2

Explanation for Sample Output 1

The state of the word after each cross is:

a-aaa
a-a-a (Interesting)
--a-a
--a--
-----

The word a-a-a is interesting and requires \(2\) crosses.

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 after each cross is:

abbab-ab
ab-ab-ab
ab-a--ab
-b-a--ab
-b----ab (Interesting)
------ab
-------b
--------

Sample Input 3

abcd
1
1 4
1 2 3 4

Sample Output 3

0

Explanation for Sample Output 3

The word was already interesting and requires \(0\) crosses.