import sys
import json

def find_mutations(reference, sample):
    mutations = []

    i, j = 0, 0
    pos = 1  # 1-based position for biology

    while i < len(reference) and j < len(sample):
        if reference[i] == sample[j]:
            i += 1
            j += 1
            pos += 1
        else:
            # Substitution
            if i + 1 < len(reference) and j + 1 < len(sample) and reference[i+1] == sample[j+1]:
                mutations.append({
                    "type": "substitution",
                    "position": pos,
                    "reference": reference[i],
                    "observed": sample[j]
                })
                i += 1
                j += 1
                pos += 1
            # Insertion
            elif j + 1 < len(sample) and reference[i] == sample[j+1]:
                mutations.append({
                    "type": "insertion",
                    "position": pos,
                    "inserted": sample[j]
                })
                j += 1
                pos += 1
            # Deletion
            elif i + 1 < len(reference) and reference[i+1] == sample[j]:
                mutations.append({
                    "type": "deletion",
                    "position": pos,
                    "deleted": reference[i]
                })
                i += 1
                pos += 1
            else:
                mutations.append({
                    "type": "substitution",
                    "position": pos,
                    "reference": reference[i],
                    "observed": sample[j]
                })
                i += 1
                j += 1
                pos += 1

    while j < len(sample):
        mutations.append({
            "type": "insertion",
            "position": pos,
            "inserted": sample[j]
        })
        j += 1
        pos += 1

    while i < len(reference):
        mutations.append({
            "type": "deletion",
            "position": pos,
            "deleted": reference[i]
        })
        i += 1
        pos += 1

    return mutations


if __name__ == "__main__":
    data = json.loads(sys.stdin.read())

    reference = data["reference"].upper()
    sample = data["sample"].upper()

    result = find_mutations(reference, sample)

    message = "No mutation found. Sequence matches reference."
    if len(result) > 0:
        message = f"Mutation found! Total mutations detected: {len(result)}"

    print(json.dumps({
        "message": message,
        "total_mutations": len(result),
        "mutations": result
    }))