// Save for later.

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

div_t floordiv(int x, int y) {
    int q = x / y - ((x % y) && (x ^ y) < 0);
    int r = x - y * q;
    return (div_t) {q, r};
}

#define INTERNAL_BASE 10

typedef struct {
    int *digit;
    int  count;
    int  sign;
} Bigint;

int _digit_add(int *x, int m, const int *y, int n)
{
    assert(m >= n);

    int carry = 0;
    int i;

    for (i = 0; i < n; i++)
    {
        carry = x[i] + y[i] + carry;
        x[i] = carry % INTERNAL_BASE;
        carry /= INTERNAL_BASE;
    }
    for (; carry && i < m; i++)
    {
        carry = x[i] + carry;
        x[i] = carry % INTERNAL_BASE;
        carry /= INTERNAL_BASE;
    }
    return carry;
}

int _digit_sub(int *x, int m, const int *y, int n)
{
    assert(m >= n);

    int borrow = 0;
    int i;

    for (i = 0; i < n; i++)
    {
        borrow = x[i] - y[i] - borrow;
        div_t d = floordiv(borrow, INTERNAL_BASE);
        x[i] = d.rem;
        borrow = d.quot & 1;
    }
    for (; borrow && i < m; i++)
    {
        borrow = x[i] - borrow;
        div_t d = floordiv(borrow, INTERNAL_BASE);
        x[i] = d.rem;
        borrow = d.quot & 1;
    }
    return borrow;
}

void _bigint_resize_noinit(Bigint* a, int n)
{
    assert(n > 0);
    a->digit = realloc(a->digit, n * sizeof *a->digit);
    a->count = n;
}

void _bigint_resize(Bigint* a, int n, int v)
{
    assert(0 <= v && v < INTERNAL_BASE);

    int m = a->count;
    _bigint_resize_noinit(a, n);
    for (int i = m; i < n; i++)
        a->digit[i] = v;
}

void _bigint_append(Bigint* a, int v)
{
    _bigint_resize(a, a->count + 1, v);
}

void _bigint_normalize(Bigint *a)
{
    while (a->count > 1 && a->digit[a->count-1] == 0)
        a->count--;
    if (a->count == 1 && a->digit[0] == 0)
        a->sign = 0;
}

// ..

void bigint_clear(Bigint *a)
{
    free(a->digit);
    a->digit = 0;
    a->count = 0;
    a->sign  = 0;
}

void bigint_init(Bigint *a)
{
    a->digit = 0;
    a->count = 0;
    a->sign  = 0;
    _bigint_append(a, 0);
}

void bigint_init_set_si(Bigint *a, int v)
{
    a->digit = 0;
    a->count = 0;
    a->sign  = v < 0;
    do
    {
        _bigint_append(a, abs(v % INTERNAL_BASE));
        v /= INTERNAL_BASE;
    }
    while (v != 0);
}

void bigint_set(Bigint *a, const Bigint *b)
{
    _bigint_resize_noinit(a, b->count);
    memmove(a->digit, b->digit, b->count * sizeof *a->digit);
    a->sign = b->sign;
}

void bigint_swap(Bigint *a, Bigint *b)
{
    Bigint t = *a; *a = *b; *b = t;
}

int _bigint_compare(const Bigint *a, const Bigint *b)
{
    int m = a->count;
    int n = b->count;
    if (m != n)
        return (m < n) ? -1 : 1;

    for (int i = m; i > 0; i--)
    {
        int x = a->digit[i-1];
        int y = b->digit[i-1];
        if (x != y)
            return (x < y) ? -1 : 1;
    }
    return 0;
}

void _bigint_add_lower(Bigint *c, const Bigint *a, const Bigint *b)
{
    if (a->count < b->count)
    {
        const Bigint *t = a; a = b; b = t;
    }

    bigint_set(c, a);
    int carry = _digit_add(c->digit, c->count, b->digit, b->count);
    if (carry != 0)
        _bigint_append(c, carry);
    _bigint_normalize(c);
}

void _bigint_sub_lower(Bigint *c, const Bigint *a, const Bigint *b)
{
    int sign = 0;

    if (_bigint_compare(a, b) < 0)
    {
        const Bigint *t = a; a = b; b = t;
        sign = 1;
    }

    bigint_set(c, a);
    _digit_sub(c->digit, c->count, b->digit, b->count);
    c->sign = sign;
    _bigint_normalize(c);
}

void _bigint_add_or_sub(Bigint *c, const Bigint *a, const Bigint *b, int invert)
{
    if ((a->sign == b->sign) ^ invert)
    {
        _bigint_add_lower(c, a, b);
        c->sign = a->sign;
    }
    else
    {
        if (a->sign)
            _bigint_sub_lower(c, b, a);
        else
            _bigint_sub_lower(c, a, b);
    }
}

void bigint_add(Bigint *c, const Bigint *a, const Bigint *b)
{
    _bigint_add_or_sub(c, a, b, 0);
}

void bigint_sub(Bigint *c, const Bigint *a, const Bigint *b)
{
    _bigint_add_or_sub(c, a, b, 1);
}

void bigint_print(const Bigint *a)
{
    if (a->sign)
        putchar('-');
    for (int i = a->count; i > 0; i--)
        printf("%d", a->digit[i-1]); // Base-10
    putchar('\n');
}

// ..

void fatalerror(const char *msg)
{
    fprintf(stderr, "Error: %s\n", msg);
    exit(1);
}

int _bigint_to_si(const Bigint *a)
{
    int result = 0;
    for (int i = a->count; i > 0; i--)
    {
        if (__builtin_mul_overflow(result, INTERNAL_BASE, &result) ||
            __builtin_add_overflow(result, a->digit[i-1], &result))
            fatalerror("overflow");
    }
    return a->sign ? -result : result;
}

void test(int n)
{
    Bigint t; bigint_init(&t);

    for (int x = -n; x <= n; x++)
        for (int y = -n; y <= n; y++)
        {
            Bigint a; bigint_init_set_si(&a, x);
            Bigint b; bigint_init_set_si(&b, y);
            bigint_add(&t, &a, &b);
            assert(_bigint_to_si(&t) == x+y);
            bigint_sub(&t, &a, &b);
            assert(_bigint_to_si(&t) == x-y);
            bigint_clear(&a);
            bigint_clear(&b);
        }

    bigint_clear(&t);
}

void fibonacci(int n, Bigint *result)
{
    Bigint a; bigint_init_set_si(&a, 0);
    Bigint b; bigint_init_set_si(&b, 1);
    Bigint t; bigint_init(&t);

    for (int i = 0; i < n; i++)
    {
        bigint_add(&t, &a, &b);
        bigint_swap(&b, &a); // a -> b
        bigint_swap(&a, &t); // t -> a
    }

    bigint_swap(&a, result);

    bigint_clear(&a);
    bigint_clear(&b);
    bigint_clear(&t);
}

int main(void)
{
    test(123);

    Bigint a; bigint_init(&a);
    Bigint b; bigint_init(&b);
    Bigint c; bigint_init(&c);

    fibonacci(202, &a);
    fibonacci(101, &b);

    bigint_sub(&c, &a, &b);

    bigint_print(&a);
    bigint_print(&b);
    bigint_print(&c);

    bigint_clear(&a);
    bigint_clear(&b);
    bigint_clear(&c);
    return 0;
}