Suffix Anagram Count

We are given a target string (S) of length (T) and (n) small strings (a_i). You are also provided with an array (R) of length (m) (1-indexed). Initially, there is an empty string (X). Then, (Q) operations are performed. In the (i)-th operation, the string (a_{R_{((i-1) \bmod m)+1}}) is appended to (X). After each operation, check if there exists a suffix of (X) of length (T) such that its character frequency matches that of (S) (i.e. it can be rearranged to form (S)). Note that since (S) is balanced (all characters occur the same number of times), the condition is equivalent to checking whether the last (T) characters of (X) form an anagram of (S).

inputFormat

The input consists of the following parts:\

1. The first line contains four integers (T), (n), (m), and (Q), where (T) is the length of (S).\
2. The second line contains the string (S).\
3. The next (n) lines each contain a small string (a_i).\
4. The last line contains (m) integers representing the array (R) (each integer is in the range ([1, n])).

outputFormat

Output a single integer: the number of operations after which there exists a suffix of (X) (of length (T)) whose characters can be rearranged to form (S).

sample

3 2 2 5
abc
a
bc
1 2

4