Generalized German Quotation

Interview

Time limit3sMemory limit512 MB

Summary

Given a string of << and >> marks, decide whether it forms nested conventional or reversed German quotes and rewrite every mark as an opening [ or closing ], or report that none exists.

Level: Medium6 of 10
Topics: Stack, Implementation, Greedy
Solved: No attempts yet

Problem

German uses the conventional angular quote marks (‘«’ and ‘»’), so one may quote text in a «conventional» way. What is unconventional in German is that one may also quote text in a »reversed« way. In normal life these styles do not mix, since they are used in different German-speaking countries. But let us have some fun: if we merge these two typographical traditions and forget the rules for nested quotes (that is, if we allow unlimited nesting), we get the Generalized German rules, which let us write small quotation masterpieces like this:

«»Anf¨uhrungszeichen« means «quote marks» in German»

Informally, a string is a correct quotation if removing all non-quote characters from it yields a correctly formed Generalized German text. Formally:

⟨G⟩ ::= ε | ⟨G⟩⟨G⟩ | ‘«’⟨G⟩‘»’ | ‘»’⟨G⟩‘«’

Thus a correct quotation is an empty string, a concatenation of two correct quotations, or a correct quotation quoted in either the conventional or the reversed way. In the latter two cases, the quote mark to the left of ⟨G⟩ is a starting quote and the quote mark to the right of ⟨G⟩ is an ending quote. For example, in the quotation string ‘«»’ the quote mark ‘«’ is a starting quote, while in the string ‘»«’ the same quote mark ‘«’ is an ending quote.

Your task is to check whether a given string is a correct quotation, and if it is, restore its structure, that is, replace all starting quote marks with ‘[’ and all ending quote marks with ‘]’.

Input

The first and only line of the input contains a single string with a sequence of quote marks. To stay within plain ASCII, the quote marks ‘«’ and ‘»’ are encoded as ‘<<’ and ‘>>’, respectively. The string contains no other characters. The string is not empty and is not longer than 254 ASCII characters.

Output

If the input string is a correct quotation, replace all starting quote marks with ‘[’, all ending quote marks with ‘]’, and output the result. If there is more than one possible solution, output any of them.

If the string is not a correct quotation, output “Keine Loesung”.

Examples3

Example 1
Input
```
<<>><<<<>>>>
```
Expected output
```
[][[]]
```
Example 2
Input
```
>><<>>>><<<<<<>>>><<
```
Expected output
```
[][[]][][]
```
Example 3
Input
```
<<<<>>
```
Expected output
```
Keine Loesung
```