{"raw_statement":[{"iden":"story","content":"You heard a song consisting of $N$ notes in fits and starts. You want to guess whether a phrase consisting of $M$ sounds was included in this song. You also want to consider cases where the phrase is included in a different [key](https://en.wikipedia.org/wiki/Key_(music)) than the original."},{"iden":"problem statement","content":"You are given two sequences of non-negative integers, $A = (A_1, \\dots, A_N)$ and $B = (B_1, \\dots, B_M)$, each of length $N$ and $M$, respectively.\nFind the number of integers $i$ that satisfy $1 \\le i \\le N - M + 1$ and meet the following condition:\n\n##### Condition\n\n> Define a contiguous subsequence $C$ of length $M$ of $A$ as $C = (A_i, \\dots, A_{i + M - 1})$. Next, update all elements of the sequences $B$ and $C$ that are $0$ with any **positive real number** (the updated values may be different for each element). Then, determine an arbitrary **positive real number** $t$, and multiply all elements of sequence $C$ by $t$. By doing so, the sequences $B$ and $C$ can be made identical."},{"iden":"constraints","content":"*   $1 \\leq M \\leq N \\leq 5 \\times 10^5$\n*   $0 \\leq A_i \\leq 5 \\times 10^5$ $(i = 1, \\ldots, N)$\n*   $0 \\leq B_i \\leq 5 \\times 10^5$ $(i = 1, \\ldots, M)$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N \\ M$\n$A_1 \\ A_2 \\ \\dots \\ A_N$\n$B_1 \\ B_2 \\ \\dots \\ B_M$"},{"iden":"sample input 1","content":"9 4\n9 3 0 0 2 99 4 0 0\n6 2 0 4"},{"iden":"sample output 1","content":"4\n\nFor $i = 1$, update $B$ to $(6, 2, 5, 4)$ and $C = (9, 3, 0, 0)$ to $(9, 3, 7.5, 6)$, and take $t = 2/3$. Finally, $B$ and $C$ will match.\nFor $i = 2, 3, 4$, it is possible to make $B$ and $C$ match by performing appropriate operations, but for $i = 5, 6$, it is impossible.\nTherefore, since $i = 1, 2, 3, 4$ meet the condition, output $4$ as the answer."},{"iden":"sample input 2","content":"8 2\n0 0 0 0 0 0 0 0\n0 0"},{"iden":"sample output 2","content":"7"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}