#!/usr/bin/env python3
import sys
from collections import defaultdict, Counter
from typing import DefaultDict, Mapping
from copy import deepcopy


def apply_rules(template: str, rules: Mapping[str, str]) -> str:
    # sliding window babey
    new = ""
    for i in range(len(template) - 1):
        new += template[i] + rules[template[i : i + 2]]
    return new + template[-1]


def part1(template: str, rules: Mapping[str, str]):
    for i in range(10):
        template = apply_rules(template, rules)
    counts: DefaultDict[str, int] = defaultdict(lambda: 0)
    for c in template:
        counts[c] += 1
    counts_sorted = sorted(counts.items(), key=lambda pair: pair[1])
    _, least = counts_sorted[0]
    _, most = counts_sorted[-1]
    print(most - least)


def part2(template: str, rules: Mapping[str, str]):
    # Apply rules with counts instead of building a string
    counts: Counter = Counter()

    for i in range(len(template) - 1):
        counts[template[i : i + 2]] += 1

    for _ in range(40):
        new_counts: Counter = Counter()
        for pair, count in counts.items():
            # Create the two new pairs, and remove the old one
            rule = rules[pair]
            p1 = pair[0] + rule
            p2 = rule + pair[1]
            # Subtract from this pair, and then add the new ones
            new_counts[p1] += counts[pair]
            new_counts[p2] += counts[pair]
        counts = new_counts
    # Count all the letters, only using the first character.
    # If we count the second character, we double-count.
    letters: Counter = Counter()
    for pair in counts:
        letters[pair[0]] += counts[pair]
    # We just need to count the last character in the original template - since this never changes.
    letters[template[-1]] += 1
    print(max(letters.values()) - min(letters.values()))


template = sys.stdin.readline().strip()
# blank
sys.stdin.readline()
rules = {
    rule: translate.strip()
    for rule, translate in map(lambda line: line.split(" -> "), sys.stdin)
}


print("Part 1")
part1(template, rules)
print("Part 2")
part2(template, rules)