"""exact rational-function parser for the Sage-style rational-function strings of the exact systems (digits, t, + - * / ^, parentheses): returns ascending coefficient lists (strings 'p/q') of num and den.
Pure python (ast walker; no eval)."""
import ast, sys
from fractions import Fraction
try: sys.set_int_max_str_digits(0)
except Exception: pass
class RF:
    __slots__ = ('num', 'den')
    def __init__(s, num, den=None):
        s.num = num; s.den = den if den is not None else {0: Fraction(1)}
        if len(s.den) == 1 and 0 in s.den and s.den[0] != 1:      # constant denominator -> absorb
            c = s.den[0]; s.num = {k: v / c for k, v in s.num.items()}; s.den = {0: Fraction(1)}
def padd(a, b):
    r = dict(a)
    for k, v in b.items(): r[k] = r.get(k, Fraction(0)) + v
    return {k: v for k, v in r.items() if v != 0}
def pmul(a, b):
    r = {}
    for i, x in a.items():
        for j, y in b.items(): r[i + j] = r.get(i + j, Fraction(0)) + x * y
    return {k: v for k, v in r.items() if v != 0}
def pneg(a): return {k: -v for k, v in a.items()}
def rf_add(x, y):
    if x.den == y.den: return RF(padd(x.num, y.num), dict(x.den))
    return RF(padd(pmul(x.num, y.den), pmul(y.num, x.den)), pmul(x.den, y.den))
def rf_mul(x, y): return RF(pmul(x.num, y.num), pmul(x.den, y.den))
def rf_div(x, y): return RF(pmul(x.num, y.den), pmul(x.den, y.num))
def rf_pow(x, n):
    r = RF({0: Fraction(1)}); b = x
    while n > 0:
        if n & 1: r = rf_mul(r, b)
        b = rf_mul(b, b); n >>= 1
    return r
def _ev(node):
    if isinstance(node, ast.Expression): return _ev(node.body)
    if isinstance(node, ast.Constant) and isinstance(node.value, int): return RF({0: Fraction(node.value)})
    if isinstance(node, ast.Name) and node.id == 't': return RF({1: Fraction(1)})
    if isinstance(node, ast.UnaryOp) and isinstance(node.op, (ast.USub, ast.UAdd)):
        v = _ev(node.operand); return RF(pneg(v.num), v.den) if isinstance(node.op, ast.USub) else v
    if isinstance(node, ast.BinOp):
        if isinstance(node.op, ast.Pow):
            if not (isinstance(node.right, ast.Constant) and isinstance(node.right.value, int) and node.right.value >= 0): raise ValueError('only non-negative integer powers')
            return rf_pow(_ev(node.left), int(node.right.value))
        a, b = _ev(node.left), _ev(node.right)
        if isinstance(node.op, ast.Add): return rf_add(a, b)
        if isinstance(node.op, ast.Sub): return rf_add(a, RF(pneg(b.num), b.den))
        if isinstance(node.op, ast.Mult): return rf_mul(a, b)
        if isinstance(node.op, ast.Div): return rf_div(a, b)
    raise ValueError('unsupported expression element: %s' % ast.dump(node)[:80])
def parse_ratfun(s):
    """'(poly)/(poly)' Sage string -> (num_coeffs, den_coeffs) ascending, coefficient strings 'p' or 'p/q'."""
    s = s.strip()
    if s in ('0', ''): return None
    r = _ev(ast.parse(s.replace('^', '**'), mode='eval'))
    nn = max(r.num) if r.num else 0; dn = max(r.den)
    return [str(r.num.get(k, Fraction(0))) for k in range(nn + 1)], [str(r.den.get(k, Fraction(0))) for k in range(dn + 1)]