#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp> // common file
#include<ext/pb_ds/tree_policy.hpp> // including tree_order_statistics_node_update
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) (x).begin(), (x).end()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define sz(x) (int)((x).size())
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define endl "\n"
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define nn "\n"
// bit manipulation
#define SetBit(x, k) (x |= (1LL << k))
#define ClearBit(x, k) (x &= ~(1LL << k))
#define CheckBit(x, k) (x & (1LL << k))
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define ordered_set tree<int, null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>
const long long INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;
int binpow(int a, int b) {
int res = 1;
while (b > 0) {
if (b & 1) {
res = a * res;
}
a = a * a;
b >>= 1;
}
return res;
}
void fast_io()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
int gcd(int a, int b) {if (b == 0) return a; return gcd(b, a % b);}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
vpii subs;
int q;
string s;
int n;
struct segtree {
int size;
vector<int> val;
set<int> *segment;
void init(int n) {
size = 1;
while (size < n) {
size *= 2;
}
val.assign(2 * size, 0);
segment = new set<int>[2 * size];
}
void build(vector<int> &a, int node, int tl, int tr) {
if ((tr - tl) == 1) {
if (tl < a.size()) {
segment[node].insert(a[tl]);
}
return;
}
int tm = tl + (tr - tl) / 2;
build(a, 2 * node + 1, tl, tm);
build(a, 2 * node + 2, tm, tr);
segment[node].insert(segment[2 * node + 1].begin(), segment[2 * node + 1].end());
segment[node].insert(segment[2 * node + 2].begin(), segment[2 * node + 2].end());
}
void build(vector<int> &a) {
build(a, 0, 0, size);
}
set<int> query(int ql, int qr, int node, int tl, int tr) {
set<int> lft, rht, res;
if (tl >= qr || tr <= ql) { // out of range
return res;
}
if (tl >= ql && tr <= qr) { // completely inside the query range
return segment[node];
}
int tm = tl + (tr - tl) / 2;
// int v1 = query(ql, qr, 2 * node + 1, tl, tm);
// int v2 = query(ql, qr, 2 * node + 2, tm, tr);
lft = query(ql, qr, 2 * node + 1, tl, tm);
rht = query(ql, qr, 2 * node + 2, tm, tr);
res.insert(lft.begin(), lft.end());
res.insert(rht.begin(), rht.end());
// return merge(v1, v2);
return res;
}
set<int> query(int ql, int qr) {
return query(ql, qr, 0, 0, size);
}
};
vi idx;
bool chk(int x) {
// debug(x);
segtree st;
vi tmp;
int cnt = 100;
for (int i = 0; i < n; i++) {
int x = s[i] - 'a';
tmp.pb(x);
}
for (int i = 0; i <= x; i++) {
tmp[idx[i]] = cnt;
cnt++;
}
// for (int ele : tmp) {
// cout << ele << endl;
// }
st.init(n);
st.build(tmp);
for (int i = 0; i < q; i++) {
int l = subs[i].ff;
int r = subs[i].ss;
set<int> res = st.query(l , r + 1);
// for (auto ele : res) {
// cout << ele << "#";
// }
// cout << endl;
// debug(l);
// debug(r);
// debug(res.size());
// debug(r - l + 1);
if (res.size() != (r - l + 1)) {
return false;
}
}
return true;
}
void KhelaFinal() {
cin >> s;
n = (int)s.size();
cin >> q;
for (int i = 0; i < q; i++) {
int x, y; cin >> x >> y;
subs.pb({x - 1, y - 1});
}
for (int i = 0; i < n; i++) {
int x; cin >> x;
idx.pb(x - 1);
}
vi tmp;
for (int i = 0; i < n; i++) {
int x = s[i] - 'a';
tmp.pb(x);
}
segtree st;
st.init(n);
st.build(tmp);
bool ok = 1;
for (int i = 0; i < q; i++) {
int l = subs[i].ff;
int r = subs[i].ss;
set<int> res = st.query(l, r + 1);
if (res.size() != (r - l + 1)) {
ok = 0;
break;
}
}
if (ok) {
cout << 0 << endl;
return;
}
int lo = 0;
int hi = n - 1;
int ans;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
// debug(mid);
if (chk(mid)) {
hi = mid - 1;
ans = mid;
}
else {
lo = mid + 1;
}
}
cout << ans + 1 << endl;
}
signed main()
{
fast_io();
//#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
//#endif
int t = 1;
// cin >> t;
while (t--) {
KhelaFinal();
}
return 0;
}
