In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 26th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #03 exercise sheet]


[AED010] Word Game

Little Susan has a new hobby: she likes to remove letters from a word to get another word. It's complicated for her, though, and her brother James always wants to help her.

James gives Susan a word A so that she can reach the word B from it. Susan removes the letters from A in a certain order which is indicated by a permutation P of the indices of the word A. For example, if the word A="SUSAN" and the permutation P={4,1,3,2,5}, then Susan's letter removals make the following sequence of words:

SUSAN → SUSAN → SUSAN → SUSAN → SUSAN → SUSAN

James knows the permutation Susan is going to use. His goal is to stop his sister at some stage and continue to remove the letters himself until he reaches the B word. However, as Susan likes this hobby so much, he wants to stop his sister as late as possible. Your task is to determine how many letters can Susan remove until she James nees to stop her.

The Problem

Given two strings A and B and a permutation P indicating the order in which Susan is going to remove the letters from A, your task is to compute how many letters can Susan remove such that from the remaining ones James can still obtain word B by removing zero or more letters.

Input

The first line of the input contains the word A. The second line contains the word B. The third line contains a permutation of the valid indexes of A (i.e., a sequence of |A| distinct integers, in the range 1 to |A|). The words will always be sequences of lower case letters and it is guaranteed that it always be possible to obtain B from A.

Output

The output should consist of a single line containing the maximum number of letters that Susan can remove in the order given by the permutation so that from the remaining string James can still obtain the word B by eventually removing more letters, as previously explained before.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ |B||A| ≤ 105       Size of the words
1 ≤ Pi|A|       Integers in the permutation

Example Input 1 Example Output 1
ababcba
abb
5 3 4 1 7 6 2
3

We have the sequence ababcba → ababcba → ababcba → ababcba
Susan cannot continue from here since we could not obtain abb from ababcba

Example Input 2 Example Output 2
bbbabb
bb
1 6 3 4 2 5
4

We have the sequence bbbabb → bbbabb → bbbabbbbbabbbbbabb
Susan cannot continue from here since we could not obtain bb from bbbabb


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto