Background

Patrik loves studying English words. He especially likes words that contain exactly $N$ letters. When he sees a word that meets this condition, he immediately starts analyzing its $Q$ substrings. If the letters in these $Q$ substrings are all different, then he calls the original word a "perfect word".

Krešimir is different: he prefers throwing snowballs at Patrik. On a cold winter morning, while he was wandering around the city holding $N$ snowballs, he suddenly ran into Patrik, who was studying a word of length $N$.

Krešimir threw his $N$ snowballs at Patrik. The $i$-th snowball hit exactly the $p_i$-th letter of the word.

Problem Description

Patrik decided to redefine "perfect word": for the $Q$ substrings of a word of length $N$, if the parts of the substrings that are not covered by snow have no repeated letters, then the original word is called a "perfect word".

He wants to know after Krešimir has thrown how many snowballs the original word becomes a "perfect word".

Input Format

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

The second line contains an integer $Q$.

The next $Q$ lines each contain two integers $a_i, b_i$. This means the $i$-th substring is taken as a continuous segment from the $a_i$-th letter to the $b_i$-th letter of the original word.

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

Output Format

Output the answer Patrik wants to know, i.e., after throwing how many (possibly $0$) snowballs the original word can become a "perfect word".

aaaaa
2
1 2
4 5
2 4 1 5 3

2

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

5

abcd
1
1 4
1 2 3 4

0

Hint

Sample Explanation

In the second sample, the word after being hit by snowballs one by one is:

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

Constraints

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

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

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

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

Notes

The score of this problem follows the original COCI setting, with a full score of $70$.

Since on average each test point is worth $2.5$ points, half of the test points are set to $2$ points and the other half are set to $3$ points.

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

Translated by ChatGPT 5