I haven't seen that number before! Write a program that goes through a string of non-whitespace characters (you may assume that they are digits 0 to 9, but nothing in the way they are to be processed depends on this) and adds spaces according to the following rules.


Let the current token be the empty string, and the previously emitted tokens be an empty set.
Iterate through the characters of the string. For each character, first append the character to the current token. Then if the current token is not already in the set of previously emitted tokens, add the current token to that set and let the new current token be the empty string.
If when you reach the end of the string the current token is empty, output the previously emitted tokens in order of emission, separated by a space character. Otherwise output the original string verbatim.


Input

The input to the STDIN should be a sequence of digits.

Output

The program should print the result as specified in step 3.

Samples

Sample inputs

2015
10101010
4815162342
101010101010
3455121372425
123456789101112131415
314159265358979323846264338327950288419716939937


Sample outputs

2 0 1 5
10101010
4 8 1 5 16 2 3 42
1 0 10 101 01 010
3 4 5 51 2 1 37 24 25
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 1 4 15 9 2 6 5 35 8 97 93 23 84 62 64 33 83 27 95 0 28 841 971 69 39 937




This is code golf, so standard CG rules apply. Shortest program in bytes wins.

(Please request any clarifications in the comments. I'm still new to this. Thanks!)
Retina, 68 61 bytes

+`\b(\w+?)(?&lt;!\b\1 .*)(\w+)$
$1 $2
(?=.* (.+)$(?&lt;=\b\1 .+)) 
&lt;empty&gt;


&lt;empty&gt; is an empty line. Note the trailing space on line 3. You can run the above code from a single file with the -s flag.

Explanation

+`\b(\w+?)(?&lt;!\b\1 .*)(\w+)$
$1 $2


This first step implements rules 1 to 6. It is a regex substitution which is applied repeatedly until the string stops changing (that's what the + is for). In each step we add a single space into the string from left to right (following the rules of the challenge). The regex matches the shortest string of digits which hasn't appeared in the already processed part of the string. We ensure that we're looking at a prefix of the remaining string with the word boundary \b and checking that we can reach the end of the string without passing spaces with (\w+)$. The latter also ensures that we only perform one replacement per step.

(?=.* (.+)$(?&lt;=\b\1 .+)) 
&lt;empty&gt;


This matches any space (which is at the end of the regex), provided that the last segment of the string is the same as any other segment in the string, and replaces them with the empty string. That is, we undo the first step if it resulted in an invalid final segment, implementing rule 7.