Finding the Bad Cows

Farmer John has N cows (\(1 \leq N \leq 10^5\)) among which exactly K are misbehaving (\(1 \leq K \leq 25000\)). These bad cows always stand together in the lineup. Each cow sports a number between \(1\) and \(S\) (\(1 \leq S \leq 25\)). Although the number on the cow's tag is not a perfect identifier, it helps somewhat. Farmer John does not remember the exact numbers of the bad cows but recalls a pattern of numbers. In this pattern, cows with equal numbers must correspond to cows with equal numbers in the actual segment, and the ordering (i.e. the less‐or‐greater relationship) between different numbers in the pattern must be preserved in the actual numbers.

For example, consider the pattern:

[ 1,;4,;4,;3,;2,;1 ]

This indicates that the first and last bad cow have the same (and smallest) number; the second and third cows share the same (and largest) number; and the remaining cows have numbers in between such that the order is preserved.

Given a lineup of cows, for example:

[ 5,;6,;2,;10,;10,;7,;3,;2,;9 ]

the contiguous substring 2, 10, 10, 7, 3, 2 (starting at position 3) matches the pattern’s equality and order relations, so it could be the group of bad cows.

Your task is to find all possible contiguous segments in the lineup that could correspond to the group of bad cows.

inputFormat

The first line contains three integers: N, K, and S.

The second line contains K integers describing the pattern.

The third line contains N integers representing the numbers on the cows in the lineup.

outputFormat

On the first line, output the number of segments that match the pattern.

On the second line, output the 1-indexed starting positions of each matching segment, separated by a space. If there is no matching segment, the second line can be empty.

sample

9 6 10
1 4 4 3 2 1
5 6 2 10 10 7 3 2 9

1
3

</p>