Problem description

Johnny, niepoprawny romantyk, znowu narobił bałaganu w swoim życiu uczuciowym. Uwielbia flirtować i sypać tandetnymi komplementami, co – o dziwo – czasami działa. Niestety, Johnny ma pamięć krótszą niż… zarost na jego gładkim licu. Jedyną rzeczą, jaką zapisuje w swoim telefonie, są numery telefonów dziewczyn oraz pierwsze litery ich imion.

Ale jest problem. Niektóre dziewczyny zablokowały Johnny’ego (i nie bez powodu). Kiedy tak się dzieje, numer w jego telefonie pozostaje bez litery, a Johnny zupełnie go ignoruje.

Dziś są Walentynki – najważniejszy dzień w życiu Johnny’ego. Marzy o tym, by umówić się na randki z kilkoma dziewczynami. Jednak jego sposób wyboru jest, delikatnie mówiąc, niecodzienny:

1. Johnny wybiera spójny przedział ze swojej listy N numerów, np. przedział od 3 do 7.

2. Następnie patrzy na litery przypisane do numerów w tym przedziale (włącznie z końcami przedziału). Jeśli jakaś litera pojawia się więcej niż raz, Johnny jest zbyt zagubiony, by zadzwonić (nie chce popełnić faux pas, myląc imiona!). Ale jeśli wszystkie litery w przedziale są unikatowe, wówczas Johnny może swobodnie zadzwonić do którejś z Pań.

3. Niestety, wraz z upływem dnia Johnny jest blokowany przez kolejne dziewczyny. Kolejność banów jest dokładnie określona: i-ta dziewczyna, która go blokuje, ma numer p_i na liście Johnny’ego.

Twoim zadaniem jest pomóc Johnny’emu i odpowiedzieć na pytanie: po ilu banach Johnny będzie mógł bez wątpliwości zadzwonić do dziewczyn w Q określonych przedziałach?

Wejście

W pierwszym wierszu wejścia znajduje się N literowe słowo - pierwsze litery imion dziewczyn, których numery zapisane ma Johnny.

W drugim wierszu znajduje się liczba Q - liczba przedziałów.

W i-tym z kolejnych Q wierszy znajdują się liczby a_i, b_i, oznaczające lewy i prawy koniec i-tego przedziału (1 ≤ a_i ≤ b_i ≤ N).

W ostatnim wierszu znajduje się permutacja N elementów - ciąg p_i (1 ≤ i ≤ N), określający kolejność blokowania Johnnego przez dziewczyny (permutacja to taki ciąg liczb od 1 do N, w którym każda liczba występuje dokładnie raz).

Wyjście

W jedynym wierszu wyjścia powinna znaleźć się minimalna liczba dziewczyn, które muszą zablokowac Johnny’ego, aby ten mógł bezpiecznie umówić się na randki.

Ograniczenia

1 ≤ N ≤ 10⁵,

1 ≤ Q ≤ 10⁵.

W tym zadaniu można otrzymać część punktów za wolniejsze rozwiązania (dla mniejszych N i Q).

Przykład

abcbd
2
1 4
4 5
3 2 5 1 4

2