Grudanje

Patrik은 영어 단어를 연구하는 것을 좋아한다. 그는 특히 정확히 N개의 글자로 이루어진 단어를 좋아한다. 그런 단어를 보면 곧바로 그 단어의 부분 단어 Q개를 관찰하며, 각 부분 단어의 모든 글자가 서로 다른지 판단한다. Q개의 부분 단어 모두에서 그렇다면, 그는 원래 단어를 완벽하다고 여긴다.

Krešimir는 영어 단어를 연구하는 것을 좋아하지 않고, 대신 Patrik에게 눈덩이를 던지는 것을 좋아한다. 추운 겨울 아침, 그는 정확히 N개의 눈덩이를 들고 마을을 걷다가, 어딘가 불량배들이 벽에 써 놓은 거대한 N글자 단어를 관찰하고 있는 Patrik을 만난다. 참 우연이라도 있는 듯이.

Krešimir는 Patrik을 향해 첫 번째 눈덩이를 세차게 던졌지만, Patrik은 능숙하게 피했고 눈덩이는 벽에 있는 단어의 p1번째 글자를 맞혀 완전히 덮었다. 비슷하게, Krešimir는 다음 (N - 1)개의 눈덩이로도 Patrik을 맞히지 못했다. 더 정확히는, i번째 눈덩이는 Patrik을 빗나가 벽에 있는 단어의 pi번째 글자를 완전히 덮었다. 흥미롭게도, Krešimir가 모든 눈덩이를 던지고 나자 단어 전체가 눈으로 덮였다.

Patrik은 완전히 덮인 단어를 보고 그것이 완벽하다고 결론지었다. 그래서 그는 완벽한 단어의 정의를 약간 바꿔야 했다. 단어는 Q개의 부분 단어 중 어느 것에도 눈에 덮이지 않은 같은 글자 두 개가 없으면 완벽하다. 이제 그는 벽에 있는 단어가 몇 번째 눈덩이 이후에 완벽해졌는지(0번째일 수도 있다) 알고 싶어 한다.

첫째 줄에는 영어 알파벳 소문자로 이루어진 N (1 ≤ N ≤ 105)글자 단어가 주어진다.

둘째 줄에는 문제 설명의 정수 Q (1 ≤ Q ≤ 105)가 주어진다.

다음 Q개 줄 중 i번째 줄에는 두 정수 ai와 bi (1 ≤ ai ≤ bi ≤ N)가 주어지며, 이는 문제 설명의 Q개 부분 단어 중 i번째가 벽에 있는 단어의 ai번째 글자부터 bi번째 글자까지를 포함한다는 뜻이다.

다음 줄에는 문제 설명의 서로 다른 N개 정수 pi (1 ≤ pi ≤ N)가 주어진다.

한 줄에 벽에 있는 단어가 몇 번째 눈덩이 이후에 완벽해졌는지(0번째일 수도 있다)를 출력한다.

두 번째 예제에 대한 설명:

각 눈덩이를 던진 후 벽에 있는 단어의 상태는 다음과 같다:

abbab*ab
ab*ab*ab
ab*a**ab
*b*a**ab
*b****ab
******ab
*******b
********