Logo Matching

As part of a new advertising campaign, a large company wants to place its logo somewhere in the city. The company will spend its entire yearly advertising budget on the logo, so it has to be enormous — one manager decided to use whole buildings as parts of it.

The logo consists of $n$ vertical stripes of pairwise different heights, numbered $1$ to $n$ from left to right. It is described by a permutation $(s_1, s_2, \dots, s_n)$ of $1, 2, \dots, n$: stripe $s_1$ is the shortest, stripe $s_2$ is the second shortest, and so on, up to stripe $s_n$, the tallest. Only the relative order of the stripe heights matters, not their actual values.

There are $m$ buildings along the main street, and all of their heights are pairwise different. A contiguous block of $n$ consecutive buildings matches the logo when, inside that block, the building at position $s_1$ is the shortest, the building at position $s_2$ is the second shortest, and so on. For example, heights $5, 10, 4$ match the logo $(3, 1, 2)$: the building at position $3$ (height $4$) is the shortest, the one at position $1$ is the second shortest, and the one at position $2$ is the tallest. Find every place where the logo matches the buildings.

The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 10^6$).

The second line contains $n$ integers $s_1, \dots, s_n$, a permutation of $1, 2, \dots, n$ (so $1 \le s_i \le n$ and $s_i \ne s_j$ for $i \ne j$).

The third line contains $m$ integers $h_1, \dots, h_m$, the heights of the buildings ($1 \le h_i \le 10^9$); all $h_i$ are different.

Within each line the integers are separated by single spaces.

On the first line print the number of matches $k$.

On the second line print, in increasing order and separated by single spaces, the $1$-based index of the building aligned with stripe number $1$ of the logo for each match — equivalently, the starting index of each matching block.

If $k = 0$, the second line must be empty.

Both blocks $6, 3, 8, 12, 7$ and $7, 1, 10, 11, 9$ match the logo described by the permutation $(2, 1, 5, 3, 4)$. In the first block the building at position $2$ (height $3$) is the shortest, the building at position $1$ (height $6$) is the second shortest, the building at position $5$ (height $7$) is the third shortest, and so on.