P7204 [COCI 2019/2020 #3] Grudanje

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.

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".

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 the answer Patrik wants to know, i.e., after throwing how many (possibly $0$) snowballs the original word can become a "perfect word".

#### Sample Explanation In the second sample, the word after being hit by snowballs one by one is: ```plain 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](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf) _T2 Grudanje_.** Translated by ChatGPT 5