소 무늬 패턴 찾기

농부 John의 소 $N$마리 중에서 말썽을 부리는 $K$마리가 있다. 이들은 한 줄로 설 때 언제나 특정한 상대적 순서로 나란히 선다. 이 말썽꾸러기들을 찾기 위해 John은 소 $N$마리를 한 줄로 세웠고, 소들은 그 순서를 유지한 채 축사로 들어간다. 이 줄 안에서 말썽꾸러기일 수도 있는, 연속한 $K$마리로 이루어진 모든 구간을 찾아야 한다.

John은 각 소의 털에 있는 반점 수 $1..S$로 소를 구별한다. 완벽한 방법은 아니지만 목적에는 충분하다. John은 말썽꾸러기 각각의 정확한 반점 수는 기억하지 못하지만, 무리 안에서 어떤 소들의 반점 수가 서로 같은지, 그리고 반점 수가 다른 두 소 중 어느 쪽이 더 많은지는 기억한다. 그는 이러한 패턴을 $1..S$ 범위의 순위 $K$개로 이루어진 수열로 표현한다. 예를 들어 다음 수열을 보자.

1 4 4 3 2 1

이 예에서 John은 한 줄로 선 소 $N$마리 중 연속한 6마리를 찾고 있다. 이 수열에서 1번과 6번 소는 반점 수가 서로 같으며(그 값이 반드시 1이라는 뜻은 아니다), 6마리 중 반점 수가 가장 적다('1'로 표시되었기 때문이다). 5번 소는 두 번째로 반점 수가 적으며, 나머지 소들과 모두 다르다. 2번과 3번 소는 반점 수가 서로 같고, 그 값은 6마리 중 가장 크다.

어떤 연속한 소들의 실제 반점 수가 다음과 같다면,

5 6 2 10 10 7 3 2 9

패턴과 일치하는 것은 구간 2 10 10 7 3 2 하나뿐이다.

한 줄로 선 소들 중에서 주어진 패턴과 일치하는, 길이 $K$인 연속 구간을 모두 찾아라.

여기서 '일치'란 두 수열의 상대적 대소 관계가 완전히 같다는 뜻이다. 즉 모든 위치 쌍 $i, j$에 대해, 패턴의 $i$번째 값이 $j$번째 값보다 작은지·같은지·큰지가 구간에서도 똑같이 성립해야 한다.

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $K$, $S$ ($1 \le N \le 100{,}000$, $1 \le K \le 25{,}000$, $1 \le S \le 25$).
• 다음 $N$개 줄: $i$번째 줄에는 $i$번 소의 반점 수가 주어진다 ($1..S$).
• 다음 $K$개 줄: $i$번째 줄에는 패턴의 $i$번째 순위가 주어진다 ($1..S$).

• 첫째 줄: 패턴과 일치하는 시작 위치의 개수 $B$.
• 다음 $B$개 줄: 패턴이 일치하는 구간의 시작 위치($1..N$)를 증가하는 순서로 한 줄에 하나씩 출력한다.

일치하는 구간이 없으면 첫째 줄에 0만 출력한다.

위 설명의 예에서 실제 반점 수 5 6 2 10 10 7 3 2 9와 패턴 1 4 4 3 2 1을 비교하면, 일치하는 구간은 3번 위치에서 시작하는 2 10 10 7 3 2 하나뿐이다.