Moo Sick

Interview

Time limit1sMemory limit128 MB

Summary

Find every window of C consecutive notes whose sorted, min-subtracted shape matches the given chord's shape.

Level: Medium4 of 10
Topics: Array, Sorting, Sliding window, Implementation
Solved: No attempts yet

Problem

Cows love almost every kind of music. Almost -- the great cow composer Wolfgang Amadeus Moozart once discovered that one particular chord tends to make cows ill. That chord, the ruminant seventh chord, is therefore avoided in cow compositions.

Farmer John, unaware of this, plays his favorite song over the barn loudspeakers. Your task is to find every ruminant seventh chord in the song so we can estimate how sick it will make the cows.

The song is a sequence of $N$ notes ( $1 \le N \le 20000$ ), each an integer in $[1, 88]$ . A ruminant seventh chord is defined by a set of $C$ distinct notes ( $1 \le C \le 10$ ), also integers in $[1, 88]$ . The chord is invariant under transposition (adding the same amount to every note) and reordering. For example, if 4 6 7 is a ruminant seventh chord, then 3 5 6 (transposed by $-1$ ), 6 8 9 (transposed by $+2$ ), 6 4 7 (reordered), and 5 3 6 (transposed and reordered) are all ruminant seventh chords too.

An occurrence of the chord in the song is any block of $C$ consecutive notes that, after some transposition and reordering, equals the chord. Such an occurrence is uniquely identified by its starting position. Report the starting positions of every ruminant seventh chord occurrence in the song.

Input

Line 1: the integer $N$ .
Lines 2 to $N+1$ : the $N$ notes of the song, one per line.
Line $N+2$ : the integer $C$ .
Lines $N+3$ to $N+2+C$ : the $C$ notes of one example ruminant seventh chord, one per line. Every transposition and/or reordering of these notes is also a ruminant seventh chord.

Output

Line 1: the count $K$ of ruminant seventh chord occurrences in the song. Note that different occurrences may overlap.
Lines 2 to $K+1$ : the starting index of each occurrence (index $1$ is the first note, index $N$ the last), listed in increasing order.

Hint

To test a block of $C$ consecutive notes, sort it and subtract the smallest note from every note; this yields a "shape" that is invariant to transposition and reordering. Compute the chord's shape the same way. The block is a ruminant seventh chord exactly when its shape equals the chord's shape. Because occurrences are counted at every starting position, two of them may overlap.

Examples3

Example 1
Input
```
6
1
8
5
7
9
10
3
4
6
7
```
Expected output
```
2
2
4
```
Example 2
Input
```
3
5
5
5
1
40
```
Expected output
```
3
1
2
3
```
Example 3
Input
```
5
1
2
3
4
5
2
10
11
```
Expected output
```
4
1
2
3
4
```