Description

For an integer sequence $(a_1,a_2,\cdots,a_n)$ and a permutation $(p_1,p_2,\cdots,p_n)$ of $1 \sim n$, we say that $(a_1,a_2,\cdots,a_n)$ matches $(p_1,p_2,\cdots,p_n)$ if and only if:

• Any two numbers in $\{a\}$ are different from each other.
• After sorting $(a_1,a_2,\cdots,a_n)$ in increasing order, we obtain $(a_{p_1},a_{p_2},\cdots,a_{p_n})$.

Now you are given a permutation $\{p\}$ of $1 \sim n$ and a sequence $h_1,h_2,\cdots,h_m$. Please determine which substrings of $\{h\}$ match the permutation $\{p\}$.

Input Format

The first line contains two positive integers $n,m$ separated by spaces.

The second line contains $n$ positive integers separated by spaces, representing the permutation $p$.

The third line contains $m$ positive integers separated by spaces, representing the sequence $h$.

Output Format

The first line contains an integer $k$, indicating the number of substrings that match $\{p\}$.

The second line contains $k$ positive integers separated by spaces, indicating the starting positions of these substrings (indexed from $1$). Output these positions in increasing order. In particular, if $k=0$, you should output an empty line as well.

5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

2
2 6

Hint

For $100\%$ of the testdata, $2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n$. It is guaranteed that all elements in $\{h\}$ are pairwise distinct, and $\{p\}$ is a permutation.

Constraints

Translated by ChatGPT 5