#390. String小游戏

String小游戏

给定一个字符串tt和一个长度不超过tt的字符串pp,以及一个操作序列aa。对于操作序列aa,每个操作aia_i代表删除tt中第aia_i个字符。

若按从左往右顺序执行操作序列中的操作,请问最多能执行几次操作使得p还是t的子序列(子序列是指从最初序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列)

Input

第一行为一个字符串,代表tt

第二行为一个字符串,代表pp

第三行为一个正整数nn,代表操作序列aa的长度

第四行为nn个正整数,代表aa中的每一次操作

$1\leq \left |p\right| <  \left |t \right|=n  \leq  200 000 $

Output

一个整数xx,代表最多能执行xx次操作使得pp还是tt的子序列(如果pp本来就不是tt的子串则输出0 0 )

Samples

ababcba
abb
7
5 3 4 1 7 6 2
3
aaa
b
3
1 2 3
0