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

237. Galaxy X: Episode I - Masters of Mind
time limit per test: 0.25 sec.
memory limit per test: 16384 KB
input: standard
output: standard



Galaxy "X" greets you, the Masters of Mind Game. Are you ready to support your galaxy in battle for mind overwhelming? Are you ready to become Overminds? Are you brave enough to fight against the best of the best all-over-the-Universe mind-warriors? Then listen to me, Sons of Earth. That battle seems to be not too hard. Your mission is very simple. You must win at all costs. The Universal Mind contest begins:

The Universal Mind contest consists of several rounds, in which contestants solve logical, mathematical and other kinds of puzzles in fight for universal domination. We are not strong enough yet, and our galaxy can not get too much finance to stimulate our wishes and will to win. So, we do not need to win this contest (we simply are not able to do that truly heroical turn). All that we need is to pass the first round of contest (so called quarterfinals) and, probably, second (so called half-finals).

Our trainer N.A.Taskevich, found out (by using his special secret channels) that at the first round of the contest participants must, given a regular expression with special characters "*", "!" and "?", say the shortest palindrome (if answer is not unique, then you need to say lexicographically smallest one) that can be obtained by replacing special symbols with ordinary alphabet characters (small Latin letters from "a" to "z"), knowing the following rules of replacement:
"*" is replaced by any number of any symbols from alphabet (possibly, zero symbols - empty string).
"!" is replaced by exactly three symbols from alphabet.
"?" is replaced by exactly one symbol from alphabet.

Palindrome is a string which does not change after reversing it (for example reversed string for "astalavista" is "atsivalatsa", so "astalavista" is not palindrome, but "abacaba" is palindrome, because its reversed string is "abacaba" too).

But even using all this, we currently do not fully understand logic of answers because we can not always say, whether answer is correct or not correct. To make some clearance about that, we need to write a program which determines a really correct answer (shortest lexicographically smallest one).

Input
On the first line of input file there is a regular expression, consisting of ordinary alphabet characters (small Latin letters) and special characters ("*", "!" and "?"). The length of regular expression does not exceed 255.

Output
On the first line of output file you must write single word "YES" (when it is possible to replace special characters to produce a palindrome) or "NO" (when it is impossible). In the case of positive answer, the second line of output file must contain the shortest lexicographically smallest palindrome which can be obtained from given regular expression. Words must be written without quotes.

Sample test(s)

Input
Test #1
abac?ba

Test #2
a?dcaba

Test #3
avtobus*

Output
Test #1
YES
abacaba

Test #2
NO

Test #3
YES
avtobusubotva
Author:	Alexey Preobrajensky
Resource:	---
Date:	December, 2003

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

Given a string of length at most `255` containing:

- lowercase letters `a`–`z`;
- `?`, which must be replaced by exactly one lowercase letter;
- `!`, which must be replaced by exactly three lowercase letters;
- `*`, which may be replaced by any number of lowercase letters, possibly zero.

Determine whether the expression can be transformed into a palindrome.

If possible, output:

1. `YES`
2. the shortest possible palindrome

If several shortest palindromes exist, output the lexicographically smallest one.

Otherwise output `NO`.

---

## 2. Key Observations

### Observation 1: Replace `!` with `???`

The symbol `!` means exactly three arbitrary letters, so it is equivalent to three `?` characters.

After preprocessing, the expression contains only:

- lowercase letters;
- `?`;
- `*`.

The maximum length becomes:

```text
255 * 3 = 765
```

---

### Observation 2: Use interval dynamic programming

We need the result to be a palindrome. For any substring `s[l...r]`, consider the shortest palindrome that can be generated from it.

Define:

```text
dp[l][r] = minimum length of a palindrome obtainable from s[l...r]
```

If impossible:

```text
dp[l][r] = INF
```

An empty substring can generate the empty palindrome:

```text
dp[l][r] = 0, if l > r
```

---

### Observation 3: Handle the outermost characters

For a palindrome, the first and last generated characters must be equal.

There are several cases.

#### Case 1: Left side is `*`

The `*` can generate nothing:

```text
dp[l][r] = min(dp[l][r], dp[l + 1][r])
```

#### Case 2: Right side is `*`

Similarly:

```text
dp[l][r] = min(dp[l][r], dp[l][r - 1])
```

#### Case 3: Both ends are not `*`

Then both ends must generate one character.

They are compatible if:

- both are equal fixed letters;
- or at least one is `?`.

Then:

```text
dp[l][r] = min(dp[l][r], dp[l + 1][r - 1] + 2)
```

#### Case 4: Left is not `*`, right is `*`

The right `*` may generate a character matching the left side.

The right `*` remains available for the inner part, because it may generate more characters:

```text
dp[l][r] = min(dp[l][r], dp[l + 1][r] + 2)
```

#### Case 5: Left is `*`, right is not `*`

Symmetrically:

```text
dp[l][r] = min(dp[l][r], dp[l][r - 1] + 2)
```

---

### Observation 4: Shortest length is not enough

We also need the lexicographically smallest palindrome among all shortest ones.

So after computing `dp`, we reconstruct the answer.

For every interval `s[l...r]`, among all transitions that achieve the optimal value `dp[l][r]`, we build candidate palindromes and choose the lexicographically smallest one.

---

## 3. Full Solution Approach

### Step 1: Preprocess

Expand every `!` into `???`.

Example:

```text
a!b*  ->  a???b*
```

Let the expanded string be `s` and its length be `n`.

---

### Step 2: Compute minimum palindrome lengths

Use interval DP.

Base case:

```text
dp[i][i] = 0, if s[i] == '*'
dp[i][i] = 1, otherwise
```

For longer intervals, use the transitions described above.

The answer exists if:

```text
dp[0][n - 1] < INF
```

Otherwise, print `NO`.

---

### Step 3: Reconstruct lexicographically smallest shortest palindrome

We process intervals again in increasing length.

Let:

```text
best[l][r] = lexicographically smallest palindrome of length dp[l][r]
             obtainable from s[l...r]
```

For memory efficiency, we do not store all strings. A state of length `len` depends only on states of length:

- `len - 1`
- `len - 2`

So we keep only three rolling layers of strings.

When trying a transition, we check whether it preserves optimal length.

For example, if both ends are non-`*` and compatible:

```text
if dp[l + 1][r - 1] + 2 == dp[l][r]:
    candidate = c + best[l + 1][r - 1] + c
```

The character `c` is chosen as the smallest possible matching character:

- `a` and `a` force `a`;
- `a` and `?` force `a`;
- `?` and `b` force `b`;
- `?` and `?` choose `a`.

For every valid optimal transition, build its candidate and keep the lexicographically smallest one.

---

### Complexity

Let `n` be the expanded length, `n <= 765`.

DP states:

```text
O(n^2)
```

Each state has constant transitions.

Reconstruction compares and builds strings of length up to `O(n)`, so the worst-case time is:

```text
O(n^3)
```

Memory:

```text
O(n^2)
```

for the integer DP table, plus rolling string layers.

---

## 4. C++ Implementation with Detailed Comments

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

void read() { cin >> regex_str; }

void solve() {
    // First, '!' is just shorthand for "???", so we expand it and only have to
    // reason about letters, '?' and '*'. The core DP is dp[l][r], the minimum
    // length of a palindrome that the regex segment s[l..r] can produce. Since
    // the produced string is a palindrome, its first and last characters must
    // agree, and they come from s[l] and s[r] respectively (or, if either is a
    // '*', from that '*' absorbing one extra character). That gives a small
    // case split on (s[l], s[r]): when both are non-'*' we peel both ends with
    // a compatible outer char (letters force it, '?' is free); when one is
    // '*' and the other isn't, the '*' may match empty (drop and recurse) or
    // absorb the matching char on its side while staying in place; when both
    // are '*' either may match empty.
    //
    // Length-optimal moves can produce different palindromes, so for the
    // lex-smallest answer we have to actually compare the candidates rather
    // than rely on a heuristic ('prefer drop' / 'prefer peel' both have
    // counterexamples, e.g. "*bab*ba" needs drop but "*!ba*!" needs peel).
    // We therefore build the actual pal[l][r] string for every cell, in
    // increasing-length order. Each cell of length L depends only on cells
    // of length L-1 and L-2, so we keep just three rolling layers of strings
    // alive at any time, which caps memory at O(n^2) chars and stays well
    // under the limit even at n=765 after '!' expansion.

    string s;
    for(char c: regex_str) {
        if(c == '!') {
            s += "???";
        } else {
            s += c;
        }
    }

    int n = s.size();
    if(n == 0) {
        cout << "YES\n\n";
        return;
    }

    const int INF = INT_MAX / 2;
    vector<vector<int>> dp(n, vector<int>(n, INF));

    auto is_star = [&](int p) { return s[p] == '*'; };
    auto is_q = [&](int p) { return s[p] == '?'; };

    auto get_dp = [&](int a, int b) -> int {
        if(a > b) {
            return 0;
        }
        return dp[a][b];
    };

    for(int i = 0; i < n; i++) {
        dp[i][i] = is_star(i) ? 0 : 1;
    }

    for(int len = 2; len <= n; len++) {
        for(int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            int best = INF;

            if(is_star(l) && get_dp(l + 1, r) < INF) {
                best = min(best, get_dp(l + 1, r));
            }

            if(is_star(r) && get_dp(l, r - 1) < INF) {
                best = min(best, get_dp(l, r - 1));
            }

            if(!is_star(l) && !is_star(r)) {
                int inner = get_dp(l + 1, r - 1);
                bool ok = true;
                if(!is_q(l) && !is_q(r) && s[l] != s[r]) {
                    ok = false;
                }
                if(ok && inner < INF) {
                    best = min(best, inner + 2);
                }
            } else if(!is_star(l) && is_star(r)) {
                int inner = get_dp(l + 1, r);
                if(inner < INF) {
                    best = min(best, inner + 2);
                }
            } else if(is_star(l) && !is_star(r)) {
                int inner = get_dp(l, r - 1);
                if(inner < INF) {
                    best = min(best, inner + 2);
                }
            }

            dp[l][r] = best;
        }
    }

    if(dp[0][n - 1] >= INF) {
        cout << "NO\n";
        return;
    }

    vector<string> layer_a(n), layer_b(n), layer_c(n);
    vector<string>* lm2 = &layer_a;
    vector<string>* lm1 = &layer_b;
    vector<string>* cur = &layer_c;

    string answer;
    for(int len = 1; len <= n; len++) {
        for(int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            (*cur)[l].clear();
            if(dp[l][r] >= INF) {
                continue;
            }

            if(len == 1) {
                if(is_star(l)) {
                    (*cur)[l] = "";
                } else if(is_q(l)) {
                    (*cur)[l] = "a";
                } else {
                    (*cur)[l] = string(1, s[l]);
                }
                continue;
            }

            int target = dp[l][r];
            bool have = false;
            string best;

            auto try_cand = [&](string cand) {
                if(!have || cand < best) {
                    best = std::move(cand);
                    have = true;
                }
            };

            if(!is_star(l) && !is_star(r)) {
                int inner = (len == 2) ? 0 : dp[l + 1][r - 1];
                if(inner != INF && inner + 2 == target) {
                    bool ok = true;
                    char c = 0;
                    if(!is_q(l) && !is_q(r)) {
                        if(s[l] == s[r]) {
                            c = s[l];
                        } else {
                            ok = false;
                        }
                    } else if(!is_q(l)) {
                        c = s[l];
                    } else if(!is_q(r)) {
                        c = s[r];
                    } else {
                        c = 'a';
                    }
                    if(ok) {
                        const string& ip =
                            (len == 2) ? string() : (*lm2)[l + 1];
                        string cand;
                        cand.reserve(ip.size() + 2);
                        cand += c;
                        cand += ip;
                        cand += c;
                        try_cand(std::move(cand));
                    }
                }
            }

            if(!is_star(l) && is_star(r)) {
                int inner = dp[l + 1][r];
                if(inner != INF && inner + 2 == target) {
                    char c = is_q(l) ? 'a' : s[l];
                    const string& ip = (*lm1)[l + 1];
                    string cand;
                    cand.reserve(ip.size() + 2);
                    cand += c;
                    cand += ip;
                    cand += c;
                    try_cand(std::move(cand));
                }
            }

            if(is_star(l) && !is_star(r)) {
                int inner = dp[l][r - 1];
                if(inner != INF && inner + 2 == target) {
                    char c = is_q(r) ? 'a' : s[r];
                    const string& ip = (*lm1)[l];
                    string cand;
                    cand.reserve(ip.size() + 2);
                    cand += c;
                    cand += ip;
                    cand += c;
                    try_cand(std::move(cand));
                }
            }

            if(is_star(l) && dp[l + 1][r] == target) {
                try_cand((*lm1)[l + 1]);
            }

            if(is_star(r) && dp[l][r - 1] == target) {
                try_cand((*lm1)[l]);
            }

            (*cur)[l] = std::move(best);
        }

        if(len == n) {
            answer = std::move((*cur)[0]);
            break;
        }

        vector<string>* tmp = lm2;
        lm2 = lm1;
        lm1 = cur;
        cur = tmp;
        for(auto& x: *cur) {
            x.clear();
            x.shrink_to_fit();
        }
    }

    cout << "YES\n" << answer << "\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();
        solve();
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def solve():
    regex = sys.stdin.readline().strip()

    # Step 1: Expand '!' into "???"
    parts = []
    for ch in regex:
        if ch == "!":
            parts.append("???")
        else:
            parts.append(ch)

    s = "".join(parts)
    n = len(s)

    if n == 0:
        print("YES")
        print()
        return

    INF = 10 ** 9

    # dp[l][r] = minimum palindrome length obtainable from s[l...r]
    dp = [[INF] * n for _ in range(n)]

    def is_star(i):
        return s[i] == "*"

    def is_question(i):
        return s[i] == "?"

    def get_dp(l, r):
        if l > r:
            return 0
        return dp[l][r]

    # Base case: one symbol
    for i in range(n):
        if is_star(i):
            dp[i][i] = 0
        else:
            dp[i][i] = 1

    # Fill DP by increasing interval length
    for length in range(2, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1
            best = INF

            # Left '*' becomes empty
            if is_star(l):
                best = min(best, get_dp(l + 1, r))

            # Right '*' becomes empty
            if is_star(r):
                best = min(best, get_dp(l, r - 1))

            # Both ends are not '*'
            if not is_star(l) and not is_star(r):
                inner = get_dp(l + 1, r - 1)

                compatible = True

                # Two fixed different letters cannot match
                if (
                    not is_question(l)
                    and not is_question(r)
                    and s[l] != s[r]
                ):
                    compatible = False

                if compatible and inner < INF:
                    best = min(best, inner + 2)

            # Left is not '*', right is '*'
            elif not is_star(l) and is_star(r):
                inner = get_dp(l + 1, r)

                if inner < INF:
                    best = min(best, inner + 2)

            # Left is '*', right is not '*'
            elif is_star(l) and not is_star(r):
                inner = get_dp(l, r - 1)

                if inner < INF:
                    best = min(best, inner + 2)

            dp[l][r] = best

    # If impossible
    if dp[0][n - 1] >= INF:
        print("NO")
        return

    """
    Reconstruct lexicographically smallest shortest palindrome.

    prev2 stores answers for intervals of length length - 2.
    prev1 stores answers for intervals of length length - 1.
    cur   stores answers for intervals of current length.
    """
    prev2 = [""] * n
    prev1 = [""] * n

    answer = ""

    for length in range(1, n + 1):
        cur = [""] * n

        for l in range(0, n - length + 1):
            r = l + length - 1

            if dp[l][r] >= INF:
                continue

            # Base case: one symbol
            if length == 1:
                if is_star(l):
                    cur[l] = ""
                elif is_question(l):
                    cur[l] = "a"
                else:
                    cur[l] = s[l]

                continue

            target = dp[l][r]
            best_candidate = None

            def try_candidate(candidate):
                nonlocal best_candidate
                if best_candidate is None or candidate < best_candidate:
                    best_candidate = candidate

            # Case 1: both ends are not '*'
            if not is_star(l) and not is_star(r):
                inner_len = get_dp(l + 1, r - 1)

                if inner_len + 2 == target:
                    compatible = True
                    c = ""

                    if not is_question(l) and not is_question(r):
                        if s[l] == s[r]:
                            c = s[l]
                        else:
                            compatible = False
                    elif not is_question(l):
                        c = s[l]
                    elif not is_question(r):
                        c = s[r]
                    else:
                        c = "a"

                    if compatible:
                        inner = "" if length == 2 else prev2[l + 1]
                        candidate = c + inner + c
                        try_candidate(candidate)

            # Case 2: left is not '*', right is '*'
            if not is_star(l) and is_star(r):
                inner_len = dp[l + 1][r]

                if inner_len + 2 == target:
                    c = "a" if is_question(l) else s[l]
                    inner = prev1[l + 1]
                    candidate = c + inner + c
                    try_candidate(candidate)

            # Case 3: left is '*', right is not '*'
            if is_star(l) and not is_star(r):
                inner_len = dp[l][r - 1]

                if inner_len + 2 == target:
                    c = "a" if is_question(r) else s[r]
                    inner = prev1[l]
                    candidate = c + inner + c
                    try_candidate(candidate)

            # Case 4: left '*' becomes empty
            if is_star(l) and dp[l + 1][r] == target:
                try_candidate(prev1[l + 1])

            # Case 5: right '*' becomes empty
            if is_star(r) and dp[l][r - 1] == target:
                try_candidate(prev1[l])

            cur[l] = best_candidate if best_candidate is not None else ""

        if length == n:
            answer = cur[0]
            break

        # Rotate rolling layers
        prev2, prev1 = prev1, cur

    print("YES")
    print(answer)


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