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

273. Game Po
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



In the eastern country Pon-pong there is a very popular game Po. Po is the game with stones of four different colors: blue, red, yellow and white. The game is played by four participants. Before the beginning all stones are randomly placed in a row in front of the participants, each player chooses one of the stone colors (all players should have different colors). After that the game process begins. Each of the players in a turn chooses two nearby stones and replaces them by the third one, but only if this change is permitted by the "List of Po Replacements". Replacement is possible if the stones in the row and in the "List of Po Replacements" are in the same order. The game is considered to be finished if it is impossible to perform any change on the stones row. If after the end of the game only one stone remains, the player who chose the color of the stone left is a winner. If there are multiple stones, then the game result is draw. The boy Sasha liked very much the game Po during his visit to Pon-pong. He noticed, that in some games the players with some color are doomed to loose before the beginning of the game (after the distribution of the colors between players, but before the first move). Sasha decided to choose only such color, that he will have some chance to win the game, i.e. there is some sequence of players' moves, that leads to Sasha's victory.

Input
Each stone color is defined by one symbol: "b" -- blue, "r" -- red, "y" -- yellow and "w" -- white. The first line of the input file contains integer numbers B, R, Y and W (1 <= B,R,Y,W <= 16). The following B lines contain the rules of replacement of stones to the blue stone (one rule per line). Each rule is a pair of symbols without spaces, denoting the two stones which can be replaced by the blue one. The following R lines describe the rules of replacement to the red stone, Y lines --- to the yellow stone and W lines -- to the white stone. The last line contains from 1 to 200 symbols denoting stone colors -- the row of the stones before the beginning of the game.

Output
Output the single line without spaces containing the list of colors, for which there is a chance to win the game (in any order). If it is impossible to win the game with any color, output "Nobody".

Sample test(s)

Input
Test #1
2 1 1 1
br
bw
bw
wb
wy
brwy

Test #2
1 1 1 1
br
bw
yr
by
bbbbbbbbbbb

Output
Test #1
br

Test #2
Nobody
Author:	Sergey V. Mironov, Alexander S. Ivanov
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

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

There are stones in a row. Each stone has one of four colors:

```text
b = blue, r = red, y = yellow, w = white
```

A replacement rule has form:

```text
xy -> c
```

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

Given all replacement rules and the initial row, determine for which colors there exists **some sequence of valid replacements** that reduces the whole row to exactly one stone of that color.

If no color can be the final single stone, output:

```text
Nobody
```

Otherwise output all possible winning colors in any order.

---

## 2. Key Observations

### Observation 1: The game is like parsing a string

A replacement rule:

```text
xy -> c
```

can be viewed in reverse as:

```text
c can be formed from x followed by y
```

So the problem is similar to checking which nonterminals can generate a substring in a context-free grammar.

There are only 4 possible colors, so we can store sets of colors efficiently.

---

### Observation 2: Any final reduction has a last move

Suppose a substring `row[l..r]` can be reduced to one stone.

The last move must merge two adjacent stones. Those two stones must have come from two smaller adjacent substrings:

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

If there is a rule:

```text
ab -> c
```

then:

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

This naturally suggests interval dynamic programming.

---

### Observation 3: Use bitmasks for color sets

There are only 4 colors, so we encode a set of possible colors as a 4-bit integer:

```text
bit 0 -> b
bit 1 -> r
bit 2 -> y
bit 3 -> w
```

For example:

```text
mask = 5 = binary 0101
```

means the segment can be reduced to colors `b` and `y`.

---

## 3. Full Solution Approach

### Color Encoding

We map colors to integers:

```text
b -> 0
r -> 1
y -> 2
w -> 3
```

---

### Rule Storage

Let:

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

be a 4-bit mask of all colors that can result from replacing adjacent colors `a` and `b`.

For example, if both rules exist:

```text
br -> b
br -> y
```

then:

```text
rule_mask[b][r] = bit(b) | bit(y)
```

This is necessary because the same ordered pair may produce multiple possible colors.

---

### DP Definition

Let:

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

be a 4-bit mask of all colors into which substring `row[l..r]` can be reduced.

---

### Base Case

A substring of length `1` is already one stone.

Therefore:

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

---

### Transition

For every interval `[l, r]`, try every possible split point `mid`:

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

If the left part can become color `a`, and the right part can become color `b`, and there is a rule:

```text
ab -> c
```

then the whole interval can become `c`.

So:

```text
dp[l][r] |= rule_mask[a][b]
```

for all possible colors `a` and `b`.

Because there are only 4 colors, checking all pairs is cheap.

We can also precompute:

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

which directly gives the result mask obtainable by merging any color from `left_mask` with any color from `right_mask`.

---

### Final Answer

After filling the DP table, the possible winning colors are exactly the bits set in:

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

If this mask is zero, output:

```text
Nobody
```

Otherwise output the corresponding color letters.

---

### Complexity

There are `O(n^2)` intervals and `O(n)` split points per interval.

For each split, checking color pairs costs at most `16`, but with precomputed mask transitions it becomes `O(1)`.

So the total complexity is:

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

Memory usage:

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

Since `n <= 200`, this is easily feasible.

---

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

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

---

## 5. Python Implementation with Detailed Comments

```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():
    data = sys.stdin.read().split()
    ptr = 0

    # Read numbers of rules producing 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 color a followed by color b.
    """
    rule_mask = [[0] * 4 for _ in range(4)]

    """
    Rules are grouped by resulting color:
    first rules producing blue,
    then red,
    then yellow,
    then white.
    """
    for result_color in range(4):
        for _ in range(cnt[result_color]):
            rule = data[ptr]
            ptr += 1

            a = color_id(rule[0])
            b = color_id(rule[1])

            # Mark that a followed by b can produce result_color.
            rule_mask[a][b] |= 1 << result_color

    # Read initial row of stones.
    row = data[ptr]
    n = len(row)

    """
    Precompute transition between masks.

    transition[left_mask][right_mask] gives all colors obtainable by:
    - choosing any color from left_mask,
    - choosing any color from right_mask,
    - applying a replacement rule.
    """
    transition = [[0] * 16 for _ in range(16)]

    for left_mask in range(16):
        for right_mask in range(16):
            result_mask = 0

            for a in range(4):
                if not (left_mask & (1 << a)):
                    continue

                for b in range(4):
                    if not (right_mask & (1 << b)):
                        continue

                    result_mask |= rule_mask[a][b]

            transition[left_mask][right_mask] = result_mask

    """
    dp[l][r] is a 4-bit mask.

    A bit c is set if row[l..r] can be reduced to one stone of color c.
    """
    dp = [[0] * n for _ in range(n)]

    # Base case: one stone can only stay its own color.
    for i, ch in enumerate(row):
        dp[i][i] = 1 << color_id(ch)

    """
    Process all intervals by increasing length.
    """
    for length in range(2, n + 1):
        for l in range(0, n - length + 1):
            r = l + length - 1

            mask = 0

            """
            Try every final split.

            The last replacement inside row[l..r] must merge:
            - one stone obtained from row[l..mid]
            - one stone obtained from row[mid+1..r]
            """
            for mid in range(l, r):
                left_mask = dp[l][mid]
                right_mask = dp[mid + 1][r]

                mask |= transition[left_mask][right_mask]

                # All four colors are possible, so we can stop early.
                if mask == 15:
                    break

            dp[l][r] = mask

    # Convert final mask to output characters.
    colors = "bryw"
    final_mask = dp[0][n - 1]

    answer = []

    for c in range(4):
        if final_mask & (1 << c):
            answer.append(colors[c])

    if answer:
        print("".join(answer))
    else:
        print("Nobody")


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