<|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.

191. Exhibition
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Two companies "A" and "B" decided to hold a joint exhibition of their production. Antitrust committee decided to take an experiment. To have a possibility to show its own production each company must advertise the production of its competitor. The exhibition is built as a straight row of stands. Some stands can be empty, other contain the production of represented companies (each stand can contain the production of only one company). The empty stands are also signed with the names of the companies.
Originally the exhibition consists of just one empty stand, which is signed by the name of one of the companies (by a lot).
The company can choose any of its empty stands and either to fill it with the production of the competitor or to place the empty stand to the left, signed by the name of the competitor, and to the left of that place the stand with its own production. If there are any stands to the left, they are moved to the left. By the beginning of the exhibition all stands must be filled.
Your task is to write a program in accordance with the filled stands before the exhibition to determine if the requirements of the antitrust committee were satisfied or not.

Input
The first line contains the name of the company ("A" or "B"), which was chosen to be the first to fill the empty stand. The second line contains a row of the stands presented to the antitrust committee. The stands are listed from left to right. Letter "A" indicates a stand of company "A", letter "B" - a stand of company "B". Maximum number of stands at the exhibition is 30000.

Output
Output "YES" - if the requirements of the antitrust committee were fulfilled, and "NO" - if not.

Sample test(s)

Input
A
AAB

Output
YES
Author:	Sergey V. Mironov
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

<|response|>
## 1) Abridged problem statement (concise)

We start with **one empty stand** labeled either `A` or `B` (given). Repeatedly, a company may pick an **empty stand labeled with its own letter** and do one of:

1. **Fill** it with the competitor's product (so an empty `A` becomes a filled `B`, and vice versa).
2. **Expand** it by inserting two stands immediately to its **left**: first a **filled stand of its own letter**, then an **empty stand labeled with the competitor**. (The chosen empty stand remains in place.)

By the beginning of the exhibition, **all stands must be filled**.
Given the initial label and the final filled row (a string of `A`/`B`), decide if this final row is achievable.

`|s| ≤ 30000`.

---

## 2) Key observations

### Observation 1: Model the process as a grammar
Treat an **empty stand labeled X** as a nonterminal `S_X` (`X ∈ {A,B}`).

From an empty `A`:
- Fill with competitor: `S_A -> 'B'`
- Expand: produces `'A'` then an empty `B` then the same empty `A`
  `S_A -> 'A' S_B S_A`

Similarly:
- `S_B -> 'A'`
- `S_B -> 'B' S_A S_B`

So:
- `S_A -> 'B' | 'A' S_B S_A`
- `S_B -> 'A' | 'B' S_A S_B`

We must check if the given string `s` can be derived from `S_init`.

### Observation 2: Deterministic choice (LL(1)-like)
If we need to expand `S_A`:
- Next char `'B'` forces `S_A -> 'B'`
- Next char `'A'` forces `S_A -> 'A' S_B S_A`

Same for `S_B`.
So we can parse left-to-right with a stack (predictive parsing).

---

## 3) Full solution approach

We simulate generating the final string using a stack of "pending empty stands".

- Represent pending nonterminals as chars `'A'` (meaning `S_A`) and `'B'` (meaning `S_B`).
- Initialize stack with `[init]`.
- Process `s` from left to right:
  1. If stack is empty → we have no way to generate more output → **NO**.
  2. Pop `top` from stack.
  3. If current output char `c` equals `top`, we must use the expanding rule:
     - `S_A -> 'A' S_B S_A` or `S_B -> 'B' S_A S_B`
     - We already matched the leading terminal (`c`), so we still must produce:
       `S_opponent(top)` then `S_top`
     - Push in reverse order so opponent is processed next:
       push `top`, then push `opponent(top)`.
  4. Else (`c != top`), the only valid way is the terminal rule:
     - `S_A -> 'B'` or `S_B -> 'A'`
     - Consume `c`, push nothing.

After consuming all characters, the stack must be empty (no unfinished empty stands).
If empty → **YES**, else **NO**.

**Complexity:**
Each character causes O(1) stack work → **O(n)** time, **O(n)** memory, `n ≤ 30000`.

---

## 4) C++ implementation

```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;
};

char init;
string s;

void read() { cin >> init >> s; }

void solve() {
    // The problem statement is somewhat hard to parse, but it boils down to a
    // context-free grammar. Let S_A and S_B be nonterminals representing empty
    // stands signed by A and B, and let 'A', 'B' be terminals (filled stands).
    // The two operations give us the following productions:
    //     S_A -> 'B'
    //     S_A -> 'A' S_B S_A
    //     S_B -> 'A'
    //     S_B -> 'B' S_A S_B
    //
    // We need to check if the given string can be derived starting from S_A or
    // S_B (given in input). This grammar is LL(1) since the first terminal
    // uniquely determines which production to apply: if c == X we must expand,
    // if c is the opponent we must use the terminal production. So we can use
    // standard predictive parsing with a stack of pending nonterminals. For each
    // character c, pop the top S_X: if c is the opponent of X, it matches a
    // terminal production and we consume it. If c == X, we apply the expand
    // rule, pushing S_X and then S_{opponent} on top. The string is valid iff
    // the stack is empty at the end.

    auto opponent = [](char c) { return c == 'A' ? 'B' : 'A'; };

    vector<char> stack = {init};
    for(char c: s) {
        if(stack.empty()) {
            cout << "NO" << endl;
            return;
        }

        char top = stack.back();
        stack.pop_back();

        if(c == top) {
            stack.push_back(top);
            stack.push_back(opponent(top));
        }
    }

    cout << (stack.empty() ? "YES" : "NO") << endl;
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def opponent(c: str) -> str:
    return 'B' if c == 'A' else 'A'

def main() -> None:
    data = [line.strip() for line in sys.stdin if line.strip() != ""]
    init = data[0]   # 'A' or 'B'
    s = data[1]      # final filled stands

    # Stack of pending nonterminals: 'A' means S_A, 'B' means S_B
    st = [init]

    for ch in s:
        if not st:
            # No pending empty stand to generate next character.
            print("NO")
            return

        top = st.pop()

        if ch == top:
            # Expand:
            #   S_A -> 'A' S_B S_A
            #   S_B -> 'B' S_A S_B
            #
            # We matched the leading terminal already, so push the remaining
            # nonterminals in reverse order to process opponent first.
            st.append(top)
            st.append(opponent(top))
        else:
            # Terminal rule:
            #   S_A -> 'B' or S_B -> 'A'
            # Nothing to push.
            pass

    # Valid iff all pending nonterminals are resolved exactly at the end.
    print("YES" if not st else "NO")

if __name__ == "__main__":
    main()
```

These implementations follow the deterministic stack-parsing simulation implied by the exhibition rules, and run comfortably within the limits for `n = 30000`.
