<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

302. BHTML 1.0
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The hypertext markup language BHTML 1.0 has only two paired tags. They are UP /UP and DOWN /DOWN. The UP /UP tag capitalizes all letters inside its body (between an open tag and a close one), and DOWN /DOWN makes all inside the body letters lowercase. You are given the text consisting of latin letters and tags. Your task is to write the text right as it will be shown in the Bernet Explorer browser window. Tags in the text are arranged correctly, i.e. they form correct bracket sequence. If a letter lays inside several tags, its case is defined by the most inner tag.

Input
The input contains the string S with the text. The length of the string is a natural number not exceeding 1000. Tags are always written in uppercase.

Output
Write to the output text after the processing.

Example(s)
sample input
sample output
Thi<UP>sIs<DOWN>EaSY</DOWN>Pr<UP>O</UP>ble</UP>m
ThiSISeasyPROBLEm

<|response|>
## 1. Abridged Problem Statement

Given a string S (length ≤ 1000) containing only Latin letters and correctly nested tags `<UP>...</UP>` and `<DOWN>...</DOWN>`, produce the rendered text by:
- Converting every letter inside an `<UP>`…`</UP>` block to uppercase.
- Converting every letter inside a `<DOWN>`…`</DOWN>` block to lowercase.
- If tags are nested, the innermost tag's rule applies.

Output the transformed text with all tags removed.

---

## 2. Detailed Editorial

We need to parse S, keep track of which tags are currently open, and apply the right case transformation to each letter. A classic way is to scan S from left to right, maintain a stack of active modes (`UP` or `DOWN`), and build the output string on the fly:

- Whenever we see `<UP>`, we push `UP` onto the stack and skip over the tag.
- Whenever we see `</UP>`, we pop the stack (it must be `UP`) and skip the tag.
- Likewise for `<DOWN>` and `</DOWN>`.
- For any ordinary letter c, we look at the top of the stack:
  - If it is `UP`, append `toupper(c)`.
  - If it is `DOWN`, append `tolower(c)`.
  - If the stack is empty, append c as is.

Since tags are guaranteed to form a correct bracket sequence, we never pop the wrong tag. Each character and each tag boundary is processed in O(1), so the overall runtime is O(|S|). Memory is O(|S|) for the output and O(depth) ≤ O(|S|) for the stack.

The provided C++ solution does something equivalent but in two passes:
- First pass: it uses a stack of `(char, index)` pairs to detect tags in the raw string and immediately applies case changes to the original string `s` when a closing tag is found. It uses special markers `'1'` and `'2'` on the stack for `<UP>` and `<DOWN>` openings.
- Second pass: it rebuilds the final answer by copying from the now-cased string `s` and skipping over any remaining tag fragments.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string s;

void read() { cin >> s; }

template<typename T>
void pop_back(vector<T> &st, int len) {
    for(int i = 0; i < len; i++) {
        st.pop_back();
    }
}

void pop_back(string &s, int len) {
    for(int i = 0; i < len; i++) {
        s.pop_back();
    }
}

string string_from_last(const vector<pair<char, int>> &st, int len) {
    if(st.size() < len) {
        return "";
    }

    string res;
    for(int i = 0; i < len; i++) {
        res.push_back(st[st.size() - len + i].first);
    }
    return res;
}

string string_from_last(const string &s, int len) {
    if(s.size() < len) {
        return "";
    }

    string res;
    for(int i = 0; i < len; i++) {
        res.push_back(s[s.size() - len + i]);
    }
    return res;
}

char make_upper(char c) {
    if('a' <= c && c <= 'z') {
        return c - 'a' + 'A';
    }
    return c;
}

char make_lower(char c) {
    if('A' <= c && c <= 'Z') {
        return c - 'A' + 'a';
    }
    return c;
}

void solve() {
    // Use '1' char as opening <UP> 
    // Use '2' char as opening <DOWN> 

    vector<pair<char, int>> st;
    for(int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        st.push_back({c, i});
        if(string_from_last(st, 4) == "<UP>") {
            pop_back(st, 4);
            st.push_back({'1', -1});
        } else if(string_from_last(st, 5) == "</UP>") {
            pop_back(st, 5);
            while(st.back().first != '1') {
                s[st.back().second] = make_upper(s[st.back().second]);
                st.pop_back();
            }
            st.pop_back();
        } else if(string_from_last(st, 6) == "<DOWN>") {
            pop_back(st, 6);
            st.push_back({'2', -1});
        } else if(string_from_last(st, 7) == "</DOWN>") {
            pop_back(st, 7);
            while(st.back().first != '2') {
                s[st.back().second] = make_lower(s[st.back().second]);
                st.pop_back();
            }
            st.pop_back();
        }
    }

    string ans;
    for(auto c: s) {
        ans.push_back(c);
        if(string_from_last(ans, 4) == "<UP>") {
            pop_back(ans, 4);
        } else if(string_from_last(ans, 5) == "</UP>") {
            pop_back(ans, 5);
        } else if(string_from_last(ans, 6) == "<DOWN>") {
            pop_back(ans, 6);
        } else if(string_from_last(ans, 7) == "</DOWN>") {
            pop_back(ans, 7);
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
def process_bhtml(s):
    """
    Parse the BHTML string s and return the rendered text:
      <UP>...</UP> => uppercase
      <DOWN>...</DOWN> => lowercase
    Nested tags are allowed; innermost takes precedence.
    """
    i = 0
    n = len(s)
    stack = []       # will store 'UP' or 'DOWN'
    output = []      # list of characters for the result

    while i < n:
        # Check for each possible tag at position i
        if s.startswith("<UP>", i):
            stack.append("UP")
            i += 4
        elif s.startswith("</UP>", i):
            # must match the last pushed
            stack.pop()
            i += 5
        elif s.startswith("<DOWN>", i):
            stack.append("DOWN")
            i += 6
        elif s.startswith("</DOWN>", i):
            stack.pop()
            i += 7
        else:
            # normal character
            c = s[i]
            if stack and stack[-1] == "UP":
                output.append(c.upper())
            elif stack and stack[-1] == "DOWN":
                output.append(c.lower())
            else:
                output.append(c)
            i += 1

    return "".join(output)

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip()
    # only one line of input
    print(process_bhtml(data))
```

---

## 5. Compressed Editorial

Maintain a stack of modes ("UP" or "DOWN"). Scan the input string. On `<UP>` or `<DOWN>`, push the mode; on `</…>` pop it. For each non-tag character, apply `upper()` if the top of stack is `UP`, `lower()` if it is `DOWN`, or leave it unchanged if the stack is empty. Accumulate and print the resulting characters. This runs in O(n) time and uses O(n) space.
