Blue Gene, Jr.

Time limit1sMemory limit128 MB

Summary

Simulate the recursive mutation rules on each short alphanumeric code and print the stabilized code.

Level: Medium5 of 10
Topics: Recursion, Simulation, String
Solved: No attempts yet

Problem

Inspired by IBM's Blue Gene project, the CEO of Universal Biological Machinery (UBM) has called on you, UBM's top software engineer. The company's privately subsidized space program found a virus on Mars, the Areopagusvirus, and you have to write a program that calculates how it mutates.

Input

The input is a non-empty series of up to 100 data sets. Each data set follows the description below, and no blank lines separate the data sets.

A single data set has three parts.

Start line: a single line START N, where $1 \le N \le 20$ .
Viral code: a single line of $N$ alphanumeric characters. An alphanumeric character is an uppercase letter A to Z, or a digit 0 to 9.
End line: a single line END.

A single line ENDOFINPUT follows the final data set.

Output

For each data set there is exactly one output set, and no blank lines separate the output sets.

A single output set is one line holding the viral code after it has stabilized through mutating. The viral code mutates according to the following rules.

The first viral segment to mutate begins with the first alphanumeric character of the viral code and ends with the rightmost alphanumeric character of the code.
If the first alphanumeric character of a viral segment is a letter, that character is unstable, and it mutates into $n$ , the number of mutations that occur in the viral segment immediately to its right (see rule 5). If $n$ is greater than 9, the character mutates into the remainder of $n$ divided by 10. If there is no viral segment immediately to the right of the unstable character, it mutates into 0.
If the first alphanumeric character of a viral segment is a digit $n$ from 1 to 9, that character is also unstable, and it mutates into $n-1$ . It also makes the viral segment that begins with the alphanumeric character $n$ positions to its right and ends with the rightmost alphanumeric character of the viral code mutate. If there is no alphanumeric character $n$ positions to its right, then the viral segment immediately to its right (see rule 5) mutates, if one exists.
If the first alphanumeric character of a viral segment is 0, that character is stable and does not mutate. The character stays 0, and no mutation is counted.
The viral segment immediately to the right of an alphanumeric character begins with the alphanumeric character one position to its right and ends with the rightmost alphanumeric character of the viral code.

Examples2

Example 1

Input

START 1
A
END
START 4
A1B2
END
START 15
A3B2CCC4AD1232R
END
START 15
0ABCDEFGHIJKLMN
END
START 11
ABCDEFGHIJK
END
START 10
9AAAAAAAAA
END
ENDOFINPUT

Expected output

0
3011
82B26543AD11310
0ABCDEFGHIJKLMN
09876543210
8AAAAAAAA0

Example 2

Input

START 1
0
END
START 1
9
END
START 1
Z
END
START 1
5
END
START 1
1
END
START 1
A
END
ENDOFINPUT

Expected output