HTML Editor

Time limit1sMemory limit128 MB

Summary

Given a valid HTML string and a range, output that substring wrapped with the tags needed to preserve its formatting.

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

Problem

While building an HTML editor for a smartphone, you get stuck on the cut / copy / paste feature. It looks simple, but it is actually quite tricky, because the selected range must keep exactly the same formatting it had before. To make matters worse, the formatting of the selection depends on tags that live outside the selected range.

You are given an HTML document and you select the range from position $B$ up to position $E$ . You must add the necessary tags before and after the substring from $B$ to $E$ so that, on its own, it has the same formatting it had inside the original document.

Every tag consists of an opening tag (e.g. ) and a matching closing tag (e.g. ); they always come in pairs, and another tag may be nested between them. However, you cannot write a closing tag while an unmatched open tag is still pending. For example, abcdefghi is not valid HTML. You also cannot open a tag that is already open (not yet closed). For example, recursive b is not valid HTML.

Input

The input consists of several test cases, one per line, each in the form B E TEXT.

$B$ is the start position of the substring (inclusive) and $E$ is the end position (exclusive); TEXT is the HTML document held in the editor.
The three values are separated by single spaces. If $L$ is the length of TEXT, then $0 \le B \le E \le L$ .
The line after the last test case is -1 -1, which marks the end of the input.

TEXT is at most 200 characters long and consists only of characters whose ASCII value is between 32 and 126 inclusive. An opening tag always has the form <X>, where $X$ is at least one character long and consists only of a-z, A-Z, 0-9, and -. The character < is used only to start a tag.

Every HTML document in the input is always valid: every opening tag has a matching closing tag and vice versa, and no substring ever cuts a tag in the middle.

Output

For each test case, print on one line the substring from $B$ to $E$ (the character at position $E$ is not included) with the tags needed on both sides so that it has the same formatting as in the original document.

Examples3

Example 1

Input

0 15 Testing<b>!</b>
18 23 <big>100, <bigger>1000, <biggest>10000</biggest></bigger></big>
4 4 <b>123</b>
0 16   :-/ :-> :-) :-<-> </->
-1 -1

Expected output

Testing<b>!</b>
<big><bigger>1000,</bigger></big>
<b></b>
  :-/ :-> :-) :-

Example 2
Input
```
3 6 <a>XYZ</a>
-1 -1
```
Expected output
```
<a>XYZ</a>
```
Example 3
Input
```
0 11 hello world
-1 -1
```
Expected output
```
hello world
```