Problem A

Music Grep

In this problem:

• a music is just a sequence of pairs (note and duration).
• a note is described by the distance to a reference note (the number of semitones).
• the duration of the note is described by the number of time units.

The musical format

The following tune

could be coded as:

0 2
2 2
4 2
5 2
7 4
9 2
7 2
5 4
4 2
2 2
0 8

Where the note reference = C/dó, and time reference = semi-quaver (semicolcheia = 1/4 tempo)

Problem

We want to write a tool to help in the process of finding a musical pattern in a tune.

The tune and the musical pattern are described in format given above.

The matching process should be able to find a musical pattern whose notes are shifted in frequence or duration (the same music can be performed faster or slower, starting in different frequences).

See the examples below.

Input

A tune (in musical format), an empty line, and a pattern (in musical format).

The maximum number of notes in a tune is 1000. The maximum number of notes in a pattern is 20.

Example:

0 2  (... The music: the previous music)
2 2
4 2
5 2
7 4
9 2
7 2
5 4
4 2
2 2
0 8

2 4  (... The pattern: notes 4..7, shift down 5 semitones)
4 2
2 2
0 4

Output

The position of the note where the pattern was found for the first time, or -1 if the pattern was not found. Note position numbers start at zero.

Example: the answer to the prev. input is:

4

More Examples

In the input given abouve, if the pattern has its durations reduced by 1

0 2  (... the previous music)
...
0 8

2 3  (The pattern: notes match but durations don't)
4 1
2 1
0 3

The answer should be -1 (the time relations are different)

If the pattern has is durations reduced

0 2  (... the previous music)
...
0 8

2 2  (The pattern: notes and durations are shift but match)
4 1
2 1
0 2

The answer should again be 4