## 1. Abridged Problem Statement

There are stones in a row, each colored blue `b`, red `r`, yellow `y`, or white `w`.

A replacement rule has the form:

```text
xy -> c
```

meaning two adjacent stones with colors `x` then `y` may be replaced by one stone of color `c`.

The input gives all rules grouped by resulting color, then gives the initial row of stones.

For each color, determine whether there exists some sequence of valid replacements that reduces the entire row to exactly one stone of that color. Output all such colors, or `Nobody` if no color can win.

The order of colors in the output may be arbitrary.

Constraints:

- Initial row length: `1..200`
- Each color has `1..16` replacement rules.



## 2. Detailed Editorial

This problem asks whether the whole string of stones can be reduced to a single stone of each possible color.

This is very similar to parsing a string with a context-free grammar:

- Each color is a nonterminal.
- A rule `xy -> c` means a segment reducible to color `x` followed by a segment reducible to color `y` can together be reduced to color `c`.

Since the row length is at most `200`, we can use interval dynamic programming.

### State

Let:

```text
dp[l][r]
```

be the set of colors into which the substring `row[l..r]` can be reduced.

There are only 4 colors, so we store this set as a 4-bit integer mask:

```text
bit 0 -> blue
bit 1 -> red
bit 2 -> yellow
bit 3 -> white
```

For example, if `dp[l][r] = 5`, binary `0101`, then the segment can be reduced to blue and yellow.

### Base Case

A segment of length `1` is just one stone, so it can only be reduced to its own color:

```text
dp[i][i] = mask(row[i])
```

### Transition

For a longer segment `row[l..r]`, the last replacement must merge two adjacent already-reduced parts:

```text
row[l..mid]     -> color a
row[mid+1..r]   -> color b
```

If the rule `ab -> c` exists, then:

```text
row[l..r] -> color c
```

So for every split point `mid`, and every possible pair of colors from the left and right masks, we add all possible resulting colors.

Formally:

```text
for mid in [l, r-1]:
    for a in dp[l][mid]:
        for b in dp[mid+1][r]:
            dp[l][r] includes rule_mask[a][b]
```

Here:

```text
rule_mask[a][b]
```

is also a 4-bit mask containing all colors that can be produced from adjacent colors `a b`.

Multiple rules may have the same pair but different result colors, so a mask is convenient.

### Answer

After filling DP, `dp[0][n-1]` contains exactly the colors into which the whole row can be reduced.

Output those colors. If the mask is zero, output:

```text
Nobody
```

### Correctness Argument

We prove that `dp[l][r]` contains exactly the colors into which segment `row[l..r]` can be reduced.

#### Base Case

For `l = r`, the segment consists of a single stone. It can only already be its own color and cannot be reduced further. The initialization stores exactly that color.

#### Transition Soundness

Whenever the algorithm adds color `c` to `dp[l][r]`, it found a split `mid`, a color `a` reachable from `row[l..mid]`, and a color `b` reachable from `row[mid+1..r]`, with a valid rule `ab -> c`.

By the induction hypothesis, the left and right parts can indeed be reduced to stones of colors `a` and `b`. Then the rule allows replacing those two stones by `c`. Therefore `row[l..r]` can be reduced to `c`.

#### Transition Completeness

Suppose `row[l..r]` can be reduced to color `c`. Consider the final replacement in this reduction. Immediately before it, the segment consists of two stones produced from two adjacent subsegments:

```text
row[l..mid] and row[mid+1..r]
```

for some `mid`.

Let their colors be `a` and `b`. Then there must be a rule `ab -> c`. By induction, `a` is in `dp[l][mid]` and `b` is in `dp[mid+1][r]`. The algorithm considers this split and pair, so it adds `c`.

Thus the DP is exact.

### Complexity

There are `O(n^2)` intervals and `O(n)` split points per interval. For each split we try at most `4 * 4 = 16` color pairs.

So the complexity is:

```text
O(n^3 * 16) = O(n^3)
```

Memory usage is:

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



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

int rule_mask[4][4];
string row;

int color_id(char c) { return c == 'b' ? 0 : c == 'r' ? 1 : c == 'y' ? 2 : 3; }

void read() {
    int cnt[4];
    for(int c = 0; c < 4; c++) {
        cin >> cnt[c];
    }

    for(int c = 0; c < 4; c++) {
        for(int i = 0; i < cnt[c]; i++) {
            string rule;
            cin >> rule;
            rule_mask[color_id(rule[0])][color_id(rule[1])] |= 1 << c;
        }
    }

    cin >> row;
}

void solve() {
    // dp[l][r] is a 4-bit mask whose set bits are the colors that the segment
    // row[l..r] can be collapsed into as a single stone. Any collapse of a
    // segment ends with one final merge of two adjacent stones, and those two
    // stones are the independent collapses of a prefix row[l..mid] into some
    // color a and a suffix row[mid+1..r] into some color b. So for every split
    // point mid and every reachable pair (a, b) we add all colors that the
    // replacement rules allow (a, b) to turn into. rule_mask[a][b] already
    // holds that set as a mask, including the case where one ordered pair is
    // listed under several target colors.
    //
    // The base case is a single stone, which can only stay its own color. The
    // colors Sasha can win with are exactly the bits of dp[0][n-1], since
    // winning means reducing the whole row to one stone of his color.

    int n = (int)row.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) {
        dp[i][i] = 1 << color_id(row[i]);
    }

    for(int len = 2; len <= n; len++) {
        for(int l = 0, r = len - 1; r < n; l++, r++) {
            int mask = 0;
            for(int mid = l; mid < r; mid++) {
                int left = dp[l][mid], right = dp[mid + 1][r];
                for(int a = 0; a < 4; a++) {
                    for(int b = 0; b < 4; b++) {
                        if((left >> a & 1) && (right >> b & 1)) {
                            mask |= rule_mask[a][b];
                        }
                    }
                }
            }

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

    string colors = "bryw", ans;
    for(int c = 0; c < 4; c++) {
        if(dp[0][n - 1] >> c & 1) {
            ans += colors[c];
        }
    }

    cout << (ans.empty() ? "Nobody" : 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();
        solve();
    }

    return 0;
}
```



## 4. Python Solution

This Python version uses the same DP idea, with one small optimization: it precomputes transitions between masks.

Instead of trying all `4 * 4` color pairs for every split, we precompute:

```text
transition[left_mask][right_mask]
```

which directly gives all colors obtainable by merging any color from `left_mask` with any color from `right_mask`.

```python
import sys


def color_id(c):
    """
    Convert a color character to an integer id.

    b -> 0
    r -> 1
    y -> 2
    w -> 3
    """
    if c == 'b':
        return 0
    if c == 'r':
        return 1
    if c == 'y':
        return 2
    return 3


def main():
    # Read all input tokens.
    data = sys.stdin.read().split()

    # Pointer to the current token.
    ptr = 0

    # Read counts B, R, Y, W.
    cnt = list(map(int, data[ptr:ptr + 4]))
    ptr += 4

    # rule_mask[a][b] is a 4-bit mask of colors that can be produced
    # by replacing adjacent stones of colors a followed by b.
    rule_mask = [[0] * 4 for _ in range(4)]

    # Rules are given grouped by resulting color:
    # first rules producing blue, then red, then yellow, then white.
    for result_color in range(4):
        # Read all rules for this result color.
        for _ in range(cnt[result_color]):
            # Rule is a two-character string like "br".
            rule = data[ptr]
            ptr += 1

            # Convert both input colors to ids.
            a = color_id(rule[0])
            b = color_id(rule[1])

            # Mark that pair (a, b) can produce result_color.
            rule_mask[a][b] |= 1 << result_color

    # Read the initial row of stones.
    row = data[ptr]

    # Number of stones.
    n = len(row)

    # Precompute transition between masks.
    #
    # transition[left_mask][right_mask] gives all colors obtainable by:
    # choosing one color a from left_mask,
    # choosing one color b from right_mask,
    # then applying a rule a b -> result.
    transition = [[0] * 16 for _ in range(16)]

    # There are only 16 possible 4-bit masks.
    for left_mask in range(16):
        for right_mask in range(16):
            # Store all possible resulting colors here.
            result_mask = 0

            # Try every color a from the left mask.
            for a in range(4):
                if not (left_mask & (1 << a)):
                    continue

                # Try every color b from the right mask.
                for b in range(4):
                    if not (right_mask & (1 << b)):
                        continue

                    # Add all possible result colors for pair (a, b).
                    result_mask |= rule_mask[a][b]

            # Save the precomputed result.
            transition[left_mask][right_mask] = result_mask

    # dp[l][r] is a 4-bit mask of colors into which row[l..r] can reduce.
    dp = [[0] * n for _ in range(n)]

    # Base case: each one-character segment is already one stone of its color.
    for i, ch in enumerate(row):
        dp[i][i] = 1 << color_id(ch)

    # Process intervals by increasing length.
    for length in range(2, n + 1):
        # l is the left boundary.
        for l in range(0, n - length + 1):
            # r is the right boundary.
            r = l + length - 1

            # Accumulate all colors possible for this interval.
            mask = 0

            # Try all final split positions.
            for mid in range(l, r):
                # Left part is row[l..mid].
                left_mask = dp[l][mid]

                # Right part is row[mid+1..r].
                right_mask = dp[mid + 1][r]

                # Add all colors obtainable by merging these two parts.
                mask |= transition[left_mask][right_mask]

                # All four colors are already possible, no need to continue.
                if mask == 15:
                    break

            # Store result for row[l..r].
            dp[l][r] = mask

    # Characters in the order matching ids 0, 1, 2, 3.
    colors = "bryw"

    # Full-row achievable colors.
    final_mask = dp[0][n - 1]

    # Build answer.
    answer = []

    # Add every color whose bit is set.
    for c in range(4):
        if final_mask & (1 << c):
            answer.append(colors[c])

    # Print answer or Nobody.
    if answer:
        print("".join(answer))
    else:
        print("Nobody")


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



## 5. Compressed Editorial

Use interval DP.

Encode colors as:

```text
b = 0, r = 1, y = 2, w = 3
```

Store every set of possible colors as a 4-bit mask.

Let:

```text
dp[l][r]
```

be the mask of colors into which substring `row[l..r]` can be reduced.

Base:

```text
dp[i][i] = 1 << color_id(row[i])
```

For each rule `ab -> c`, store:

```text
rule_mask[a][b] |= 1 << c
```

Transition:

```text
dp[l][r] = OR over all splits mid:
           OR over a in dp[l][mid], b in dp[mid+1][r]:
           rule_mask[a][b]
```

The last move reducing an interval must merge two already-reduced adjacent subintervals, so this recurrence considers every possible valid reduction.

Finally, inspect `dp[0][n-1]`. Output all colors whose bits are set, or `Nobody` if the mask is zero.

Complexity:

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

or `O(n^3)` with precomputed mask transitions.
