Contiguous Flower Arrangement Count

In this problem, you are given a line of N flowers, each represented by an integer indicating its type. There are M possible flower types. You are also given a set of arrangement requirements: for a given flower type, a specific count is needed in the subarray. Your task is to compute the number of contiguous subarrays (windows) of fixed length (i.e. the sum of the required counts) that exactly match the required counts for each flower type.

Formally, let (N) be the total number of flowers and let ({f_1, f_2, \dots, f_N}) be the sequence of flower types. If the arrangement requirements are given as a set of pairs ((t_i, c_i)) (flower type and required count), define (L = \sum_i c_i) as the window size. A contiguous subarray ({f_j, f_{j+1}, \dots, f_{j+L-1}}) is valid if for every required type (t_i), the frequency of (t_i) in the subarray satisfies (\text{freq}(t_i) = c_i). Your task is to count the number of such valid subarrays.

It is guaranteed that the input subarray is given in a single test case and the required subarray length is not larger than (N).

inputFormat

The input is read from standard input (stdin) and consists of the following:

1. The first line contains two integers (N) and (M), where (N) is the total number of flowers and (M) is the number of flower types.
   
2. The second line contains (N) integers representing the types of the flowers in order.
   
3. The third line contains an integer (K), the number of arrangement requirements.
   
4. The next (K) lines each contain two integers: a flower type and the exact number required for that type.

outputFormat

Output to standard output (stdout) a single integer: the number of contiguous subarrays that satisfy all the arrangement requirements.## sample

7 3
1 2 1 3 2 3 1
3
1 2
2 1
3 2

1