Genome Compression Minimization Operation

A gene string is defined as a string that contains only the characters A, G, C and T. For any legal gene string S, we can compute its compressed string T by compressing each maximal block of consecutive identical characters into the count (if greater than 1) followed by that character. In other words, if a block has length 1, only the character is written; if its length is k (k > 1) then it is written as kX, where X is the repeated character. For instance, the compressed string of AAAAACAAAAACC is 5AC5A2C.

Given a legal gene string S whose compressed string is T, you are allowed to perform exactly one operation on S. The allowed operations are one of the following:

• Insert: Insert a gene character Z immediately after the x^th character of S.
• Delete: Remove the x^th character of S.
• Replace: Replace the x^th character of S with a different gene character Z.

Let S′ be the string after the operation and let T′ be its compressed string (computed as described above, with any number in a LaTeX formatted way, e.g. if the count is 1 then simply write the character, and if the count is greater than 1 then write it as $k$ followed by the letter). Your task is to choose one valid operation so that the length of T′ is minimized.

Note: If multiple operations yield the same minimum compressed length, you can output any one of them. The output format for the operation should be as follows:

• If the operation is an insertion, output: I x Z (meaning insert character Z after the x^th character of S).
• If the operation is a deletion, output: D x (meaning delete the x^th character of S).
• If the operation is a replacement, output: R x Z (meaning replace the x^th character with Z).

inputFormat

The input consists of a single line containing a non‐empty string T which represents the compressed version of a legal gene string S. The string T is formed by digits and characters among {A, G, C, T} as described above.

outputFormat

Output one line representing one valid operation that, when applied to S, minimizes the length of the compressed string T′. The output should be in one of the following formats:

• I x Z: representing an insertion after the x^th character of S.
• D x: representing a deletion of the x^th character of S.
• R x Z: representing a replacement of the x^th character of S with character Z.

Here, x is a 1-indexed position.

sample

5AC5A2C

D 6