from math import gcd
from typing import Optional, Tuple

def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def find_solution(a: int, b: int, c: int) -> Optional[Tuple[int, int]]:
    g = gcd(a, b)
    if c % g != 0:
        return None
    
    # Scale everything down by gcd
    a, b, c = a//g, b//g, c//g
    
    # Find base solution using extended GCD
    _, x0, y0 = extended_gcd(a, b)
    x0 *= c
    y0 *= c
    
    # Find the general solution
    # x = x0 + k*(b/g)
    # y = y0 - k*(a/g)
    # We need both x and y to be non-negative
    k_min = -(x0 // b) if x0 < 0 else -((y0) // a)
    k_max = (y0 // a) if y0 > 0 else (x0 // b)
    
    # Find k that gives minimum positive solution
    for k in range(k_min, k_max + 1):
        x = x0 + k * b
        y = y0 - k * a
        if x >= 0 and y >= 0:
            return (x, y)
    return None

def solve_machine(ax: int, ay: int, bx: int, by: int, px: int, py: int, max_presses: Optional[int] = None) -> Optional[int]:
    # Find solution for x-coordinate
    sol_x = find_solution(ax, bx, px)
    if not sol_x:
        return None
    
    # Find solution for y-coordinate
    sol_y = find_solution(ay, by, py)
    if not sol_y:
        return None
    
    # Check if solutions match
    if sol_x[0] != sol_y[0] or sol_x[1] != sol_y[1]:
        return None
    
    # Check max presses constraint if specified
    if max_presses and (sol_x[0] > max_presses or sol_x[1] > max_presses):
        return None
    
    # Calculate tokens needed (3 for A, 1 for B)
    return 3 * sol_x[0] + sol_x[1]

def parse_input(filename: str):
    machines = []
    with open(filename, 'r') as f:
        lines = f.read().strip().split('\n\n')
        for machine in lines:
            lines = machine.strip().split('\n')
            ax = int(lines[0].split('X+')[1].split(',')[0])
            ay = int(lines[0].split('Y+')[1])
            bx = int(lines[1].split('X+')[1].split(',')[0])
            by = int(lines[1].split('Y+')[1])
            px = int(lines[2].split('X=')[1].split(',')[0])
            py = int(lines[2].split('Y=')[1])
            machines.append((ax, ay, bx, by, px, py))
    return machines

def solve_part1(machines):
    total_tokens = 0
    for machine in machines:
        tokens = solve_machine(*machine, max_presses=100)
        if tokens is not None:
            total_tokens += tokens
    return str(total_tokens)

def solve_part2(machines):
    offset = 10**13
    total_tokens = 0
    modified_machines = []
    for ax, ay, bx, by, px, py in machines:
        modified_machines.append((ax, ay, bx, by, px + offset, py + offset))
    
    for machine in modified_machines:
        tokens = solve_machine(*machine)
        if tokens is not None:
            total_tokens += tokens
    return str(total_tokens)

# Read and parse input
machines = parse_input("input.txt")

# Solve part 1
print(solve_part1(machines))

# Solve part 2
print(solve_part2(machines))