Задача №114916. Заснеженная стена
Пафнутий любит изучать слова на английском языке. Особенно он любит слова, которые содержат ровно \( N \) букв. Когда он видит такое слово, он немедленно начинает наблюдать за \( Q \) его подсловами и для каждого из этих подслов он определяет, все ли его буквы различны. Если это условие выполнено для каждого из \( Q \) подслов, то Пафнутий считает исходное слово (содержащее \( N \) букв) совершенным.
Иннокентий не любит изучать английские слова, вместо этого он любит кидаться снежками в Пафнутия. Холодным зимним утром он прогуливался по городу, нес ровно \( N \) снежков и наткнулся на Пафнутия, который наблюдал за гигантским словом из \( N \) букв, написанным на стене какими-то хулиганами. Какое совпадение...
Иннокентий яростно бросил первый снежок в сторону Пафнутия, но Пафнутий умело увернулся от снежка, так что он попал и полностью покрыл \( p_1 \)-ую букву слова на стене. Аналогичным образом Иннокентий не смог поразить Пафнутия следующими (\( N - 1 \)) снежками. Точнее, его \( i \)-ый снежок пролетел мимо Пафнутия и полностью покрыл \( p_i \)-ую букву слова на стене. Интересно, что после того, как Иннокентий бросил все снежки, всё слово было покрыто снегом.
Пафнутий взглянул на полностью покрытое снегом слово и пришел к выводу, что оно совершенно. Поэтому ему нужно было немного изменить свое определение совершенного слова. Слово совершенно если ни в одном из \( Q \) его подслов нет двух одинаковых букв, которые не покрыты снегом. Теперь Пафнутий хочет узнать, после скольких брошенных снежков (возможно, нуля, т.е. до броска первого снежка) слово на стене стало совершенным.
Первая строка содержит слово, состоящее из \( N \) (\( 1 \le N \le 10^5 \)) строчных букв английского алфавита.
Вторая строка содержит целое число \( Q \) (\( 1 \le Q \le 10^5 \)) из описания задачи.
\( i \)-ая из следующих \( Q \) строк содержит два целых числа \( a_i \) и \( b_i \) (\( 1 \le a_i \le b_i \le N \)), которые обозначают, что \( i \)-ое из \( Q \) подслов из описания задачи состоит из букв \( a_i, a_{i + 1}, ... b_{i - 1}, b_i \), записанных на стене.
Следующая строка содержит \( N \) различных целых чисел \( p_i \) (\( 1 \le p_i \le N \)) из описания задачи.
В единственной строке, которую вы должны вывести, должно находиться единственное число \( - \) количество брошенных снежков (возможно, нулевое), после которых слово на стене стало совершенным.
| Группа | Доп. ограничения | Баллы |
| \( 1 \) | \( 1 \le N, Q \le 500 \) | \( 20 \) |
| \( 2 \) | \( 1 \le N, Q \le 3000 \) | \( 30 \) |
| \( 3 \) | Слово на стене содержит только буквы 'a' | \( 20 \) |
| \( 4 \) | \( - \) | \( 30 \) |
Разъяснение второго примера:
Состояние слова на стене после каждого брошенного снежка:
abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********
aaaaa 2 1 2 4 5 2 4 1 5 3
2
abbabaab 3 1 3 4 7 3 5 6 3 5 1 4 2 7 8
5
abcd 1 1 4 1 2 3 4
0