404999: GYM101733 E Good Snippets

One of the most important component of a good search engine is the informative snippets of the documents.

Snippet management is a feature of some text editors, program source code editors, IDEs, and related software. It allows the user to avoid repetitive typing in the course of routine edit operations.

Vladimir is working on a snippets project. Vladimir's algorithm selects the most appropriate snippet for the document, but it only considers such parts of the document that contain words that occur in the query.

You are given a sequence of words w₁, w₂, ..., w_n and the set of words s₁, s₂, ..., s_k (different words from the query). Find the number of pairs of indices (l, r) (1 ≤ l ≤ r ≤ n) such that among the words w_l, w_l + 1, ..., w_r there are all query words s_i. We say that word s_i occurs on the segment from l to r if and only if there exits j, such that w_j = s_i and l ≤ j ≤ r. That is, we count only exact matches and do not consider substrings.

The first input line contains two integers n and k (1 ≤ n, k ≤ 100 000), the number of words in the document and the number of words in the query, respectively. The second line contains n words w_i (1 ≤ |w_i| ≤ 10). The third line contains k different words s_i (1 ≤ |s_i| ≤ 10).

The words in the lines are separated by single spaces. The words consist of lowercase English letters.

In a single line print the number of pairs of indices satisfying the problem.

6 2
yandex search engine algorithm is powerful
yandex algorithm

3

9 1
the best solution is trying to find better solution
solution

27

7 2
a b a c a b a
b a

18