P3560 [POI 2013] LAN-Colorful Chain

Little Bytie loves to play with colorful chains. He already has quite an impressive collection, and some of them he likes more than the others. Each chain consists of a certain number of colorful links. Byteasar has noticed that Bytie's sense of aesthetics is very precise. It turns out that Bytie finds a contiguous fragment of a chain nice if it contains exactly  links of color  links of color  links of color , and moreover it contains no links of other colors. A chain's appeal is its number of (contiguous) fragments that are nice. By trial and error, Byteasar has determined the values  and . Now he would like to buy a new chain, and therefore asks you to write a program to aid him in shopping. 给定一个长度为 $n$ 的序列 $a$ 和 $m$ 个条件（每个条件中包含键 $c_i$ 和值 $l_i$），要求找出满足下列条件的子串的数量并输出： + 条件中存在键 $c_i$ 的，要求子串中 $c_i$ 恰好出现 $l_i$ 次。 + 条件中不存在键 $c_i$ 的，要求子串中不出现 $c_i$。 先输入 $n$ 和 $m$，再输入 $m$ 个条件的 $l_i$，然后输入 $m$ 个条件的 $c_i$，最后输入 $a_i$。

无

无

### 数据范围： 对于 $100\%$ 的数据，$1\leq m\leq n \leq 10^6$，$1\leq a_i,b_i,c_i\leq n$。