Problem: Analysing Bach

Want to try solving this problem? You can submit your code online if you log in or register.

Analysing Bach

Input File: bachin.txt
Output File: bachout.txt
Time Limit: 1.667 seconds

Back in the era when musicians did not have the opportunity to grace CD covers with pictures of themselves, the composer Bach developed a habit of embedding the letters of his name in his music. At that time, the letters B, A, C and H were all notes of the musical scale, and a number of his pieces contained these four notes consecutively. Thus he left his mark on history.

You have some friends who compose as a hobby, and it has suddenly struck you to see if they have also embedded their names in some of their masterpieces.

For simplicity, we will have ten notes in our musical scale, represented by the digits 0,1,...,9. You cannot go any higher or lower, since your friends are writing for beginner saxophonists. Each musical piece can thus be represented as a sequence of digits.

We will also represent the composer's name as a sequence of digits. Your task is to find the composer's name embedded in the piece.

Take for example the following musical delight:

1467654543234545679905

Say the composer's name translates to 67654. Then we can see the composer's name beginning at the third character.

Bach also often transposed his name up or down. This corresponds to adding or subtracting some constant amount from each digit in the composer's name. We see the digits 45432 starting at the seventh digit, which corresponds to the composer's name transposed down by two.

Bach even inverted his name from time to time. This corresponds to replacing each digit d with the corresponding digit 9-d. So in our example the composer's name inverted is 32345, which appears beginning at the tenth digit. Finally, the composer may even be as bold as to invert and transpose, such as our composer has done beginning at the fourteenth digit where we see 54567.

Input

The first line of the input shall consist of a single string of digits representing the composer's name, whose length will be between 1 and 50 digits inclusive.

The remainder of the input file will contain a musical piece, possibly split over a number of lines for convenience. Each line will be a sequence of between 1 and 50 digits, and there will be at most 600 such lines. Together these lines form the musical piece, and occurrences of the composer's name may run across line breaks.

The musical piece will be terminated by a line containing the single character #.

Output

Your program must output each occurrence of the composer's name, in the order in which they appear in the piece.

If the occurrence is exact or simply transposed, you must output a line containing the integer i, where the occurrence begins at the ith note. If the output is inverted or inverted and transposed, you must output a line containing i followed by a single space and the word "inverted".

You are guaranteed that any given occurrence will not be both uninverted and inverted.

If no occurrences are found, your program must output the single line "No occurrences.".

Sample Input 1

67654
14676545
43234545679
905
#

Sample Output 1

3
7
10 inverted
14 inverted

Sample Input 2

636
14676545
43234545679
905
#

Sample Output 2

No occurrences.

Scoring

For each test case, let n be the number of occurrences of the composer's name. If your program correctly finds c of these occurrences and incorrectly identifies i fraudulent occurrences, it will be awarded (c-i)/n of the available marks for the test case, down to a minimum of zero.

If there are no occurrences in the test case, your program will be awarded either all or none of the available marks for the test case according to whether or not it correctly identified this fact.