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:
Johnny wybiera spójny przedział ze swojej listy N numerów, np. przedział od 3 do 7.
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ń.
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 pi 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 ai, bi, oznaczające lewy i prawy koniec i-tego przedziału (1 ≤ ai ≤ bi ≤ N).
W ostatnim wierszu znajduje się permutacja N elementów - ciąg pi (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 ≤ 105,
1 ≤ Q ≤ 105.
W tym zadaniu można otrzymać część punktów za wolniejsze rozwiązania (dla mniejszych N i Q).
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Po drugim blokowaniu lista kontaktów Johnny’ego wygląda następująco a * * bd. Po pierwszym blokowaniu lista wyglądała tak: ab * bd, a Johnny nie mógł zdecydować się na wybór dziewczyny w przedziale od 1 do 4 (dwukrotnie widzi tam literkę b). |