CNI "Tudor Vianu" PreOJI, clasa a X-a | Cuvintele Magice

Mini-Burac alături de Elefantul Marcici fac ravagii în oraș...

Cerință

Vi se dă un cuvânt format din $N$ litere ale alfabetului latinesc și $Q$ intervale ce reprezintă subsecvențe ale acestui cuvânt.
Cuvântul se numește magic doar dacă fiecare subsecvență dintre cele $Q$ are toate literele, care sunt vizibile, distincte.
La început, toate literele sunt vizibile.
Totuși, la fiecare moment de timp $i$ ($1 \le i \le N$), a $P_i$-a litera este acoperită, și nu mai este astfel vizibilă. Se garantează că $P$ este o permutare a numerelor de la $1$ la $N$.
Aflați după al cătelea moment de timp cuvântul va deveni magic (posibil $0$, adică string-ul era magic înainte să se înceapa acoperirea de litere).

Date de intrare

Pe prima linie a fișierului de intrare magice.in se găsește un cuvânt de $N$ litere latinești.
Pe următoarea linie se găsește numărul de intervale $Q$.
Pe următoarele $Q$ linii se găsesc perechi de forma $L_i \: R_i$ ($1 \le L \le R \le N$), semnificând subsecvențele din cerință.
Pe ultima linie se găsesc $N$ numere, reprezentând permutarea $P$.

Date de ieșire

Pe prima linie a fișierului de ieșire magice.out se va găsi un singur număr între $0$ și $N$, reprezentând momentul de timp la care cuvântul dat devine magic.

Restricții și precizări

• $N, Q \le 10^5$
• Pentru $14$ puncte, $N, Q \le 500$
• Pentru încă $21$ puncte, $N, Q \le 3000$
• Pentru încă $14$ puncte, cuvântul dat va fi compus doar din litera a

Exemplul 1

magice.in

aaaaa
2
1 2
4 5
2 4 1 5 3

magice.out

2

Exemplul 2

magice.in

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

magice.out

5

Explicație

Evoluția cuvântului (începând cu momentul de timp 0)
abbab#ab
ab#ab#ab
ab#a##ab
#b#a##ab
#b####ab
######ab
#######b
########

Exemplul 3

magice.in

abcd
1
1 4
1 2 3 4

magice.out

0