Problem B
Lög um lög

Photo from flickr.com

It occurs frequently in pop music, but also in other music genres, that the popular songs follow the same chord progression. This gives listeners a feeling of familiarity, and therefore increases the chances that they will enjoy the song. However, this can cause issues regarding copyright. Because the chord progression is often the same, there is a limited amount of melodies, or the notes which are sung, to be considered. Therefore, legal cases have popped up, in which a composer is accused of plagiarism. The reason is that part of one song’s melody sounds exactly the same as part of another song’s melody.

For example, Katy Perry was sued by Marcus Gray over the song Dark Horse. Originally, the court ruled in favour of Marcus Gray, but the verdict was overturned on the basis that the part of the melody in question was not particulary unique or rare. It can be dangerous to set a precedent where everyone can sue everyone over a few notes. That is why, usually, the part has to be a good portion of the song, not just a few seconds. On occasion, it may occur, that two songs are exactly the same over a long time period and then the belief is that an act of plagiarism has been committed. There is however the chance that it is a coincidence. The reason for that is there are mathematics behind what tones sound nice in sequence, which composers either know or have an intuition for.

Now a record label is worried that their intellectual property is being violated. It takes too long to listen to all the songs that might be the same, so the record label contacts you. The request is for a program which can analyze two songs simultaneously, one from the record label and the other from the alleged plagiarizer. The program should determine whether the songs sound similar enough to warrant legal action. The record label is extremely worried about filing a lawsuit that would be judged in the favour of the defendant, and therefore only wants to sue if the songs are the same in their entirety, according to music theory.

Each note, or tone, has its own frequency. It is sufficient to set a frequency for one note and then the frequencies of the other notes may be calculated according to a rule. An octave is defined as the interval between two notes where one note’s frequency is double the other’s frequency. In traditional European music, the octave is usually split into $12$ frequencies which are in sequence, and are called the chromatic scale, with an equal interval from one note to the next which is named semitone or half step. A whole step is then two half steps. On a piano you can see these twelve tones, repeated, once in each octave, but usually with incomplete octaveson the far left and the far right.

Figure 1: Notes marked on the keys of a piano.

Pianos are designed around the seven tone major scale, specifically C major. The base note is then C and the scale follows the formula: whole step, whole step, half step, whole step, whole step, whole step, half step. The notes are named after the letters A-G, as can be seen in the image, and the C major scale consists of the notes C D E F G A B, which correspond to the white keys on the piano. The notes which are not in the C major scale are exactly the notes corresponding to the black keys on the piano. They are named based on the other notes with additional half steps up or down. A half step up is written by adding # after the note, but a half step down is written by adding a b after the note. Therefore the notes in an octave are C C#/Db D D#/Eb E F F#/Gb G G#/Ab A A#/Bb B, but also note that one can write Cb for B, B# for C, Fb for E and E# for F. To signify on which octave each note is being played, an integer is added to the back of the note. The octaves are in increasing order from left to right and the first C note marks the start of octave $1$. If the fourth octave were written up in its entirety it could be written as C4 C#4 D4 D#4 E4 F4 F#4 G4 G#4 A4 A#4 B4. The note on the far left on an $88$ key piano is A0, the note known as middle C is C4, marked by a triangle in the image, and the note on the far right is C8.

Melodies are a big part of songs and they can be defined as a series of notes and rests. Rests are symbolized by - and represent the absence of sound. Each note or rest lasts for the same amount of time. To determine whether two songs are the same you can use the following rules:

• Rule 1: If two melodies are written exactly the same, then they represent the same song. For example, the melodies C4 D4 - E4 and C4 D4 - E4 are the same.

• Rule 2: If two melodies are written differently, but the notes are equivalent, then they represent the same song. For example, the melodies C4 C#4 - Eb4 and B#3 Db4 - D#4 are the same.

• Rule 3: If two melodies are written the same, except all the notes in one of them have been transposed, or shifted, by the same number of octaves, then they represent the same song. For example, the melodies B3 D4 - E4 and B5 D6 - E6 are the same.

• Rule 4: If two melodies are written the same, except all the notes in one of them have been transposed, or shifted, by the same number of semitones, then they represent the same song. For example, the melodies B3 D4 - E4 and C#4 E4 - F#4 are the same.

If the songs have not been determined to be the same after the application of these rules, then the songs are not the same.

Input

Input starts with one line containing a positive integer $n$, where $1 \leq n \leq 10^5$, which represents the length of each melody. Next two lines follow, each with a melody, where the melodies consist of $n$ values representing notes or rests, separated by spaces. Notes and rests are written in the same form as mentioned previously in the statement. The lowest note appearing in the input is A0 and the highest note is C8, corresponding to an $88$ key piano. Each note will have a maximum of one # symbol or b symbol.

Output

Output Jebb if the songs are the same, and the record label should sue, otherwise output Neibb.

Scoring

Additonal info on samples

To listen to the melodies in the sample inputs, you can download the sound files here. In sample $5$ you can hear parts of melodies from the songs Ég Á Líf by Örlygur Smári, the former melody, and I Am Cow by the band The Arrogant Worms, the latter melody. In sample $8$ you can hear two parts of the melody from the song Paradise Lost by Symphony X, where the latter melody is the same as the former, but transposed up by a whole step.

16
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - E4 -
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - E4 -

Jebb

16
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - E4 -
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - C4 -

Neibb

16
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - E4 -
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 - D4 - E4

Neibb

16
C4 D4 E4 E4 C4 D4 E4 - C4 D4 E4 E4 D4 - E4 -
C6 D6 E6 E6 C6 D6 E6 - C6 D6 E6 E6 D6 - E6 -

Jebb

16
A4 B4 C#5 - C#5 B4 A4 - A4 G#4 F#4 G#4 F#4 E4 C#4 -
C#4 D4 E4 - G#4 A4 E4 - A4 G#4 F#4 G#4 A4 F#4 E4 -

Neibb

8
C#3 D3 E3 F3 G3 A3 B3 C4
Db3 D3 Fb3 F3 G3 A3 Cb4 C4

Jebb

8
C#3 D3 E3 F3 G3 A3 B3 C4
Db5 D5 Fb5 F5 G5 A5 Cb6 C6

Jebb

25
D5 F4 A4 D5 C5 E4 D5 F4 A4 D5 E5 G4 F5 A4 D5 F5 E5 G4 D5 F4 Bb4 D5 C5 E4 E5
E5 G4 B4 E5 D5 F#4 E5 G4 B4 E5 F#5 A4 G5 B4 E5 G5 F#5 A4 E5 G4 C5 E5 D5 F#4 F#5

Jebb