QOJ.ac

QOJ

Süre Sınırı: 2 s Bellek Sınırı: 256 MB Toplam puan: 100

#21240. Moo Sick

İstatistikler

Everyone knows that cows love to listen to all forms of music. Almost all forms, that is -- the great cow composer Wolfgang Amadeus Moozart once discovered that a specific chord tends to make cows rather ill. This chord, known as the ruminant seventh chord, is therefore typically avoided in all cow musical compositions.

Farmer John, not knowing the finer points of cow musical history, decides to play his favorite song over the loudspeakers in the barn. Your task is to identify all the ruminant seventh chords in this song, to estimate how sick it will make the cows.

The song played by FJ is a series of $N$ $1 \le N \le 20,000$ notes, each an integer in the range 1..88. A ruminant seventh chord is specified by a sequence of $C$ $1 \le C \le 10$ distinct notes, also integers in the range 1..88. However, even if these notes are transposed (increased or decreased by a common amount), or re-ordered, the chord remains a ruminant seventh chord! 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" (re-ordered), and "5 3 6" (transposed and re-ordered) are also ruminant seventh chords.

A ruminant seventh chord is a sequence of $C$ consecutive notes satisfying the above criteria. It is therefore uniquely determined by its starting location in the song. Please determine the indices of the starting locations of all of the ruminant seventh chords.

Input

  • Line 1: A single integer: $N$.
  • Lines $2..1+N$: The $N$ notes in FJ's song, one note per line.
  • Line $2+N$: A single integer: $C$.
  • Lines $3+N..2+N+C$: The $C$ notes in an example of a ruminant seventh chord. All transpositions and/or re-orderings of these notes are also ruminant seventh chords.

Output

  • Line 1: A count, $K$, of the number of ruminant seventh chords that appear in FJ's song. Observe that different instances of ruminant seventh chords can overlap each-other.
  • Lines $2..1+K$: Each line specifies the starting index of a ruminant seventh chord (index 1 is the first note in FJ's song, index $N$ is the last). Indices should be listed in increasing sorted order.

Examples

Input 1

6
1
8
5
7
9
10
3
4
6
7

Output 1

2
2
4

FJ's song is 1,8,5,7,9,10. A ruminant seventh chord is some transposition/re-ordering of 4,6,7.

Two ruminant seventh chords appear in FJ's song (and these occurrences actually overlap by one note). The first is 8,5,7 (transposed by +1 and reordered) starting at index 2, and the second is 7,9,10 (transposed by +3) starting at index 4.

Problem credits: Rob Seay

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.