#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
struct Intervalle {
int deb, fin;
};
bool comp(const Intervalle& a, const Intervalle& b)
{
if (a.deb == b.deb)
return a.fin < b.fin;
return a.deb < b.deb;
}
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string mot;
cin >> mot;
int N = mot.length();
int nbRequetes;
cin >> nbRequetes;
vector<Intervalle> requetes(nbRequetes);
for (int _ = 0; _ < nbRequetes; _++)
{
cin >> requetes[_].deb >> requetes[_].fin;
requetes[_].deb--; requetes[_].fin--;
}
sort(requetes.begin(), requetes.end(), comp);
if (N < 10000 && nbRequetes < 10000)
{
/* cout << "MES INTER :\n";
for (auto inter : requetes)
cout << inter.deb << " " << inter.fin << "\n"; */
vector<map<char, int>> occ((int)requetes.size());
vector<int> nbMotsAChanger((int)requetes.size());
for (int j = 0; j < (int)requetes.size(); j++)
{
auto inter = requetes[j];
for (int i = inter.deb; i <= inter.fin; i++)
occ[j][mot[i]]++;
for (auto el : occ[j])
if (el.second > 1)
nbMotsAChanger[j]++;
}
/* cout << "MON MOT : " << mot << "\n";
for (int j = 0; j < (int)requetes.size(); j++)
{
auto inter = requetes[j];
cout << "JE REGARDE L'INTERVALLE : " << inter.deb << " et " << inter.fin << "\n";
cout << "VOICI LES OCCURENCES DES MOTS DEDANS :\n";
for (auto el : occ[j])
cout << el.first << " : " << el.second << "\n";
cout << "NB MOTS A CHANGER : " << nbMotsAChanger[j] << "\n";
} */
bool valide = true;
for (int z = 0; z < (int)requetes.size(); z++)
if (nbMotsAChanger[z] > 0)
valide = false;
if (valide)
{
cout << "0\n";
return 0;
}
for (int i = 0; i < N; i++)
{
int iChange;
cin >> iChange;
iChange--;
bool valide2 = true;
for (int z = 0; z < (int)requetes.size(); z++)
{
// cout << "je suis dans l'intervalle " << requetes[z].deb << " - " << requetes[z].fin << " avec iChange " << iChange << "\n";
auto inter = requetes[z];
if (iChange >= inter.deb && iChange <= inter.fin)
{
if (occ[z][mot[iChange]] == 2)
nbMotsAChanger[z]--;
occ[z][mot[iChange]]--;
// cout << "J'ai retiré une occurence de " << mot[iChange] << "\n";
}
if (nbMotsAChanger[z] > 0)
valide2 = false;
}
if (valide2)
{
cout << i + 1 << "\n";
return 0;
}
}
}
else
{
/* cout << "MES INTER :\n";
for (auto inter : requetes)
cout << inter.deb << " " << inter.fin << "\n"; */
vector<Intervalle> disjoints;
disjoints.push_back(requetes[0]);
for (int i = 1; i < (int)requetes.size(); i++)
{
if (requetes[i].deb > disjoints[(int)disjoints.size() - 1].fin)
disjoints.push_back(requetes[i]);
else
disjoints[(int)disjoints.size() - 1].fin = max(disjoints[(int)disjoints.size() - 1].fin, requetes[i].fin);
}
/* cout << "MES INTER :\n";
for (auto inter : disjoints)
cout << inter.deb << " " << inter.fin << "\n"; */
vector<map<char, int>> occ((int)disjoints.size());
vector<int> nbMotsAChanger((int)disjoints.size());
for (int j = 0; j < (int)disjoints.size(); j++)
{
auto inter = disjoints[j];
for (int i = inter.deb; i <= inter.fin; i++)
occ[j][mot[i]]++;
for (auto el : occ[j])
if (el.second > 1)
nbMotsAChanger[j]++;
}
/* cout << "MON MOT : " << mot << "\n";
for (int j = 0; j < (int)disjoints.size(); j++)
{
auto inter = disjoints[j];
cout << "JE REGARDE L'INTERVALLE : " << inter.deb << " et " << inter.fin << "\n";
cout << "VOICI LES OCCURENCES DES MOTS DEDANS :\n";
for (auto el : occ[j])
cout << el.first << " : " << el.second << "\n";
cout << "NB MOTS A CHANGER : " << nbMotsAChanger[j] << "\n";
} */
bool valide = true;
for (int z = 0; z < (int)disjoints.size(); z++)
if (nbMotsAChanger[z] != 0)
valide = false;
if (valide)
{
cout << "0\n";
return 0;
}
for (int i = 0; i < N; i++)
{
int iChange;
cin >> iChange;
iChange--;
bool valide2 = true;
for (int z = 0; z < (int)disjoints.size(); z++)
{
// cout << "je suis dans l'intervalle " << disjoints[z].deb << " - " << disjoints[z].fin << " avec iChange " << iChange << "\n";
auto inter = disjoints[z];
if (iChange >= inter.deb && iChange <= inter.fin)
{
if (occ[z][mot[iChange]] == 2)
nbMotsAChanger[z]--;
occ[z][mot[iChange]]--;
// cout << "J'ai retiré une occurence de " << mot[iChange] << "\n";
}
if (nbMotsAChanger[z] > 0)
valide2 = false;
}
if (valide2)
{
cout << i + 1 << "\n";
return 0;
}
}
}
return 0;
}
