Cow Patterns

A group of $K$ of Farmer John's cows likes to make trouble. When placed in a line, these troublemakers always stand together in a particular relative order. To find them, FJ has lined up all $N$ of his cows, who will file into the barn keeping that order. Help FJ locate every block of $K$ consecutive cows in the line that could be the troublemakers.

FJ tells his cows apart by the number of spots $1..S$ on each cow's coat. It is not a perfect method, but it serves his purposes. FJ does not remember the exact number of spots on each troublemaker. He does remember which cows in the group have the same number of spots, and, for any two cows with different counts, which one has more. He writes such a pattern as a sequence of $K$ ranks in the range $1..S$. For example, consider the sequence:

1 4 4 3 2 1

Here FJ is looking for 6 consecutive cows. Cows #1 and #6 have the same number of spots (not necessarily 1) and the fewest among the six (they are labeled '1'). Cow #5 has the second-fewest spots, different from every other cow. Cows #2 and #3 have equal spots, the most among the six.

If the true spot counts of some consecutive cows are:

5 6 2 10 10 7 3 2 9

then only the block 2 10 10 7 3 2 matches the pattern above.

Find every length-$K$ block of consecutive cows whose spot counts match the given pattern.

Here a block matches the pattern when the two sequences have exactly the same relative order: for every pair of positions $i, j$, whether the pattern's $i$-th entry is smaller than, equal to, or greater than its $j$-th entry must hold identically for the block.

• Line 1: Three space-separated integers $N$, $K$, and $S$ ($1 \le N \le 100{,}000$, $1 \le K \le 25{,}000$, $1 \le S \le 25$).
• Lines 2..N+1: Line $i+1$ contains the number of spots on cow $i$ ($1..S$).
• Lines N+2..N+K+1: Line $i+N+1$ contains the $i$-th rank of the pattern ($1..S$).

• Line 1: $B$, the number of starting positions at which the pattern matches.
• Next $B$ lines: the starting positions ($1..N$) where the pattern matches, one per line, in increasing order.

If there is no match, print a single line containing 0.

In the worked example above, comparing the true spot counts 5 6 2 10 10 7 3 2 9 with the pattern 1 4 4 3 2 1 gives exactly one match: the block 2 10 10 7 3 2 starting at position 3.