Sequence

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 262144/131072KB (Java/Others)

Problem Description

Losanto has a sequence {a[1],a[2],…,a[n]} with n positive integers. Superman has some positive integer sequences with different size. Losanto wants to know the total occurrences of every sequence Superman has in Losanto's sequence (the occurrences are allowed to overlap).
We say one sequence B occurs in another sequence A if there is a contiguous subsequence of A that is the same as B after add an integer.
For example A={1,2,3,5},B={2,3} then B occurs two times in A. The occurrences are {1,2}and{2,3} . And the addition is -1 and 0.

Input

There are multiple test cases. (No more than 20 cases)
For each test case:The first line contains two integer n and m (1≤n,m≤10000), indicating the size of Losanto's sequence and the number of sequences Superman has. In the next line, there are integers, a[1],a[2],…,a[n], indicating Losanto's sequence. In the following m lines, each starts with an integer k[i](1≤k[i]≤10000) - the size of the sequence. Then k[i] space-separated positive integers follow, indicating the sequence.
The total sum of k[i] is less than or equal to 100000. Other integers are between 1 and 10000, inclusive.

Output

For each case, One line with a number indicate that the sum of occurs times.

Sample Input

4 2
1 2 3 5
2 2 3
2 2 4

Sample Output

3

Source

第九届北京化工大学程序设计竞赛

Manager

Information
Solved Number35
Submit Number95
Problem Tags
data structures
strings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel