Problem Description

A war has recently broken out between countries A and B. dick, as the commander-in-chief of country A, has been having a headache about intelligence. This is because country B has recently hired a cryptography expert named Easy to encrypt all of their communications.

Easy likes singing very much, so he decided to store all signals as melodies. For example, $11556654433221$ could be a sequence of encrypted notes. We represent it with a sequence of the same length, which becomes $1,1,5,5,6,6,\dots$. To increase confidentiality, he further adjusted the encrypted score by changing some pitches, turning the original sequence $A$ into $B$, where $|A|=|B|$, and for $a_i=a_j$ we have $b_i=b_j$, for $a_i<a_j$ we have $b_i<b_j$, and for $a_i>a_j$ we have $b_i>b_j$. For example, 11221 and 55775 may represent the same melody.

Recently, dick intercepted a signal that may contain important information. Based on past experience, dick already knows what some melodies mean. So dick wants to know: for a known melody, can we determine whether it appears in the intercepted melody? If it does, can we find how many times it appears and at which positions?

"Task": Determine the number of occurrences and the positions where the given melody appears in the intercepted melody.

Input Format

The first line contains three positive integers $n,m,s$. $n$ is the length of the intercepted melody, $m$ is the length of the known melody. All melodies are positive integers in $1\sim s(s\leq 25)$.

The next $n$ lines each contain one integer describing the intercepted melody $A$.

The next $m$ lines each contain one integer describing the known melody $B$.

Output Format

The first line contains an integer $t$, the number of occurrences.

Then output $t$ lines. In increasing order, give the starting position $p$ of each occurrence, i.e. $A[p\dots p+m-1]$ is equivalent to $B$.

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

1
3

Hint

For all testdata, it is guaranteed that $1\leq n \leq 10^5$, $1\leq m \leq 25000$。

Translated by ChatGPT 5