Sourav and Arijit are very fond of numbers and have decided to communicate with each other using encrypted messages. Arijit has recently left Sourav with an Encrypted Message EM. Sourav has the following information regarding the message:

• The Encrypted Message EM is a a binary string consisting of only 0s and 1s.
• The Actual Message AM is a string consisting of only the following uppercase english alphabets: A, B, C, D, E, F.
• There is a mapping from the above alphabets to binary strings as follows:

A -> 1

B -> 01

C -> 10

D -> 100

E -> 101

F -> 110

Arijit has given Sourav the following task:

Given the Encrypted Message EM, find all possible even length AMs in alphabatical order, and compute minimum number of edit operations required to transform the first half of these AMs into its last half. For example, in the string "ADECAB", "ADE" is the first half, while "CAB" is the second half. 

The allowed edit operations are:
i) Insert a character
ii) Delete a character
iii) Replace a character (all edit operations have same cost)

For example:
i) To transform "cat" to "bats", it would require 2 operations: "cat" -> "bat" (replace 'c' with 'b'), "bat" -> "bats" (insert 's').

ii) To transform "abcd" to "bcde", it would require 2 operations: "abcd" -> "bcd" (remove 'a'), "bcd" -> "bcde" (insert 'e').

Sourav is busy with some urgent work, and so has asked you to help him out. Please help Sourav to find all the possible even decodings in alphabatical order with corresponding number of minimum edit operations required.

Input Format:

The only input line contains the Encrypted Message EM which is a binary string of only 0s and 1s.

Output Format:

The ouput contains all possible even length Actual Messages (AMs) (in alphabatical order) and their corresponding edit operations (space seperated) in new lines.

If no even length Actual Message is possible, output "SORRY" (without the quotes).

Constraints:

$1 \leq |EM| \leq 40$