Problem 574

Verifying Primes — CRT meet-in-the-middle for V(p); primorials in i128.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 574
# Verifying Primes — CRT meet-in-the-middle for V(p); primorials in i128.

extern {
    function calloc(n: i64, size: i64) -> ptr<void>
    function free(p: ptr<void>) -> void
}

function egcd(a0: i128, b0: i128, outx: ptr<i128>, outy: ptr<i128>) -> i128 {
    let mut a: i128 = a0
    let mut b: i128 = b0
    let mut x0: i128 = 1
    let mut y0: i128 = 0
    let mut x1: i128 = 0
    let mut y1: i128 = 1
    while b != 0 {
        let q: i128 = a / b
        let na: i128 = b
        b = a - q * b
        a = na
        let nx: i128 = x1
        x1 = x0 - q * x1
        x0 = nx
        let ny: i128 = y1
        y1 = y0 - q * y1
        y0 = ny
    }
    outx[0] = x0
    outy[0] = y0
    return a
}

function modinv128(a0: i128, m: i128) -> i128 {
    let xy: ptr<i128> = calloc(2, 16)
    let g: i128 = egcd(a0 % m, m, xy, xy + 1)
    let x: i128 = xy[0]
    free(xy)
    if g != 1 { return 0 }
    let mut r: i128 = x % m
    if r < 0 { r = r + m }
    return r
}

function sieve(limit: i64, primes: ptr<i64>) -> i64 {
    let is_prime: ptr<i8> = calloc(limit + 1, 1)
    if is_prime == null { return 0 }
    let mut i: i64 = 0
    while i <= limit {
        is_prime[i] = 1
        i = i + 1
    }
    is_prime[0] = 0
    is_prime[1] = 0
    i = 2
    while i * i <= limit {
        if is_prime[i] != 0 {
            let mut j: i64 = i * i
            while j <= limit {
                is_prime[j] = 0
                j = j + i
            }
        }
        i = i + 1
    }
    let mut m: i64 = 0
    i = 2
    while i <= limit {
        if is_prime[i] != 0 {
            primes[m] = i
            m = m + 1
        }
        i = i + 1
    }
    free(is_prime)
    return m
}

function subset_sums128(terms: ptr<i128>, k: i64, modv: i128, out: ptr<i128>) -> i64 {
    out[0] = 0
    let mut n: i64 = 1
    let mut t: i64 = 0
    while t < k {
        let term: i128 = terms[t]
        let mut i: i64 = 0
        let old: i64 = n
        while i < old {
            out[n] = (out[i] + term) % modv
            n = n + 1
            i = i + 1
        }
        t = t + 1
    }
    return n
}

function sort_i128(a: ptr<i128>, n: i64) -> void {
    let mut i: i64 = 1
    while i < n {
        let key: i128 = a[i]
        let mut j: i64 = i - 1
        while j >= 0 && a[j] > key {
            a[j + 1] = a[j]
            j = j - 1
        }
        a[j + 1] = key
        i = i + 1
    }
}

function bisect_left128(a: ptr<i128>, n: i64, x: i128) -> i64 {
    let mut lo: i64 = 0
    let mut hi: i64 = n
    while lo < hi {
        let mid: i64 = (lo + hi) / 2
        if a[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

function min_B_difference(p: i64, primes: ptr<i64>, pk: i64, M: i128, bases: ptr<i128>) -> i128 {
    if pk == 0 { return 1 }
    let terms: ptr<i128> = calloc(pk, 16)
    let mut i: i64 = 0
    while i < pk {
        let r: i128 = primes[i] as i128
        let mut negp: i128 = (-(p as i128)) % r
        if negp < 0 { negp = negp + r }
        terms[i] = (negp * bases[i]) % M
        i = i + 1
    }
    let mid: i64 = pk / 2
    let L: ptr<i128> = calloc(1 << mid, 16)
    let R: ptr<i128> = calloc(1 << (pk - mid), 16)
    let nL: i64 = subset_sums128(terms, mid, M, L)
    # copy second half terms
    let termsR: ptr<i128> = calloc(pk - mid, 16)
    i = 0
    while i < pk - mid {
        termsR[i] = terms[mid + i]
        i = i + 1
    }
    let nR: i64 = subset_sums128(termsR, pk - mid, M, R)
    free(termsR)
    sort_i128(R, nR)
    let mut best: i128 = M
    let p128: i128 = p as i128
    i = 0
    while i < nL {
        let x: i128 = L[i]
        if x != 0 && (x % p128) != 0 {
            if x < best { best = x }
        }
        i = i + 1
    }
    i = 0
    while i < nR {
        let x: i128 = R[i]
        if x != 0 && (x % p128) != 0 {
            if x < best { best = x }
        }
        i = i + 1
    }
    i = 0
    while i < nL {
        let l: i128 = L[i]
        let target: i128 = M - l
        let mut j: i64 = bisect_left128(R, nR, target)
        while j < nR {
            let s: i128 = l + R[j]
            if s == M {
                j = j + 1
            } else {
                if s < M {
                    break
                }
                let res: i128 = s - M
                if res >= best {
                    break
                }
                if (res % p128) != 0 {
                    best = res
                    break
                }
                j = j + 1
            }
        }
        i = i + 1
    }
    free(terms)
    free(L)
    free(R)
    return best
}

function max_B_sum(p: i64, primes: ptr<i64>, pk: i64, M: i128, bases: ptr<i128>) -> i128 {
    let limit: i128 = (p / 2) as i128
    if pk == 0 { return limit }
    let Amax: i128 = (p as i128) - limit
    if M > Amax * limit { return -1 }
    let terms: ptr<i128> = calloc(pk, 16)
    let mut i: i64 = 0
    while i < pk {
        let r: i128 = primes[i] as i128
        terms[i] = (((p as i128) % r) * bases[i]) % M
        i = i + 1
    }
    let residues: ptr<i128> = calloc(1 << pk, 16)
    let nr: i64 = subset_sums128(terms, pk, M, residues)
    let mut bestB: i128 = 0
    i = 0
    while i < nr {
        let b0: i128 = residues[i]
        if b0 == 0 {
            if M <= limit {
                let B: i128 = (limit / M) * M
                if B > bestB { bestB = B }
            }
        } else {
            if b0 <= limit {
                let B: i128 = b0 + ((limit - b0) / M) * M
                if B > bestB { bestB = B }
            }
        }
        i = i + 1
    }
    free(terms)
    free(residues)
    if bestB == 0 { return -1 }
    return bestB
}

function q_for_p(p: i64, primes: ptr<i64>, np: i64) -> i64 {
    let mut i: i64 = 0
    while i < np {
        let q: i64 = primes[i]
        if q * q > p { return q }
        i = i + 1
    }
    return 0
}

function S(n: i64) -> i64 {
    let primes: ptr<i64> = calloc(10000, 8)
    let np: i64 = sieve(n + 200, primes)
    let mut max_q: i64 = 0
    let mut i: i64 = 0
    while i < np {
        let p: i64 = primes[i]
        if p < n {
            let q: i64 = q_for_p(p, primes, np)
            if q > max_q { max_q = q }
        }
        i = i + 1
    }
    let mut nq: i64 = 0
    i = 0
    while i < np {
        if primes[i] <= max_q { nq = nq + 1 }
        i = i + 1
    }
    let Ms: ptr<i128> = calloc(nq, 16)
    let base_offs: ptr<i64> = calloc(nq, 8)
    let base_lens: ptr<i64> = calloc(nq, 8)
    let all_bases: ptr<i128> = calloc(nq * nq + 8, 16)
    let mut bcap: i64 = 0
    i = 0
    while i < nq {
        let mut M: i128 = 1
        let mut j: i64 = 0
        while j < i {
            M = M * (primes[j] as i128)
            j = j + 1
        }
        Ms[i] = M
        base_offs[i] = bcap
        base_lens[i] = i
        j = 0
        while j < i {
            let r: i128 = primes[j] as i128
            let Mr: i128 = M / r
            let inv: i128 = modinv128(Mr % r, r)
            all_bases[bcap] = (Mr * inv) % M
            bcap = bcap + 1
            j = j + 1
        }
        i = i + 1
    }

    let mut total: i128 = 0
    i = 0
    while i < np {
        let p: i64 = primes[i]
        if p < n {
            let q: i64 = q_for_p(p, primes, np)
            let mut qidx: i64 = 0
            while primes[qidx] != q { qidx = qidx + 1 }
            let M: i128 = Ms[qidx]
            let pk: i64 = base_lens[qidx]
            let bases: ptr<i128> = calloc(pk + 1, 16)
            let mut j: i64 = 0
            while j < pk {
                bases[j] = all_bases[base_offs[qidx] + j]
                j = j + 1
            }
            let Adiff: i128 = (p as i128) + min_B_difference(p, primes, pk, M, bases)
            let Bsum: i128 = max_B_sum(p, primes, pk, M, bases)
            if Bsum < 0 {
                total = total + Adiff
            } else {
                let Asum: i128 = (p as i128) - Bsum
                if Asum < Adiff {
                    total = total + Asum
                } else {
                    total = total + Adiff
                }
            }
            free(bases)
        }
        i = i + 1
    }
    free(primes)
    free(Ms)
    free(base_offs)
    free(base_lens)
    free(all_bases)
    return total as i64
}

function main() -> i32 {
    printf("%lld\n", S(3800))
    return 0
}

Generated C

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
    while (flow_temp_head) {
        flow_temp_node* n = flow_temp_head;
        flow_temp_head = n->next;
        free(n);
    }
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
    flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
    if (!node) return NULL;
    node->next = flow_temp_head;
    flow_temp_head = node;
    if (!flow_temp_atexit_set) {
        flow_temp_atexit_set = 1;
        atexit(flow_temp_free_all);
    }
    return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
    size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
    char* r = (char*)flow_temp_alloc(la + lb + 1);
    if (!r) return NULL;
    if (la) memcpy(r, a, la);
    if (lb) memcpy(r + la, b, lb);
    r[la + lb] = '\0';
    return r;
}

#define __flow_in_arr(arr, val) __extension__ ({ \
    int _found = 0; \
    size_t _n = sizeof(arr)/sizeof((arr)[0]); \
    for (size_t _i = 0; _i < _n; _i++) { \
        if ((arr)[_i] == (val)) { _found = 1; break; } \
    } _found; })

/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
    fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
    abort();
#if defined(__GNUC__) || defined(__clang__)
    __builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")

#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif

#include <math.h>

void* _ui_state = NULL;

static inline float i32_to_f32(int32_t v) { return (float)v; }

/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }

__int128 egcd_i128_i128_ptr_i128_ptr_i128(__int128 a0, __int128 b0, __int128* outx, __int128* outy);
__int128 modinv128_i128_i128(__int128 a0, __int128 m);
int64_t sieve_i64_ptr_i64(int64_t limit, int64_t* primes);
int64_t subset_sums128_ptr_i128_i64_i128_ptr_i128(__int128* terms, int64_t k, __int128 modv, __int128* out);
void sort_i128_ptr_i128_i64(__int128* a, int64_t n);
int64_t bisect_left128_ptr_i128_i64_i128(__int128* a, int64_t n, __int128 x);
__int128 min_B_difference_i64_ptr_i64_i64_i128_ptr_i128(int64_t p, int64_t* primes, int64_t pk, __int128 M, __int128* bases);
__int128 max_B_sum_i64_ptr_i64_i64_i128_ptr_i128(int64_t p, int64_t* primes, int64_t pk, __int128 M, __int128* bases);
int64_t q_for_p_i64_ptr_i64_i64(int64_t p, int64_t* primes, int64_t np);
int64_t S_i64(int64_t n);
int32_t main(void);



__int128 egcd_i128_i128_ptr_i128_ptr_i128(__int128 a0, __int128 b0, __int128* outx, __int128* outy) {
    __int128 a = a0;
    __int128 b = b0;
    __int128 x0 = 1;
    __int128 y0 = 0;
    __int128 x1 = 0;
    __int128 y1 = 1;
    while (b != 0) {
        __int128 q = FLOW_CHECKED_DIV((a), (b));
        __int128 na = b;
        b = (a - (q * b));
        a = na;
        __int128 nx = x1;
        x1 = (x0 - (q * x1));
        x0 = nx;
        __int128 ny = y1;
        y1 = (y0 - (q * y1));
        y0 = ny;
    }
    outx[0] = x0;
    outy[0] = y0;
    return a;
}

__int128 modinv128_i128_i128(__int128 a0, __int128 m) {
    __int128* xy = (__int128*)(calloc(2, 16));
    __int128 g = egcd_i128_i128_ptr_i128_ptr_i128(FLOW_CHECKED_MOD((a0), (m)), m, xy, (xy + 1));
    __int128 x = xy[0];
    free(xy);
    if (g != 1) {
        return 0;
    }
    __int128 r = FLOW_CHECKED_MOD((x), (m));
    if (r < 0) {
        r = (r + m);
    }
    return r;
}

int64_t sieve_i64_ptr_i64(int64_t limit, int64_t* primes) {
    int8_t* is_prime = (int8_t*)(calloc((limit + 1), 1));
    if (is_prime == NULL) {
        return 0;
    }
    int64_t i = 0;
    while (i <= limit) {
        is_prime[i] = 1;
        i = (i + 1);
    }
    is_prime[0] = 0;
    is_prime[1] = 0;
    i = 2;
    while ((i * i) <= limit) {
        if (is_prime[i] != 0) {
            int64_t j = (i * i);
            while (j <= limit) {
                is_prime[j] = 0;
                j = (j + i);
            }
        }
        i = (i + 1);
    }
    int64_t m = 0;
    i = 2;
    while (i <= limit) {
        if (is_prime[i] != 0) {
            primes[m] = i;
            m = (m + 1);
        }
        i = (i + 1);
    }
    free(is_prime);
    return m;
}

int64_t subset_sums128_ptr_i128_i64_i128_ptr_i128(__int128* terms, int64_t k, __int128 modv, __int128* out) {
    out[0] = 0;
    int64_t n = 1;
    int64_t t = 0;
    while (t < k) {
        __int128 term = terms[t];
        int64_t i = 0;
        int64_t old = n;
        while (i < old) {
            out[n] = FLOW_CHECKED_MOD(((out[i] + term)), (modv));
            n = (n + 1);
            i = (i + 1);
        }
        t = (t + 1);
    }
    return n;
}

void sort_i128_ptr_i128_i64(__int128* a, int64_t n) {
    int64_t i = 1;
    while (i < n) {
        __int128 key = a[i];
        int64_t j = (i - 1);
        while ((j >= 0 && a[j] > key)) {
            a[(j + 1)] = a[j];
            j = (j - 1);
        }
        a[(j + 1)] = key;
        i = (i + 1);
    }
}

int64_t bisect_left128_ptr_i128_i64_i128(__int128* a, int64_t n, __int128 x) {
    int64_t lo = 0;
    int64_t hi = n;
    while (lo < hi) {
        int64_t mid = FLOW_CHECKED_DIV(((lo + hi)), (2));
        if (a[mid] < x) {
            lo = (mid + 1);
        } else {
            hi = mid;
        }
    }
    return lo;
}

__int128 min_B_difference_i64_ptr_i64_i64_i128_ptr_i128(int64_t p, int64_t* primes, int64_t pk, __int128 M, __int128* bases) {
    if (pk == 0) {
        return 1;
    }
    __int128* terms = (__int128*)(calloc(pk, 16));
    int64_t i = 0;
    while (i < pk) {
        __int128 r = ((__int128)(primes[i]));
        __int128 negp = FLOW_CHECKED_MOD(((-((__int128)(p)))), (r));
        if (negp < 0) {
            negp = (negp + r);
        }
        terms[i] = FLOW_CHECKED_MOD(((negp * bases[i])), (M));
        i = (i + 1);
    }
    int64_t mid = FLOW_CHECKED_DIV((pk), (2));
    __int128* L = (__int128*)(calloc(FLOW_CHECKED_SHL((1), (mid)), 16));
    __int128* R = (__int128*)(calloc(FLOW_CHECKED_SHL((1), ((pk - mid))), 16));
    int64_t nL = subset_sums128_ptr_i128_i64_i128_ptr_i128(terms, mid, M, L);
    __int128* termsR = (__int128*)(calloc((pk - mid), 16));
    i = 0;
    while (i < (pk - mid)) {
        termsR[i] = terms[(mid + i)];
        i = (i + 1);
    }
    int64_t nR = subset_sums128_ptr_i128_i64_i128_ptr_i128(termsR, (pk - mid), M, R);
    free(termsR);
    sort_i128_ptr_i128_i64(R, nR);
    __int128 best = M;
    __int128 p128 = ((__int128)(p));
    i = 0;
    while (i < nL) {
        __int128 x = L[i];
        if ((x != 0 && FLOW_CHECKED_MOD((x), (p128)) != 0)) {
            if (x < best) {
                best = x;
            }
        }
        i = (i + 1);
    }
    i = 0;
    while (i < nR) {
        __int128 x = R[i];
        if ((x != 0 && FLOW_CHECKED_MOD((x), (p128)) != 0)) {
            if (x < best) {
                best = x;
            }
        }
        i = (i + 1);
    }
    i = 0;
    while (i < nL) {
        __int128 l = L[i];
        __int128 target = (M - l);
        int64_t j = bisect_left128_ptr_i128_i64_i128(R, nR, target);
        while (j < nR) {
            __int128 s = (l + R[j]);
            if (s == M) {
                j = (j + 1);
            } else {
                if (s < M) {
                    break;
                }
                __int128 res = (s - M);
                if (res >= best) {
                    break;
                }
                if (FLOW_CHECKED_MOD((res), (p128)) != 0) {
                    best = res;
                    break;
                }
                j = (j + 1);
            }
        }
        i = (i + 1);
    }
    free(terms);
    free(L);
    free(R);
    return best;
}

__int128 max_B_sum_i64_ptr_i64_i64_i128_ptr_i128(int64_t p, int64_t* primes, int64_t pk, __int128 M, __int128* bases) {
    __int128 limit = ((__int128)(FLOW_CHECKED_DIV((p), (2))));
    if (pk == 0) {
        return limit;
    }
    __int128 Amax = (((__int128)(p)) - limit);
    if (M > (Amax * limit)) {
        return (-1);
    }
    __int128* terms = (__int128*)(calloc(pk, 16));
    int64_t i = 0;
    while (i < pk) {
        __int128 r = ((__int128)(primes[i]));
        terms[i] = FLOW_CHECKED_MOD(((FLOW_CHECKED_MOD((((__int128)(p))), (r)) * bases[i])), (M));
        i = (i + 1);
    }
    __int128* residues = (__int128*)(calloc(FLOW_CHECKED_SHL((1), (pk)), 16));
    int64_t nr = subset_sums128_ptr_i128_i64_i128_ptr_i128(terms, pk, M, residues);
    __int128 bestB = 0;
    i = 0;
    while (i < nr) {
        __int128 b0 = residues[i];
        if (b0 == 0) {
            if (M <= limit) {
                __int128 B = (FLOW_CHECKED_DIV((limit), (M)) * M);
                if (B > bestB) {
                    bestB = B;
                }
            }
        } else {
            if (b0 <= limit) {
                __int128 B = (b0 + (FLOW_CHECKED_DIV(((limit - b0)), (M)) * M));
                if (B > bestB) {
                    bestB = B;
                }
            }
        }
        i = (i + 1);
    }
    free(terms);
    free(residues);
    if (bestB == 0) {
        return (-1);
    }
    return bestB;
}

int64_t q_for_p_i64_ptr_i64_i64(int64_t p, int64_t* primes, int64_t np) {
    int64_t i = 0;
    while (i < np) {
        int64_t q = primes[i];
        if ((q * q) > p) {
            return q;
        }
        i = (i + 1);
    }
    return 0;
}

int64_t S_i64(int64_t n) {
    int64_t* primes = (int64_t*)(calloc(10000, 8));
    int64_t np = sieve_i64_ptr_i64((n + 200), primes);
    int64_t max_q = 0;
    int64_t i = 0;
    while (i < np) {
        int64_t p = primes[i];
        if (p < n) {
            int64_t q = q_for_p_i64_ptr_i64_i64(p, primes, np);
            if (q > max_q) {
                max_q = q;
            }
        }
        i = (i + 1);
    }
    int64_t nq = 0;
    i = 0;
    while (i < np) {
        if (primes[i] <= max_q) {
            nq = (nq + 1);
        }
        i = (i + 1);
    }
    __int128* Ms = (__int128*)(calloc(nq, 16));
    int64_t* base_offs = (int64_t*)(calloc(nq, 8));
    int64_t* base_lens = (int64_t*)(calloc(nq, 8));
    __int128* all_bases = (__int128*)(calloc(((nq * nq) + 8), 16));
    int64_t bcap = 0;
    i = 0;
    while (i < nq) {
        __int128 M = 1;
        int64_t j = 0;
        while (j < i) {
            M = (M * ((__int128)(primes[j])));
            j = (j + 1);
        }
        Ms[i] = M;
        base_offs[i] = bcap;
        base_lens[i] = i;
        j = 0;
        while (j < i) {
            __int128 r = ((__int128)(primes[j]));
            __int128 Mr = FLOW_CHECKED_DIV((M), (r));
            __int128 inv = modinv128_i128_i128(FLOW_CHECKED_MOD((Mr), (r)), r);
            all_bases[bcap] = FLOW_CHECKED_MOD(((Mr * inv)), (M));
            bcap = (bcap + 1);
            j = (j + 1);
        }
        i = (i + 1);
    }
    __int128 total = 0;
    i = 0;
    while (i < np) {
        int64_t p = primes[i];
        if (p < n) {
            int64_t q = q_for_p_i64_ptr_i64_i64(p, primes, np);
            int64_t qidx = 0;
            while (primes[qidx] != q) {
                qidx = (qidx + 1);
            }
            __int128 M = Ms[qidx];
            int64_t pk = base_lens[qidx];
            __int128* bases = (__int128*)(calloc((pk + 1), 16));
            int64_t j = 0;
            while (j < pk) {
                bases[j] = all_bases[(base_offs[qidx] + j)];
                j = (j + 1);
            }
            __int128 Adiff = (((__int128)(p)) + min_B_difference_i64_ptr_i64_i64_i128_ptr_i128(p, primes, pk, M, bases));
            __int128 Bsum = max_B_sum_i64_ptr_i64_i64_i128_ptr_i128(p, primes, pk, M, bases);
            if (Bsum < 0) {
                total = (total + Adiff);
            } else {
                __int128 Asum = (((__int128)(p)) - Bsum);
                if (Asum < Adiff) {
                    total = (total + Asum);
                } else {
                    total = (total + Adiff);
                }
            }
            free(bases);
        }
        i = (i + 1);
    }
    free(primes);
    free(Ms);
    free(base_offs);
    free(base_lens);
    free(all_bases);
    return ((int64_t)(total));
}

int32_t main(void) {
    printf("%lld\n", S_i64(3800));
    return 0;
}

Generated MLIR

module {
  llvm.func @printf(!llvm.ptr, ...) -> i32
  llvm.mlir.global internal constant @str_0("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
  func.func private @calloc(i64, i64) -> !llvm.ptr
  func.func private @free(!llvm.ptr) -> ()
  func.func @egcd(%arg0: i128, %arg1: i128, %arg2: !llvm.ptr, %arg3: !llvm.ptr) -> i128 {
    %0 = llvm.mlir.constant(1 : i64) : i64
    %1 = llvm.alloca %0 x i128 : (i64) -> !llvm.ptr
    llvm.store %arg0, %1 : i128, !llvm.ptr
    %2 = llvm.mlir.constant(1 : i64) : i64
    %3 = llvm.alloca %2 x i128 : (i64) -> !llvm.ptr
    llvm.store %arg1, %3 : i128, !llvm.ptr
    %4 = arith.constant 1 : i32
    %5 = arith.extsi %4 : i32 to i128
    %6 = llvm.mlir.constant(1 : i64) : i64
    %7 = llvm.alloca %6 x i128 : (i64) -> !llvm.ptr
    llvm.store %5, %7 : i128, !llvm.ptr
    %8 = arith.constant 0 : i32
    %9 = arith.extsi %8 : i32 to i128
    %10 = llvm.mlir.constant(1 : i64) : i64
    %11 = llvm.alloca %10 x i128 : (i64) -> !llvm.ptr
    llvm.store %9, %11 : i128, !llvm.ptr
    %12 = arith.constant 0 : i32
    %13 = arith.extsi %12 : i32 to i128
    %14 = llvm.mlir.constant(1 : i64) : i64
    %15 = llvm.alloca %14 x i128 : (i64) -> !llvm.ptr
    llvm.store %13, %15 : i128, !llvm.ptr
    %16 = arith.constant 1 : i32
    %17 = arith.extsi %16 : i32 to i128
    %18 = llvm.mlir.constant(1 : i64) : i64
    %19 = llvm.alloca %18 x i128 : (i64) -> !llvm.ptr
    llvm.store %17, %19 : i128, !llvm.ptr
    cf.br ^bb0
    ^bb0:
    %20 = llvm.load %3 : !llvm.ptr -> i128
    %21 = arith.constant 0 : i32
    %23 = arith.trunci %20 : i128 to i64
    %24 = arith.extsi %21 : i32 to i64
    %22 = arith.cmpi ne, %23, %24 : i64
    cf.cond_br %22, ^bb1, ^bb2
    ^bb1:
      %25 = llvm.load %1 : !llvm.ptr -> i128
      %26 = llvm.load %3 : !llvm.ptr -> i128
      %28 = arith.trunci %25 : i128 to i64
      %29 = arith.trunci %26 : i128 to i64
      %27 = arith.divsi %28, %29 : i64
      %30 = arith.extsi %27 : i64 to i128
      %31 = llvm.load %3 : !llvm.ptr -> i128
      %32 = llvm.load %1 : !llvm.ptr -> i128
      %33 = llvm.load %3 : !llvm.ptr -> i128
      %35 = arith.trunci %30 : i128 to i64
      %36 = arith.trunci %33 : i128 to i64
      %34 = arith.muli %35, %36 : i64
      %38 = arith.trunci %32 : i128 to i64
      %37 = arith.subi %38, %34 : i64
      %39 = arith.extsi %37 : i64 to i128
      llvm.store %39, %3 : i128, !llvm.ptr
      llvm.store %31, %1 : i128, !llvm.ptr
      %40 = llvm.load %15 : !llvm.ptr -> i128
      %41 = llvm.load %7 : !llvm.ptr -> i128
      %42 = llvm.load %15 : !llvm.ptr -> i128
      %44 = arith.trunci %30 : i128 to i64
      %45 = arith.trunci %42 : i128 to i64
      %43 = arith.muli %44, %45 : i64
      %47 = arith.trunci %41 : i128 to i64
      %46 = arith.subi %47, %43 : i64
      %48 = arith.extsi %46 : i64 to i128
      llvm.store %48, %15 : i128, !llvm.ptr
      llvm.store %40, %7 : i128, !llvm.ptr
      %49 = llvm.load %19 : !llvm.ptr -> i128
      %50 = llvm.load %11 : !llvm.ptr -> i128
      %51 = llvm.load %19 : !llvm.ptr -> i128
      %53 = arith.trunci %30 : i128 to i64
      %54 = arith.trunci %51 : i128 to i64
      %52 = arith.muli %53, %54 : i64
      %56 = arith.trunci %50 : i128 to i64
      %55 = arith.subi %56, %52 : i64
      %57 = arith.extsi %55 : i64 to i128
      llvm.store %57, %19 : i128, !llvm.ptr
      llvm.store %49, %11 : i128, !llvm.ptr
      cf.br ^bb0
    ^bb2:
    %58 = llvm.load %7 : !llvm.ptr -> i128
    %59 = arith.constant 0 : i32
    %60 = arith.extsi %59 : i32 to i64
    %61 = llvm.getelementptr %arg2[%60] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    llvm.store %58, %61 : i128, !llvm.ptr
    %62 = llvm.load %11 : !llvm.ptr -> i128
    %63 = arith.constant 0 : i32
    %64 = arith.extsi %63 : i32 to i64
    %65 = llvm.getelementptr %arg3[%64] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    llvm.store %62, %65 : i128, !llvm.ptr
    %66 = llvm.load %1 : !llvm.ptr -> i128
    func.return %66 : i128
  }
  func.func @modinv128(%arg0: i128, %arg1: i128) -> i128 {
    %68 = arith.constant 2 : i32
    %69 = arith.constant 16 : i32
    %70 = arith.extsi %68 : i32 to i64
    %71 = arith.extsi %69 : i32 to i64
    %67 = func.call @calloc(%70, %71) : (i64, i64) -> !llvm.ptr
    %74 = arith.trunci %arg0 : i128 to i64
    %75 = arith.trunci %arg1 : i128 to i64
    %73 = arith.remsi %74, %75 : i64
    # String concatenation: !llvm.ptr + i32
    %77 = arith.extsi %73 : i64 to i128
    %72 = func.call @egcd(%77, %arg1, %67, %76) : (i128, i128, !llvm.ptr, !llvm.ptr) -> i128
    %79 = arith.constant 0 : i32
    %80 = arith.extsi %79 : i32 to i64
    %81 = llvm.getelementptr %67[%80] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    %78 = llvm.load %81 : !llvm.ptr -> i128
    func.call @free(%67) : (!llvm.ptr) -> ()
    %83 = arith.constant 1 : i32
    %85 = arith.trunci %72 : i128 to i64
    %86 = arith.extsi %83 : i32 to i64
    %84 = arith.cmpi ne, %85, %86 : i64
    cf.cond_br %84, ^bb3, ^bb4
    ^bb3:
      %87 = arith.constant 0 : i32
      %88 = arith.extsi %87 : i32 to i128
      func.return %88 : i128
    ^bb4:
      cf.br ^bb5
    ^bb5:
    %90 = arith.trunci %78 : i128 to i64
    %91 = arith.trunci %arg1 : i128 to i64
    %89 = arith.remsi %90, %91 : i64
    %92 = arith.extsi %89 : i64 to i128
    %93 = llvm.mlir.constant(1 : i64) : i64
    %94 = llvm.alloca %93 x i128 : (i64) -> !llvm.ptr
    llvm.store %92, %94 : i128, !llvm.ptr
    %95 = llvm.load %94 : !llvm.ptr -> i128
    %96 = arith.constant 0 : i32
    %98 = arith.trunci %95 : i128 to i64
    %99 = arith.extsi %96 : i32 to i64
    %97 = arith.cmpi slt, %98, %99 : i64
    cf.cond_br %97, ^bb6, ^bb7
    ^bb6:
      %100 = llvm.load %94 : !llvm.ptr -> i128
      %102 = arith.trunci %100 : i128 to i64
      %103 = arith.trunci %arg1 : i128 to i64
      %101 = arith.addi %102, %103 : i64
      %104 = arith.extsi %101 : i64 to i128
      llvm.store %104, %94 : i128, !llvm.ptr
      cf.br ^bb8
    ^bb7:
      cf.br ^bb8
    ^bb8:
    %105 = llvm.load %94 : !llvm.ptr -> i128
    func.return %105 : i128
  }
  func.func @sieve(%arg0: i64, %arg1: !llvm.ptr) -> i64 {
    %107 = arith.constant 1 : i32
    %109 = arith.extsi %107 : i32 to i64
    %108 = arith.addi %arg0, %109 : i64
    %110 = arith.constant 1 : i32
    %111 = arith.extsi %110 : i32 to i64
    %106 = func.call @calloc(%108, %111) : (i64, i64) -> !llvm.ptr
    %112 = llvm.mlir.zero : !llvm.ptr
    %113 = llvm.icmp "eq" %106, %112 : !llvm.ptr
    cf.cond_br %113, ^bb9, ^bb10
    ^bb9:
      %114 = arith.constant 0 : i32
      %115 = arith.extsi %114 : i32 to i64
      func.return %115 : i64
    ^bb10:
      cf.br ^bb11
    ^bb11:
    %116 = arith.constant 0 : i32
    %117 = arith.extsi %116 : i32 to i64
    %118 = llvm.mlir.constant(1 : i64) : i64
    %119 = llvm.alloca %118 x i64 : (i64) -> !llvm.ptr
    llvm.store %117, %119 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %120 = llvm.load %119 : !llvm.ptr -> i64
    %121 = arith.cmpi sle, %120, %arg0 : i64
    cf.cond_br %121, ^bb13, ^bb14
    ^bb13:
      %122 = arith.constant 1 : i32
      %123 = llvm.load %119 : !llvm.ptr -> i64
      %124 = arith.trunci %122 : i32 to i8
      %125 = llvm.getelementptr %106[%123] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      llvm.store %124, %125 : i8, !llvm.ptr
      %126 = llvm.load %119 : !llvm.ptr -> i64
      %127 = arith.constant 1 : i32
      %129 = arith.extsi %127 : i32 to i64
      %128 = arith.addi %126, %129 : i64
      llvm.store %128, %119 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %130 = arith.constant 0 : i32
    %131 = arith.constant 0 : i32
    %132 = arith.trunci %130 : i32 to i8
    %133 = arith.extsi %131 : i32 to i64
    %134 = llvm.getelementptr %106[%133] : (!llvm.ptr, i64) -> !llvm.ptr, i8
    llvm.store %132, %134 : i8, !llvm.ptr
    %135 = arith.constant 0 : i32
    %136 = arith.constant 1 : i32
    %137 = arith.trunci %135 : i32 to i8
    %138 = arith.extsi %136 : i32 to i64
    %139 = llvm.getelementptr %106[%138] : (!llvm.ptr, i64) -> !llvm.ptr, i8
    llvm.store %137, %139 : i8, !llvm.ptr
    %140 = arith.constant 2 : i32
    %141 = arith.extsi %140 : i32 to i64
    llvm.store %141, %119 : i64, !llvm.ptr
    cf.br ^bb15
    ^bb15:
    %142 = llvm.load %119 : !llvm.ptr -> i64
    %143 = llvm.load %119 : !llvm.ptr -> i64
    %144 = arith.muli %142, %143 : i64
    %145 = arith.cmpi sle, %144, %arg0 : i64
    cf.cond_br %145, ^bb16, ^bb17
    ^bb16:
      %147 = llvm.load %119 : !llvm.ptr -> i64
      %148 = llvm.getelementptr %106[%147] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      %146 = llvm.load %148 : !llvm.ptr -> i8
      %149 = arith.constant 0 : i32
      %151 = arith.extsi %146 : i8 to i32
      %150 = arith.cmpi ne, %151, %149 : i32
      cf.cond_br %150, ^bb18, ^bb19
      ^bb18:
        %152 = llvm.load %119 : !llvm.ptr -> i64
        %153 = llvm.load %119 : !llvm.ptr -> i64
        %154 = arith.muli %152, %153 : i64
        %155 = llvm.mlir.constant(1 : i64) : i64
        %156 = llvm.alloca %155 x i64 : (i64) -> !llvm.ptr
        llvm.store %154, %156 : i64, !llvm.ptr
        cf.br ^bb21
        ^bb21:
        %157 = llvm.load %156 : !llvm.ptr -> i64
        %158 = arith.cmpi sle, %157, %arg0 : i64
        cf.cond_br %158, ^bb22, ^bb23
        ^bb22:
          %159 = arith.constant 0 : i32
          %160 = llvm.load %156 : !llvm.ptr -> i64
          %161 = arith.trunci %159 : i32 to i8
          %162 = llvm.getelementptr %106[%160] : (!llvm.ptr, i64) -> !llvm.ptr, i8
          llvm.store %161, %162 : i8, !llvm.ptr
          %163 = llvm.load %156 : !llvm.ptr -> i64
          %164 = llvm.load %119 : !llvm.ptr -> i64
          %165 = arith.addi %163, %164 : i64
          llvm.store %165, %156 : i64, !llvm.ptr
          cf.br ^bb21
        ^bb23:
        cf.br ^bb20
      ^bb19:
        cf.br ^bb20
      ^bb20:
      %166 = llvm.load %119 : !llvm.ptr -> i64
      %167 = arith.constant 1 : i32
      %169 = arith.extsi %167 : i32 to i64
      %168 = arith.addi %166, %169 : i64
      llvm.store %168, %119 : i64, !llvm.ptr
      cf.br ^bb15
    ^bb17:
    %170 = arith.constant 0 : i32
    %171 = arith.extsi %170 : i32 to i64
    %172 = llvm.mlir.constant(1 : i64) : i64
    %173 = llvm.alloca %172 x i64 : (i64) -> !llvm.ptr
    llvm.store %171, %173 : i64, !llvm.ptr
    %174 = arith.constant 2 : i32
    %175 = arith.extsi %174 : i32 to i64
    llvm.store %175, %119 : i64, !llvm.ptr
    cf.br ^bb24
    ^bb24:
    %176 = llvm.load %119 : !llvm.ptr -> i64
    %177 = arith.cmpi sle, %176, %arg0 : i64
    cf.cond_br %177, ^bb25, ^bb26
    ^bb25:
      %179 = llvm.load %119 : !llvm.ptr -> i64
      %180 = llvm.getelementptr %106[%179] : (!llvm.ptr, i64) -> !llvm.ptr, i8
      %178 = llvm.load %180 : !llvm.ptr -> i8
      %181 = arith.constant 0 : i32
      %183 = arith.extsi %178 : i8 to i32
      %182 = arith.cmpi ne, %183, %181 : i32
      cf.cond_br %182, ^bb27, ^bb28
      ^bb27:
        %184 = llvm.load %119 : !llvm.ptr -> i64
        %185 = llvm.load %173 : !llvm.ptr -> i64
        %186 = llvm.getelementptr %arg1[%185] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        llvm.store %184, %186 : i64, !llvm.ptr
        %187 = llvm.load %173 : !llvm.ptr -> i64
        %188 = arith.constant 1 : i32
        %190 = arith.extsi %188 : i32 to i64
        %189 = arith.addi %187, %190 : i64
        llvm.store %189, %173 : i64, !llvm.ptr
        cf.br ^bb29
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %191 = llvm.load %119 : !llvm.ptr -> i64
      %192 = arith.constant 1 : i32
      %194 = arith.extsi %192 : i32 to i64
      %193 = arith.addi %191, %194 : i64
      llvm.store %193, %119 : i64, !llvm.ptr
      cf.br ^bb24
    ^bb26:
    func.call @free(%106) : (!llvm.ptr) -> ()
    %196 = llvm.load %173 : !llvm.ptr -> i64
    func.return %196 : i64
  }
  func.func @subset_sums128(%arg0: !llvm.ptr, %arg1: i64, %arg2: i128, %arg3: !llvm.ptr) -> i64 {
    %197 = arith.constant 0 : i32
    %198 = arith.constant 0 : i32
    %199 = arith.extsi %197 : i32 to i128
    %200 = arith.extsi %198 : i32 to i64
    %201 = llvm.getelementptr %arg3[%200] : (!llvm.ptr, i64) -> !llvm.ptr, i128
    llvm.store %199, %201 : i128, !llvm.ptr
    %202 = arith.constant 1 : i32
    %203 = arith.extsi %202 : i32 to i64
    %204 = llvm.mlir.constant(1 : i64) : i64
    %205 = llvm.alloca %204 x i64 : (i64) -> !llvm.ptr
    llvm.store %203, %205 : i64, !llvm.ptr
    %206 = arith.constant 0 : i32
    %207 = arith.extsi %206 : i32 to i64
    %208 = llvm.mlir.constant(1 : i64) : i64
    %209 = llvm.alloca %208 x i64 : (i64) -> !llvm.ptr
    llvm.store %207, %209 : i64, !llvm.ptr
    cf.br ^bb30
    ^bb30:
    %210 = llvm.load %209 : !llvm.ptr -> i64
    %211 = arith.cmpi slt, %210, %arg1 : i64
    cf.cond_br %211, ^bb31, ^bb32
    ^bb31:
      %213 = llvm.load %209 : !llvm.ptr -> i64
      %214 = llvm.getelementptr %arg0[%213] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %212 = llvm.load %214 : !llvm.ptr -> i128
      %215 = arith.constant 0 : i32
      %216 = arith.extsi %215 : i32 to i64
      %217 = llvm.mlir.constant(1 : i64) : i64
      %218 = llvm.alloca %217 x i64 : (i64) -> !llvm.ptr
      llvm.store %216, %218 : i64, !llvm.ptr
      %219 = llvm.load %205 : !llvm.ptr -> i64
      cf.br ^bb33
      ^bb33:
      %220 = llvm.load %218 : !llvm.ptr -> i64
      %221 = arith.cmpi slt, %220, %219 : i64
      cf.cond_br %221, ^bb34, ^bb35
      ^bb34:
        %223 = llvm.load %218 : !llvm.ptr -> i64
        %224 = llvm.getelementptr %arg3[%223] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        %222 = llvm.load %224 : !llvm.ptr -> i128
        %226 = arith.trunci %222 : i128 to i64
        %227 = arith.trunci %212 : i128 to i64
        %225 = arith.addi %226, %227 : i64
        %229 = arith.trunci %arg2 : i128 to i64
        %228 = arith.remsi %225, %229 : i64
        %230 = llvm.load %205 : !llvm.ptr -> i64
        %231 = arith.extsi %228 : i64 to i128
        %232 = llvm.getelementptr %arg3[%230] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %231, %232 : i128, !llvm.ptr
        %233 = llvm.load %205 : !llvm.ptr -> i64
        %234 = arith.constant 1 : i32
        %236 = arith.extsi %234 : i32 to i64
        %235 = arith.addi %233, %236 : i64
        llvm.store %235, %205 : i64, !llvm.ptr
        %237 = llvm.load %218 : !llvm.ptr -> i64
        %238 = arith.constant 1 : i32
        %240 = arith.extsi %238 : i32 to i64
        %239 = arith.addi %237, %240 : i64
        llvm.store %239, %218 : i64, !llvm.ptr
        cf.br ^bb33
      ^bb35:
      %241 = llvm.load %209 : !llvm.ptr -> i64
      %242 = arith.constant 1 : i32
      %244 = arith.extsi %242 : i32 to i64
      %243 = arith.addi %241, %244 : i64
      llvm.store %243, %209 : i64, !llvm.ptr
      cf.br ^bb30
    ^bb32:
    %245 = llvm.load %205 : !llvm.ptr -> i64
    func.return %245 : i64
  }
  func.func @sort_i128(%arg0: !llvm.ptr, %arg1: i64) -> () {
    %246 = arith.constant 1 : i32
    %247 = arith.extsi %246 : i32 to i64
    %248 = llvm.mlir.constant(1 : i64) : i64
    %249 = llvm.alloca %248 x i64 : (i64) -> !llvm.ptr
    llvm.store %247, %249 : i64, !llvm.ptr
    cf.br ^bb36
    ^bb36:
    %250 = llvm.load %249 : !llvm.ptr -> i64
    %251 = arith.cmpi slt, %250, %arg1 : i64
    cf.cond_br %251, ^bb37, ^bb38
    ^bb37:
      %253 = llvm.load %249 : !llvm.ptr -> i64
      %254 = llvm.getelementptr %arg0[%253] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %252 = llvm.load %254 : !llvm.ptr -> i128
      %255 = llvm.load %249 : !llvm.ptr -> i64
      %256 = arith.constant 1 : i32
      %258 = arith.extsi %256 : i32 to i64
      %257 = arith.subi %255, %258 : i64
      %259 = llvm.mlir.constant(1 : i64) : i64
      %260 = llvm.alloca %259 x i64 : (i64) -> !llvm.ptr
      llvm.store %257, %260 : i64, !llvm.ptr
      cf.br ^bb39
      ^bb39:
      %261 = llvm.load %260 : !llvm.ptr -> i64
      %262 = arith.constant 0 : i32
      %264 = arith.extsi %262 : i32 to i64
      %263 = arith.cmpi sge, %261, %264 : i64
      %265 = scf.if %263 -> (i1) {
        %267 = llvm.load %260 : !llvm.ptr -> i64
        %268 = llvm.getelementptr %arg0[%267] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        %266 = llvm.load %268 : !llvm.ptr -> i128
        %270 = arith.trunci %266 : i128 to i64
        %271 = arith.trunci %252 : i128 to i64
        %269 = arith.cmpi sgt, %270, %271 : i64
        scf.yield %269 : i1
      } else {
        %272 = arith.constant false
        scf.yield %272 : i1
      }
      cf.cond_br %265, ^bb40, ^bb41
      ^bb40:
        %274 = llvm.load %260 : !llvm.ptr -> i64
        %275 = llvm.getelementptr %arg0[%274] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        %273 = llvm.load %275 : !llvm.ptr -> i128
        %276 = llvm.load %260 : !llvm.ptr -> i64
        %277 = arith.constant 1 : i32
        %279 = arith.extsi %277 : i32 to i64
        %278 = arith.addi %276, %279 : i64
        %280 = llvm.getelementptr %arg0[%278] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %273, %280 : i128, !llvm.ptr
        %281 = llvm.load %260 : !llvm.ptr -> i64
        %282 = arith.constant 1 : i32
        %284 = arith.extsi %282 : i32 to i64
        %283 = arith.subi %281, %284 : i64
        llvm.store %283, %260 : i64, !llvm.ptr
        cf.br ^bb39
      ^bb41:
      %285 = llvm.load %260 : !llvm.ptr -> i64
      %286 = arith.constant 1 : i32
      %288 = arith.extsi %286 : i32 to i64
      %287 = arith.addi %285, %288 : i64
      %289 = llvm.getelementptr %arg0[%287] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %252, %289 : i128, !llvm.ptr
      %290 = llvm.load %249 : !llvm.ptr -> i64
      %291 = arith.constant 1 : i32
      %293 = arith.extsi %291 : i32 to i64
      %292 = arith.addi %290, %293 : i64
      llvm.store %292, %249 : i64, !llvm.ptr
      cf.br ^bb36
    ^bb38:
    func.return
  }
  func.func @bisect_left128(%arg0: !llvm.ptr, %arg1: i64, %arg2: i128) -> i64 {
    %294 = arith.constant 0 : i32
    %295 = arith.extsi %294 : i32 to i64
    %296 = llvm.mlir.constant(1 : i64) : i64
    %297 = llvm.alloca %296 x i64 : (i64) -> !llvm.ptr
    llvm.store %295, %297 : i64, !llvm.ptr
    %298 = llvm.mlir.constant(1 : i64) : i64
    %299 = llvm.alloca %298 x i64 : (i64) -> !llvm.ptr
    llvm.store %arg1, %299 : i64, !llvm.ptr
    cf.br ^bb42
    ^bb42:
    %300 = llvm.load %297 : !llvm.ptr -> i64
    %301 = llvm.load %299 : !llvm.ptr -> i64
    %302 = arith.cmpi slt, %300, %301 : i64
    cf.cond_br %302, ^bb43, ^bb44
    ^bb43:
      %303 = llvm.load %297 : !llvm.ptr -> i64
      %304 = llvm.load %299 : !llvm.ptr -> i64
      %305 = arith.addi %303, %304 : i64
      %306 = arith.constant 2 : i32
      %308 = arith.extsi %306 : i32 to i64
      %307 = arith.divsi %305, %308 : i64
      %310 = llvm.getelementptr %arg0[%307] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %309 = llvm.load %310 : !llvm.ptr -> i128
      %312 = arith.trunci %309 : i128 to i64
      %313 = arith.trunci %arg2 : i128 to i64
      %311 = arith.cmpi slt, %312, %313 : i64
      cf.cond_br %311, ^bb45, ^bb46
      ^bb45:
        %314 = arith.constant 1 : i32
        %316 = arith.extsi %314 : i32 to i64
        %315 = arith.addi %307, %316 : i64
        llvm.store %315, %297 : i64, !llvm.ptr
        cf.br ^bb47
      ^bb46:
        llvm.store %307, %299 : i64, !llvm.ptr
        cf.br ^bb47
      ^bb47:
      cf.br ^bb42
    ^bb44:
    %317 = llvm.load %297 : !llvm.ptr -> i64
    func.return %317 : i64
  }
  func.func @min_B_difference(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64, %arg3: i128, %arg4: !llvm.ptr) -> i128 {
    %318 = arith.constant 0 : i32
    %320 = arith.extsi %318 : i32 to i64
    %319 = arith.cmpi eq, %arg2, %320 : i64
    cf.cond_br %319, ^bb48, ^bb49
    ^bb48:
      %321 = arith.constant 1 : i32
      %322 = arith.extsi %321 : i32 to i128
      func.return %322 : i128
    ^bb49:
      cf.br ^bb50
    ^bb50:
    %324 = arith.constant 16 : i32
    %325 = arith.extsi %324 : i32 to i64
    %323 = func.call @calloc(%arg2, %325) : (i64, i64) -> !llvm.ptr
    %326 = arith.constant 0 : i32
    %327 = arith.extsi %326 : i32 to i64
    %328 = llvm.mlir.constant(1 : i64) : i64
    %329 = llvm.alloca %328 x i64 : (i64) -> !llvm.ptr
    llvm.store %327, %329 : i64, !llvm.ptr
    cf.br ^bb51
    ^bb51:
    %330 = llvm.load %329 : !llvm.ptr -> i64
    %331 = arith.cmpi slt, %330, %arg2 : i64
    cf.cond_br %331, ^bb52, ^bb53
    ^bb52:
      %333 = llvm.load %329 : !llvm.ptr -> i64
      %334 = llvm.getelementptr %arg1[%333] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %332 = llvm.load %334 : !llvm.ptr -> i64
      %335 = arith.extsi %332 : i64 to i128
      %336 = arith.extsi %arg0 : i64 to i128
      %338 = arith.constant 0 : i128
      %337 = arith.subi %338, %336 : i128
      %340 = arith.trunci %337 : i128 to i64
      %341 = arith.trunci %335 : i128 to i64
      %339 = arith.remsi %340, %341 : i64
      %342 = arith.extsi %339 : i64 to i128
      %343 = llvm.mlir.constant(1 : i64) : i64
      %344 = llvm.alloca %343 x i128 : (i64) -> !llvm.ptr
      llvm.store %342, %344 : i128, !llvm.ptr
      %345 = llvm.load %344 : !llvm.ptr -> i128
      %346 = arith.constant 0 : i32
      %348 = arith.trunci %345 : i128 to i64
      %349 = arith.extsi %346 : i32 to i64
      %347 = arith.cmpi slt, %348, %349 : i64
      cf.cond_br %347, ^bb54, ^bb55
      ^bb54:
        %350 = llvm.load %344 : !llvm.ptr -> i128
        %352 = arith.trunci %350 : i128 to i64
        %353 = arith.trunci %335 : i128 to i64
        %351 = arith.addi %352, %353 : i64
        %354 = arith.extsi %351 : i64 to i128
        llvm.store %354, %344 : i128, !llvm.ptr
        cf.br ^bb56
      ^bb55:
        cf.br ^bb56
      ^bb56:
      %355 = llvm.load %344 : !llvm.ptr -> i128
      %357 = llvm.load %329 : !llvm.ptr -> i64
      %358 = llvm.getelementptr %arg4[%357] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %356 = llvm.load %358 : !llvm.ptr -> i128
      %360 = arith.trunci %355 : i128 to i64
      %361 = arith.trunci %356 : i128 to i64
      %359 = arith.muli %360, %361 : i64
      %363 = arith.trunci %arg3 : i128 to i64
      %362 = arith.remsi %359, %363 : i64
      %364 = llvm.load %329 : !llvm.ptr -> i64
      %365 = arith.extsi %362 : i64 to i128
      %366 = llvm.getelementptr %323[%364] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %365, %366 : i128, !llvm.ptr
      %367 = llvm.load %329 : !llvm.ptr -> i64
      %368 = arith.constant 1 : i32
      %370 = arith.extsi %368 : i32 to i64
      %369 = arith.addi %367, %370 : i64
      llvm.store %369, %329 : i64, !llvm.ptr
      cf.br ^bb51
    ^bb53:
    %371 = arith.constant 2 : i32
    %373 = arith.extsi %371 : i32 to i64
    %372 = arith.divsi %arg2, %373 : i64
    %375 = arith.constant 1 : i32
    %377 = arith.extsi %375 : i32 to i64
    %376 = arith.shli %377, %372 : i64
    %378 = arith.constant 16 : i32
    %379 = arith.extsi %378 : i32 to i64
    %374 = func.call @calloc(%376, %379) : (i64, i64) -> !llvm.ptr
    %381 = arith.constant 1 : i32
    %382 = arith.subi %arg2, %372 : i64
    %384 = arith.extsi %381 : i32 to i64
    %383 = arith.shli %384, %382 : i64
    %385 = arith.constant 16 : i32
    %386 = arith.extsi %385 : i32 to i64
    %380 = func.call @calloc(%383, %386) : (i64, i64) -> !llvm.ptr
    %387 = func.call @subset_sums128(%323, %372, %arg3, %374) : (!llvm.ptr, i64, i128, !llvm.ptr) -> i64
    %389 = arith.subi %arg2, %372 : i64
    %390 = arith.constant 16 : i32
    %391 = arith.extsi %390 : i32 to i64
    %388 = func.call @calloc(%389, %391) : (i64, i64) -> !llvm.ptr
    %392 = arith.constant 0 : i32
    %393 = arith.extsi %392 : i32 to i64
    llvm.store %393, %329 : i64, !llvm.ptr
    cf.br ^bb57
    ^bb57:
    %394 = llvm.load %329 : !llvm.ptr -> i64
    %395 = arith.subi %arg2, %372 : i64
    %396 = arith.cmpi slt, %394, %395 : i64
    cf.cond_br %396, ^bb58, ^bb59
    ^bb58:
      %398 = llvm.load %329 : !llvm.ptr -> i64
      %399 = arith.addi %372, %398 : i64
      %400 = llvm.getelementptr %323[%399] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %397 = llvm.load %400 : !llvm.ptr -> i128
      %401 = llvm.load %329 : !llvm.ptr -> i64
      %402 = llvm.getelementptr %388[%401] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %397, %402 : i128, !llvm.ptr
      %403 = llvm.load %329 : !llvm.ptr -> i64
      %404 = arith.constant 1 : i32
      %406 = arith.extsi %404 : i32 to i64
      %405 = arith.addi %403, %406 : i64
      llvm.store %405, %329 : i64, !llvm.ptr
      cf.br ^bb57
    ^bb59:
    %408 = arith.subi %arg2, %372 : i64
    %407 = func.call @subset_sums128(%388, %408, %arg3, %380) : (!llvm.ptr, i64, i128, !llvm.ptr) -> i64
    func.call @free(%388) : (!llvm.ptr) -> ()
    func.call @sort_i128(%380, %407) : (!llvm.ptr, i64) -> ()
    %411 = llvm.mlir.constant(1 : i64) : i64
    %412 = llvm.alloca %411 x i128 : (i64) -> !llvm.ptr
    llvm.store %arg3, %412 : i128, !llvm.ptr
    %413 = arith.extsi %arg0 : i64 to i128
    %414 = arith.constant 0 : i32
    %415 = arith.extsi %414 : i32 to i64
    llvm.store %415, %329 : i64, !llvm.ptr
    cf.br ^bb60
    ^bb60:
    %416 = llvm.load %329 : !llvm.ptr -> i64
    %417 = arith.cmpi slt, %416, %387 : i64
    cf.cond_br %417, ^bb61, ^bb62
    ^bb61:
      %419 = llvm.load %329 : !llvm.ptr -> i64
      %420 = llvm.getelementptr %374[%419] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %418 = llvm.load %420 : !llvm.ptr -> i128
      %421 = arith.constant 0 : i32
      %423 = arith.trunci %418 : i128 to i64
      %424 = arith.extsi %421 : i32 to i64
      %422 = arith.cmpi ne, %423, %424 : i64
      %425 = scf.if %422 -> (i1) {
        %427 = arith.trunci %418 : i128 to i64
        %428 = arith.trunci %413 : i128 to i64
        %426 = arith.remsi %427, %428 : i64
        %429 = arith.constant 0 : i32
        %431 = arith.extsi %429 : i32 to i64
        %430 = arith.cmpi ne, %426, %431 : i64
        scf.yield %430 : i1
      } else {
        %432 = arith.constant false
        scf.yield %432 : i1
      }
      cf.cond_br %425, ^bb63, ^bb64
      ^bb63:
        %433 = llvm.load %412 : !llvm.ptr -> i128
        %435 = arith.trunci %418 : i128 to i64
        %436 = arith.trunci %433 : i128 to i64
        %434 = arith.cmpi slt, %435, %436 : i64
        cf.cond_br %434, ^bb66, ^bb67
        ^bb66:
          llvm.store %418, %412 : i128, !llvm.ptr
          cf.br ^bb68
        ^bb67:
          cf.br ^bb68
        ^bb68:
        cf.br ^bb65
      ^bb64:
        cf.br ^bb65
      ^bb65:
      %437 = llvm.load %329 : !llvm.ptr -> i64
      %438 = arith.constant 1 : i32
      %440 = arith.extsi %438 : i32 to i64
      %439 = arith.addi %437, %440 : i64
      llvm.store %439, %329 : i64, !llvm.ptr
      cf.br ^bb60
    ^bb62:
    %441 = arith.constant 0 : i32
    %442 = arith.extsi %441 : i32 to i64
    llvm.store %442, %329 : i64, !llvm.ptr
    cf.br ^bb69
    ^bb69:
    %443 = llvm.load %329 : !llvm.ptr -> i64
    %444 = arith.cmpi slt, %443, %407 : i64
    cf.cond_br %444, ^bb70, ^bb71
    ^bb70:
      %446 = llvm.load %329 : !llvm.ptr -> i64
      %447 = llvm.getelementptr %380[%446] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %445 = llvm.load %447 : !llvm.ptr -> i128
      %448 = arith.constant 0 : i32
      %450 = arith.trunci %445 : i128 to i64
      %451 = arith.extsi %448 : i32 to i64
      %449 = arith.cmpi ne, %450, %451 : i64
      %452 = scf.if %449 -> (i1) {
        %454 = arith.trunci %445 : i128 to i64
        %455 = arith.trunci %413 : i128 to i64
        %453 = arith.remsi %454, %455 : i64
        %456 = arith.constant 0 : i32
        %458 = arith.extsi %456 : i32 to i64
        %457 = arith.cmpi ne, %453, %458 : i64
        scf.yield %457 : i1
      } else {
        %459 = arith.constant false
        scf.yield %459 : i1
      }
      cf.cond_br %452, ^bb72, ^bb73
      ^bb72:
        %460 = llvm.load %412 : !llvm.ptr -> i128
        %462 = arith.trunci %445 : i128 to i64
        %463 = arith.trunci %460 : i128 to i64
        %461 = arith.cmpi slt, %462, %463 : i64
        cf.cond_br %461, ^bb75, ^bb76
        ^bb75:
          llvm.store %445, %412 : i128, !llvm.ptr
          cf.br ^bb77
        ^bb76:
          cf.br ^bb77
        ^bb77:
        cf.br ^bb74
      ^bb73:
        cf.br ^bb74
      ^bb74:
      %464 = llvm.load %329 : !llvm.ptr -> i64
      %465 = arith.constant 1 : i32
      %467 = arith.extsi %465 : i32 to i64
      %466 = arith.addi %464, %467 : i64
      llvm.store %466, %329 : i64, !llvm.ptr
      cf.br ^bb69
    ^bb71:
    %468 = arith.constant 0 : i32
    %469 = arith.extsi %468 : i32 to i64
    llvm.store %469, %329 : i64, !llvm.ptr
    cf.br ^bb78
    ^bb78:
    %470 = llvm.load %329 : !llvm.ptr -> i64
    %471 = arith.cmpi slt, %470, %387 : i64
    cf.cond_br %471, ^bb79, ^bb80
    ^bb79:
      %473 = llvm.load %329 : !llvm.ptr -> i64
      %474 = llvm.getelementptr %374[%473] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %472 = llvm.load %474 : !llvm.ptr -> i128
      %476 = arith.trunci %arg3 : i128 to i64
      %477 = arith.trunci %472 : i128 to i64
      %475 = arith.subi %476, %477 : i64
      %478 = arith.extsi %475 : i64 to i128
      %479 = func.call @bisect_left128(%380, %407, %478) : (!llvm.ptr, i64, i128) -> i64
      %480 = llvm.mlir.constant(1 : i64) : i64
      %481 = llvm.alloca %480 x i64 : (i64) -> !llvm.ptr
      llvm.store %479, %481 : i64, !llvm.ptr
      cf.br ^bb81
      ^bb81:
      %482 = llvm.load %481 : !llvm.ptr -> i64
      %483 = arith.cmpi slt, %482, %407 : i64
      cf.cond_br %483, ^bb82, ^bb83
      ^bb82:
        %485 = llvm.load %481 : !llvm.ptr -> i64
        %486 = llvm.getelementptr %380[%485] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        %484 = llvm.load %486 : !llvm.ptr -> i128
        %488 = arith.trunci %472 : i128 to i64
        %489 = arith.trunci %484 : i128 to i64
        %487 = arith.addi %488, %489 : i64
        %490 = arith.extsi %487 : i64 to i128
        %492 = arith.trunci %490 : i128 to i64
        %493 = arith.trunci %arg3 : i128 to i64
        %491 = arith.cmpi eq, %492, %493 : i64
        cf.cond_br %491, ^bb84, ^bb85
        ^bb84:
          %494 = llvm.load %481 : !llvm.ptr -> i64
          %495 = arith.constant 1 : i32
          %497 = arith.extsi %495 : i32 to i64
          %496 = arith.addi %494, %497 : i64
          llvm.store %496, %481 : i64, !llvm.ptr
          cf.br ^bb86
        ^bb85:
          %499 = arith.trunci %490 : i128 to i64
          %500 = arith.trunci %arg3 : i128 to i64
          %498 = arith.cmpi slt, %499, %500 : i64
          cf.cond_br %498, ^bb87, ^bb88
          ^bb87:
            cf.br ^bb83
          ^bb88:
            cf.br ^bb89
          ^bb89:
          %502 = arith.trunci %490 : i128 to i64
          %503 = arith.trunci %arg3 : i128 to i64
          %501 = arith.subi %502, %503 : i64
          %504 = arith.extsi %501 : i64 to i128
          %505 = llvm.load %412 : !llvm.ptr -> i128
          %507 = arith.trunci %504 : i128 to i64
          %508 = arith.trunci %505 : i128 to i64
          %506 = arith.cmpi sge, %507, %508 : i64
          cf.cond_br %506, ^bb90, ^bb91
          ^bb90:
            cf.br ^bb83
          ^bb91:
            cf.br ^bb92
          ^bb92:
          %510 = arith.trunci %504 : i128 to i64
          %511 = arith.trunci %413 : i128 to i64
          %509 = arith.remsi %510, %511 : i64
          %512 = arith.constant 0 : i32
          %514 = arith.extsi %512 : i32 to i64
          %513 = arith.cmpi ne, %509, %514 : i64
          cf.cond_br %513, ^bb93, ^bb94
          ^bb93:
            llvm.store %504, %412 : i128, !llvm.ptr
            cf.br ^bb83
          ^bb94:
            cf.br ^bb95
          ^bb95:
          %515 = llvm.load %481 : !llvm.ptr -> i64
          %516 = arith.constant 1 : i32
          %518 = arith.extsi %516 : i32 to i64
          %517 = arith.addi %515, %518 : i64
          llvm.store %517, %481 : i64, !llvm.ptr
          cf.br ^bb86
        ^bb86:
        cf.br ^bb81
      ^bb83:
      %519 = llvm.load %329 : !llvm.ptr -> i64
      %520 = arith.constant 1 : i32
      %522 = arith.extsi %520 : i32 to i64
      %521 = arith.addi %519, %522 : i64
      llvm.store %521, %329 : i64, !llvm.ptr
      cf.br ^bb78
    ^bb80:
    func.call @free(%323) : (!llvm.ptr) -> ()
    func.call @free(%374) : (!llvm.ptr) -> ()
    func.call @free(%380) : (!llvm.ptr) -> ()
    %526 = llvm.load %412 : !llvm.ptr -> i128
    func.return %526 : i128
  }
  func.func @max_B_sum(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64, %arg3: i128, %arg4: !llvm.ptr) -> i128 {
    %527 = arith.constant 2 : i32
    %529 = arith.extsi %527 : i32 to i64
    %528 = arith.divsi %arg0, %529 : i64
    %530 = arith.extsi %528 : i64 to i128
    %531 = arith.constant 0 : i32
    %533 = arith.extsi %531 : i32 to i64
    %532 = arith.cmpi eq, %arg2, %533 : i64
    cf.cond_br %532, ^bb96, ^bb97
    ^bb96:
      func.return %530 : i128
    ^bb97:
      cf.br ^bb98
    ^bb98:
    %534 = arith.extsi %arg0 : i64 to i128
    %536 = arith.trunci %534 : i128 to i64
    %537 = arith.trunci %530 : i128 to i64
    %535 = arith.subi %536, %537 : i64
    %538 = arith.extsi %535 : i64 to i128
    %540 = arith.trunci %538 : i128 to i64
    %541 = arith.trunci %530 : i128 to i64
    %539 = arith.muli %540, %541 : i64
    %543 = arith.trunci %arg3 : i128 to i64
    %542 = arith.cmpi sgt, %543, %539 : i64
    cf.cond_br %542, ^bb99, ^bb100
    ^bb99:
      %544 = arith.constant 1 : i32
      %546 = arith.constant 0 : i32
      %545 = arith.subi %546, %544 : i32
      %547 = arith.extsi %545 : i32 to i128
      func.return %547 : i128
    ^bb100:
      cf.br ^bb101
    ^bb101:
    %549 = arith.constant 16 : i32
    %550 = arith.extsi %549 : i32 to i64
    %548 = func.call @calloc(%arg2, %550) : (i64, i64) -> !llvm.ptr
    %551 = arith.constant 0 : i32
    %552 = arith.extsi %551 : i32 to i64
    %553 = llvm.mlir.constant(1 : i64) : i64
    %554 = llvm.alloca %553 x i64 : (i64) -> !llvm.ptr
    llvm.store %552, %554 : i64, !llvm.ptr
    cf.br ^bb102
    ^bb102:
    %555 = llvm.load %554 : !llvm.ptr -> i64
    %556 = arith.cmpi slt, %555, %arg2 : i64
    cf.cond_br %556, ^bb103, ^bb104
    ^bb103:
      %558 = llvm.load %554 : !llvm.ptr -> i64
      %559 = llvm.getelementptr %arg1[%558] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %557 = llvm.load %559 : !llvm.ptr -> i64
      %560 = arith.extsi %557 : i64 to i128
      %561 = arith.extsi %arg0 : i64 to i128
      %563 = arith.trunci %561 : i128 to i64
      %564 = arith.trunci %560 : i128 to i64
      %562 = arith.remsi %563, %564 : i64
      %566 = llvm.load %554 : !llvm.ptr -> i64
      %567 = llvm.getelementptr %arg4[%566] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %565 = llvm.load %567 : !llvm.ptr -> i128
      %569 = arith.trunci %565 : i128 to i64
      %568 = arith.muli %562, %569 : i64
      %571 = arith.trunci %arg3 : i128 to i64
      %570 = arith.remsi %568, %571 : i64
      %572 = llvm.load %554 : !llvm.ptr -> i64
      %573 = arith.extsi %570 : i64 to i128
      %574 = llvm.getelementptr %548[%572] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %573, %574 : i128, !llvm.ptr
      %575 = llvm.load %554 : !llvm.ptr -> i64
      %576 = arith.constant 1 : i32
      %578 = arith.extsi %576 : i32 to i64
      %577 = arith.addi %575, %578 : i64
      llvm.store %577, %554 : i64, !llvm.ptr
      cf.br ^bb102
    ^bb104:
    %580 = arith.constant 1 : i32
    %582 = arith.extsi %580 : i32 to i64
    %581 = arith.shli %582, %arg2 : i64
    %583 = arith.constant 16 : i32
    %584 = arith.extsi %583 : i32 to i64
    %579 = func.call @calloc(%581, %584) : (i64, i64) -> !llvm.ptr
    %585 = func.call @subset_sums128(%548, %arg2, %arg3, %579) : (!llvm.ptr, i64, i128, !llvm.ptr) -> i64
    %586 = arith.constant 0 : i32
    %587 = arith.extsi %586 : i32 to i128
    %588 = llvm.mlir.constant(1 : i64) : i64
    %589 = llvm.alloca %588 x i128 : (i64) -> !llvm.ptr
    llvm.store %587, %589 : i128, !llvm.ptr
    %590 = arith.constant 0 : i32
    %591 = arith.extsi %590 : i32 to i64
    llvm.store %591, %554 : i64, !llvm.ptr
    cf.br ^bb105
    ^bb105:
    %592 = llvm.load %554 : !llvm.ptr -> i64
    %593 = arith.cmpi slt, %592, %585 : i64
    cf.cond_br %593, ^bb106, ^bb107
    ^bb106:
      %595 = llvm.load %554 : !llvm.ptr -> i64
      %596 = llvm.getelementptr %579[%595] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      %594 = llvm.load %596 : !llvm.ptr -> i128
      %597 = arith.constant 0 : i32
      %599 = arith.trunci %594 : i128 to i64
      %600 = arith.extsi %597 : i32 to i64
      %598 = arith.cmpi eq, %599, %600 : i64
      cf.cond_br %598, ^bb108, ^bb109
      ^bb108:
        %602 = arith.trunci %arg3 : i128 to i64
        %603 = arith.trunci %530 : i128 to i64
        %601 = arith.cmpi sle, %602, %603 : i64
        cf.cond_br %601, ^bb111, ^bb112
        ^bb111:
          %605 = arith.trunci %530 : i128 to i64
          %606 = arith.trunci %arg3 : i128 to i64
          %604 = arith.divsi %605, %606 : i64
          %608 = arith.trunci %arg3 : i128 to i64
          %607 = arith.muli %604, %608 : i64
          %609 = arith.extsi %607 : i64 to i128
          %610 = llvm.load %589 : !llvm.ptr -> i128
          %612 = arith.trunci %609 : i128 to i64
          %613 = arith.trunci %610 : i128 to i64
          %611 = arith.cmpi sgt, %612, %613 : i64
          cf.cond_br %611, ^bb114, ^bb115
          ^bb114:
            llvm.store %609, %589 : i128, !llvm.ptr
            cf.br ^bb116
          ^bb115:
            cf.br ^bb116
          ^bb116:
          cf.br ^bb113
        ^bb112:
          cf.br ^bb113
        ^bb113:
        cf.br ^bb110
      ^bb109:
        %615 = arith.trunci %594 : i128 to i64
        %616 = arith.trunci %530 : i128 to i64
        %614 = arith.cmpi sle, %615, %616 : i64
        cf.cond_br %614, ^bb117, ^bb118
        ^bb117:
          %618 = arith.trunci %530 : i128 to i64
          %619 = arith.trunci %594 : i128 to i64
          %617 = arith.subi %618, %619 : i64
          %621 = arith.trunci %arg3 : i128 to i64
          %620 = arith.divsi %617, %621 : i64
          %623 = arith.trunci %arg3 : i128 to i64
          %622 = arith.muli %620, %623 : i64
          %625 = arith.trunci %594 : i128 to i64
          %624 = arith.addi %625, %622 : i64
          %626 = arith.extsi %624 : i64 to i128
          %627 = llvm.load %589 : !llvm.ptr -> i128
          %629 = arith.trunci %626 : i128 to i64
          %630 = arith.trunci %627 : i128 to i64
          %628 = arith.cmpi sgt, %629, %630 : i64
          cf.cond_br %628, ^bb120, ^bb121
          ^bb120:
            llvm.store %626, %589 : i128, !llvm.ptr
            cf.br ^bb122
          ^bb121:
            cf.br ^bb122
          ^bb122:
          cf.br ^bb119
        ^bb118:
          cf.br ^bb119
        ^bb119:
        cf.br ^bb110
      ^bb110:
      %631 = llvm.load %554 : !llvm.ptr -> i64
      %632 = arith.constant 1 : i32
      %634 = arith.extsi %632 : i32 to i64
      %633 = arith.addi %631, %634 : i64
      llvm.store %633, %554 : i64, !llvm.ptr
      cf.br ^bb105
    ^bb107:
    func.call @free(%548) : (!llvm.ptr) -> ()
    func.call @free(%579) : (!llvm.ptr) -> ()
    %637 = llvm.load %589 : !llvm.ptr -> i128
    %638 = arith.constant 0 : i32
    %640 = arith.trunci %637 : i128 to i64
    %641 = arith.extsi %638 : i32 to i64
    %639 = arith.cmpi eq, %640, %641 : i64
    cf.cond_br %639, ^bb123, ^bb124
    ^bb123:
      %642 = arith.constant 1 : i32
      %644 = arith.constant 0 : i32
      %643 = arith.subi %644, %642 : i32
      %645 = arith.extsi %643 : i32 to i128
      func.return %645 : i128
    ^bb124:
      cf.br ^bb125
    ^bb125:
    %646 = llvm.load %589 : !llvm.ptr -> i128
    func.return %646 : i128
  }
  func.func @q_for_p(%arg0: i64, %arg1: !llvm.ptr, %arg2: i64) -> i64 {
    %647 = arith.constant 0 : i32
    %648 = arith.extsi %647 : i32 to i64
    %649 = llvm.mlir.constant(1 : i64) : i64
    %650 = llvm.alloca %649 x i64 : (i64) -> !llvm.ptr
    llvm.store %648, %650 : i64, !llvm.ptr
    cf.br ^bb126
    ^bb126:
    %651 = llvm.load %650 : !llvm.ptr -> i64
    %652 = arith.cmpi slt, %651, %arg2 : i64
    cf.cond_br %652, ^bb127, ^bb128
    ^bb127:
      %654 = llvm.load %650 : !llvm.ptr -> i64
      %655 = llvm.getelementptr %arg1[%654] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %653 = llvm.load %655 : !llvm.ptr -> i64
      %656 = arith.muli %653, %653 : i64
      %657 = arith.cmpi sgt, %656, %arg0 : i64
      cf.cond_br %657, ^bb129, ^bb130
      ^bb129:
        func.return %653 : i64
      ^bb130:
        cf.br ^bb131
      ^bb131:
      %658 = llvm.load %650 : !llvm.ptr -> i64
      %659 = arith.constant 1 : i32
      %661 = arith.extsi %659 : i32 to i64
      %660 = arith.addi %658, %661 : i64
      llvm.store %660, %650 : i64, !llvm.ptr
      cf.br ^bb126
    ^bb128:
    %662 = arith.constant 0 : i32
    %663 = arith.extsi %662 : i32 to i64
    func.return %663 : i64
  }
  func.func @S(%arg0: i64) -> i64 {
    %665 = arith.constant 10000 : i32
    %666 = arith.constant 8 : i32
    %667 = arith.extsi %665 : i32 to i64
    %668 = arith.extsi %666 : i32 to i64
    %664 = func.call @calloc(%667, %668) : (i64, i64) -> !llvm.ptr
    %670 = arith.constant 200 : i32
    %672 = arith.extsi %670 : i32 to i64
    %671 = arith.addi %arg0, %672 : i64
    %669 = func.call @sieve(%671, %664) : (i64, !llvm.ptr) -> i64
    %673 = arith.constant 0 : i32
    %674 = arith.extsi %673 : i32 to i64
    %675 = llvm.mlir.constant(1 : i64) : i64
    %676 = llvm.alloca %675 x i64 : (i64) -> !llvm.ptr
    llvm.store %674, %676 : i64, !llvm.ptr
    %677 = arith.constant 0 : i32
    %678 = arith.extsi %677 : i32 to i64
    %679 = llvm.mlir.constant(1 : i64) : i64
    %680 = llvm.alloca %679 x i64 : (i64) -> !llvm.ptr
    llvm.store %678, %680 : i64, !llvm.ptr
    cf.br ^bb132
    ^bb132:
    %681 = llvm.load %680 : !llvm.ptr -> i64
    %682 = arith.cmpi slt, %681, %669 : i64
    cf.cond_br %682, ^bb133, ^bb134
    ^bb133:
      %684 = llvm.load %680 : !llvm.ptr -> i64
      %685 = llvm.getelementptr %664[%684] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %683 = llvm.load %685 : !llvm.ptr -> i64
      %686 = arith.cmpi slt, %683, %arg0 : i64
      cf.cond_br %686, ^bb135, ^bb136
      ^bb135:
        %687 = func.call @q_for_p(%683, %664, %669) : (i64, !llvm.ptr, i64) -> i64
        %688 = llvm.load %676 : !llvm.ptr -> i64
        %689 = arith.cmpi sgt, %687, %688 : i64
        cf.cond_br %689, ^bb138, ^bb139
        ^bb138:
          llvm.store %687, %676 : i64, !llvm.ptr
          cf.br ^bb140
        ^bb139:
          cf.br ^bb140
        ^bb140:
        cf.br ^bb137
      ^bb136:
        cf.br ^bb137
      ^bb137:
      %690 = llvm.load %680 : !llvm.ptr -> i64
      %691 = arith.constant 1 : i32
      %693 = arith.extsi %691 : i32 to i64
      %692 = arith.addi %690, %693 : i64
      llvm.store %692, %680 : i64, !llvm.ptr
      cf.br ^bb132
    ^bb134:
    %694 = arith.constant 0 : i32
    %695 = arith.extsi %694 : i32 to i64
    %696 = llvm.mlir.constant(1 : i64) : i64
    %697 = llvm.alloca %696 x i64 : (i64) -> !llvm.ptr
    llvm.store %695, %697 : i64, !llvm.ptr
    %698 = arith.constant 0 : i32
    %699 = arith.extsi %698 : i32 to i64
    llvm.store %699, %680 : i64, !llvm.ptr
    cf.br ^bb141
    ^bb141:
    %700 = llvm.load %680 : !llvm.ptr -> i64
    %701 = arith.cmpi slt, %700, %669 : i64
    cf.cond_br %701, ^bb142, ^bb143
    ^bb142:
      %703 = llvm.load %680 : !llvm.ptr -> i64
      %704 = llvm.getelementptr %664[%703] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %702 = llvm.load %704 : !llvm.ptr -> i64
      %705 = llvm.load %676 : !llvm.ptr -> i64
      %706 = arith.cmpi sle, %702, %705 : i64
      cf.cond_br %706, ^bb144, ^bb145
      ^bb144:
        %707 = llvm.load %697 : !llvm.ptr -> i64
        %708 = arith.constant 1 : i32
        %710 = arith.extsi %708 : i32 to i64
        %709 = arith.addi %707, %710 : i64
        llvm.store %709, %697 : i64, !llvm.ptr
        cf.br ^bb146
      ^bb145:
        cf.br ^bb146
      ^bb146:
      %711 = llvm.load %680 : !llvm.ptr -> i64
      %712 = arith.constant 1 : i32
      %714 = arith.extsi %712 : i32 to i64
      %713 = arith.addi %711, %714 : i64
      llvm.store %713, %680 : i64, !llvm.ptr
      cf.br ^bb141
    ^bb143:
    %716 = llvm.load %697 : !llvm.ptr -> i64
    %717 = arith.constant 16 : i32
    %718 = arith.extsi %717 : i32 to i64
    %715 = func.call @calloc(%716, %718) : (i64, i64) -> !llvm.ptr
    %720 = llvm.load %697 : !llvm.ptr -> i64
    %721 = arith.constant 8 : i32
    %722 = arith.extsi %721 : i32 to i64
    %719 = func.call @calloc(%720, %722) : (i64, i64) -> !llvm.ptr
    %724 = llvm.load %697 : !llvm.ptr -> i64
    %725 = arith.constant 8 : i32
    %726 = arith.extsi %725 : i32 to i64
    %723 = func.call @calloc(%724, %726) : (i64, i64) -> !llvm.ptr
    %728 = llvm.load %697 : !llvm.ptr -> i64
    %729 = llvm.load %697 : !llvm.ptr -> i64
    %730 = arith.muli %728, %729 : i64
    %731 = arith.constant 8 : i32
    %733 = arith.extsi %731 : i32 to i64
    %732 = arith.addi %730, %733 : i64
    %734 = arith.constant 16 : i32
    %735 = arith.extsi %734 : i32 to i64
    %727 = func.call @calloc(%732, %735) : (i64, i64) -> !llvm.ptr
    %736 = arith.constant 0 : i32
    %737 = arith.extsi %736 : i32 to i64
    %738 = llvm.mlir.constant(1 : i64) : i64
    %739 = llvm.alloca %738 x i64 : (i64) -> !llvm.ptr
    llvm.store %737, %739 : i64, !llvm.ptr
    %740 = arith.constant 0 : i32
    %741 = arith.extsi %740 : i32 to i64
    llvm.store %741, %680 : i64, !llvm.ptr
    cf.br ^bb147
    ^bb147:
    %742 = llvm.load %680 : !llvm.ptr -> i64
    %743 = llvm.load %697 : !llvm.ptr -> i64
    %744 = arith.cmpi slt, %742, %743 : i64
    cf.cond_br %744, ^bb148, ^bb149
    ^bb148:
      %745 = arith.constant 1 : i32
      %746 = arith.extsi %745 : i32 to i128
      %747 = llvm.mlir.constant(1 : i64) : i64
      %748 = llvm.alloca %747 x i128 : (i64) -> !llvm.ptr
      llvm.store %746, %748 : i128, !llvm.ptr
      %749 = arith.constant 0 : i32
      %750 = arith.extsi %749 : i32 to i64
      %751 = llvm.mlir.constant(1 : i64) : i64
      %752 = llvm.alloca %751 x i64 : (i64) -> !llvm.ptr
      llvm.store %750, %752 : i64, !llvm.ptr
      cf.br ^bb150
      ^bb150:
      %753 = llvm.load %752 : !llvm.ptr -> i64
      %754 = llvm.load %680 : !llvm.ptr -> i64
      %755 = arith.cmpi slt, %753, %754 : i64
      cf.cond_br %755, ^bb151, ^bb152
      ^bb151:
        %756 = llvm.load %748 : !llvm.ptr -> i128
        %758 = llvm.load %752 : !llvm.ptr -> i64
        %759 = llvm.getelementptr %664[%758] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %757 = llvm.load %759 : !llvm.ptr -> i64
        %760 = arith.extsi %757 : i64 to i128
        %762 = arith.trunci %756 : i128 to i64
        %763 = arith.trunci %760 : i128 to i64
        %761 = arith.muli %762, %763 : i64
        %764 = arith.extsi %761 : i64 to i128
        llvm.store %764, %748 : i128, !llvm.ptr
        %765 = llvm.load %752 : !llvm.ptr -> i64
        %766 = arith.constant 1 : i32
        %768 = arith.extsi %766 : i32 to i64
        %767 = arith.addi %765, %768 : i64
        llvm.store %767, %752 : i64, !llvm.ptr
        cf.br ^bb150
      ^bb152:
      %769 = llvm.load %748 : !llvm.ptr -> i128
      %770 = llvm.load %680 : !llvm.ptr -> i64
      %771 = llvm.getelementptr %715[%770] : (!llvm.ptr, i64) -> !llvm.ptr, i128
      llvm.store %769, %771 : i128, !llvm.ptr
      %772 = llvm.load %739 : !llvm.ptr -> i64
      %773 = llvm.load %680 : !llvm.ptr -> i64
      %774 = llvm.getelementptr %719[%773] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %772, %774 : i64, !llvm.ptr
      %775 = llvm.load %680 : !llvm.ptr -> i64
      %776 = llvm.load %680 : !llvm.ptr -> i64
      %777 = llvm.getelementptr %723[%776] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %775, %777 : i64, !llvm.ptr
      %778 = arith.constant 0 : i32
      %779 = arith.extsi %778 : i32 to i64
      llvm.store %779, %752 : i64, !llvm.ptr
      cf.br ^bb153
      ^bb153:
      %780 = llvm.load %752 : !llvm.ptr -> i64
      %781 = llvm.load %680 : !llvm.ptr -> i64
      %782 = arith.cmpi slt, %780, %781 : i64
      cf.cond_br %782, ^bb154, ^bb155
      ^bb154:
        %784 = llvm.load %752 : !llvm.ptr -> i64
        %785 = llvm.getelementptr %664[%784] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %783 = llvm.load %785 : !llvm.ptr -> i64
        %786 = arith.extsi %783 : i64 to i128
        %787 = llvm.load %748 : !llvm.ptr -> i128
        %789 = arith.trunci %787 : i128 to i64
        %790 = arith.trunci %786 : i128 to i64
        %788 = arith.divsi %789, %790 : i64
        %791 = arith.extsi %788 : i64 to i128
        %794 = arith.trunci %791 : i128 to i64
        %795 = arith.trunci %786 : i128 to i64
        %793 = arith.remsi %794, %795 : i64
        %796 = arith.extsi %793 : i64 to i128
        %792 = func.call @modinv128(%796, %786) : (i128, i128) -> i128
        %798 = arith.trunci %791 : i128 to i64
        %799 = arith.trunci %792 : i128 to i64
        %797 = arith.muli %798, %799 : i64
        %800 = llvm.load %748 : !llvm.ptr -> i128
        %802 = arith.trunci %800 : i128 to i64
        %801 = arith.remsi %797, %802 : i64
        %803 = llvm.load %739 : !llvm.ptr -> i64
        %804 = arith.extsi %801 : i64 to i128
        %805 = llvm.getelementptr %727[%803] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        llvm.store %804, %805 : i128, !llvm.ptr
        %806 = llvm.load %739 : !llvm.ptr -> i64
        %807 = arith.constant 1 : i32
        %809 = arith.extsi %807 : i32 to i64
        %808 = arith.addi %806, %809 : i64
        llvm.store %808, %739 : i64, !llvm.ptr
        %810 = llvm.load %752 : !llvm.ptr -> i64
        %811 = arith.constant 1 : i32
        %813 = arith.extsi %811 : i32 to i64
        %812 = arith.addi %810, %813 : i64
        llvm.store %812, %752 : i64, !llvm.ptr
        cf.br ^bb153
      ^bb155:
      %814 = llvm.load %680 : !llvm.ptr -> i64
      %815 = arith.constant 1 : i32
      %817 = arith.extsi %815 : i32 to i64
      %816 = arith.addi %814, %817 : i64
      llvm.store %816, %680 : i64, !llvm.ptr
      cf.br ^bb147
    ^bb149:
    %818 = arith.constant 0 : i32
    %819 = arith.extsi %818 : i32 to i128
    %820 = llvm.mlir.constant(1 : i64) : i64
    %821 = llvm.alloca %820 x i128 : (i64) -> !llvm.ptr
    llvm.store %819, %821 : i128, !llvm.ptr
    %822 = arith.constant 0 : i32
    %823 = arith.extsi %822 : i32 to i64
    llvm.store %823, %680 : i64, !llvm.ptr
    cf.br ^bb156
    ^bb156:
    %824 = llvm.load %680 : !llvm.ptr -> i64
    %825 = arith.cmpi slt, %824, %669 : i64
    cf.cond_br %825, ^bb157, ^bb158
    ^bb157:
      %827 = llvm.load %680 : !llvm.ptr -> i64
      %828 = llvm.getelementptr %664[%827] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      %826 = llvm.load %828 : !llvm.ptr -> i64
      %829 = arith.cmpi slt, %826, %arg0 : i64
      cf.cond_br %829, ^bb159, ^bb160
      ^bb159:
        %830 = func.call @q_for_p(%826, %664, %669) : (i64, !llvm.ptr, i64) -> i64
        %831 = arith.constant 0 : i32
        %832 = arith.extsi %831 : i32 to i64
        %833 = llvm.mlir.constant(1 : i64) : i64
        %834 = llvm.alloca %833 x i64 : (i64) -> !llvm.ptr
        llvm.store %832, %834 : i64, !llvm.ptr
        cf.br ^bb162
        ^bb162:
        %836 = llvm.load %834 : !llvm.ptr -> i64
        %837 = llvm.getelementptr %664[%836] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %835 = llvm.load %837 : !llvm.ptr -> i64
        %838 = arith.cmpi ne, %835, %830 : i64
        cf.cond_br %838, ^bb163, ^bb164
        ^bb163:
          %839 = llvm.load %834 : !llvm.ptr -> i64
          %840 = arith.constant 1 : i32
          %842 = arith.extsi %840 : i32 to i64
          %841 = arith.addi %839, %842 : i64
          llvm.store %841, %834 : i64, !llvm.ptr
          cf.br ^bb162
        ^bb164:
        %844 = llvm.load %834 : !llvm.ptr -> i64
        %845 = llvm.getelementptr %715[%844] : (!llvm.ptr, i64) -> !llvm.ptr, i128
        %843 = llvm.load %845 : !llvm.ptr -> i128
        %847 = llvm.load %834 : !llvm.ptr -> i64
        %848 = llvm.getelementptr %723[%847] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %846 = llvm.load %848 : !llvm.ptr -> i64
        %850 = arith.constant 1 : i32
        %852 = arith.extsi %850 : i32 to i64
        %851 = arith.addi %846, %852 : i64
        %853 = arith.constant 16 : i32
        %854 = arith.extsi %853 : i32 to i64
        %849 = func.call @calloc(%851, %854) : (i64, i64) -> !llvm.ptr
        %855 = arith.constant 0 : i32
        %856 = arith.extsi %855 : i32 to i64
        %857 = llvm.mlir.constant(1 : i64) : i64
        %858 = llvm.alloca %857 x i64 : (i64) -> !llvm.ptr
        llvm.store %856, %858 : i64, !llvm.ptr
        cf.br ^bb165
        ^bb165:
        %859 = llvm.load %858 : !llvm.ptr -> i64
        %860 = arith.cmpi slt, %859, %846 : i64
        cf.cond_br %860, ^bb166, ^bb167
        ^bb166:
          %863 = llvm.load %834 : !llvm.ptr -> i64
          %864 = llvm.getelementptr %719[%863] : (!llvm.ptr, i64) -> !llvm.ptr, i64
          %862 = llvm.load %864 : !llvm.ptr -> i64
          %865 = llvm.load %858 : !llvm.ptr -> i64
          %866 = arith.addi %862, %865 : i64
          %867 = llvm.getelementptr %727[%866] : (!llvm.ptr, i64) -> !llvm.ptr, i128
          %861 = llvm.load %867 : !llvm.ptr -> i128
          %868 = llvm.load %858 : !llvm.ptr -> i64
          %869 = llvm.getelementptr %849[%868] : (!llvm.ptr, i64) -> !llvm.ptr, i128
          llvm.store %861, %869 : i128, !llvm.ptr
          %870 = llvm.load %858 : !llvm.ptr -> i64
          %871 = arith.constant 1 : i32
          %873 = arith.extsi %871 : i32 to i64
          %872 = arith.addi %870, %873 : i64
          llvm.store %872, %858 : i64, !llvm.ptr
          cf.br ^bb165
        ^bb167:
        %874 = arith.extsi %826 : i64 to i128
        %875 = func.call @min_B_difference(%826, %664, %846, %843, %849) : (i64, !llvm.ptr, i64, i128, !llvm.ptr) -> i128
        %877 = arith.trunci %874 : i128 to i64
        %878 = arith.trunci %875 : i128 to i64
        %876 = arith.addi %877, %878 : i64
        %879 = arith.extsi %876 : i64 to i128
        %880 = func.call @max_B_sum(%826, %664, %846, %843, %849) : (i64, !llvm.ptr, i64, i128, !llvm.ptr) -> i128
        %881 = arith.constant 0 : i32
        %883 = arith.trunci %880 : i128 to i64
        %884 = arith.extsi %881 : i32 to i64
        %882 = arith.cmpi slt, %883, %884 : i64
        cf.cond_br %882, ^bb168, ^bb169
        ^bb168:
          %885 = llvm.load %821 : !llvm.ptr -> i128
          %887 = arith.trunci %885 : i128 to i64
          %888 = arith.trunci %879 : i128 to i64
          %886 = arith.addi %887, %888 : i64
          %889 = arith.extsi %886 : i64 to i128
          llvm.store %889, %821 : i128, !llvm.ptr
          cf.br ^bb170
        ^bb169:
          %890 = arith.extsi %826 : i64 to i128
          %892 = arith.trunci %890 : i128 to i64
          %893 = arith.trunci %880 : i128 to i64
          %891 = arith.subi %892, %893 : i64
          %894 = arith.extsi %891 : i64 to i128
          %896 = arith.trunci %894 : i128 to i64
          %897 = arith.trunci %879 : i128 to i64
          %895 = arith.cmpi slt, %896, %897 : i64
          cf.cond_br %895, ^bb171, ^bb172
          ^bb171:
            %898 = llvm.load %821 : !llvm.ptr -> i128
            %900 = arith.trunci %898 : i128 to i64
            %901 = arith.trunci %894 : i128 to i64
            %899 = arith.addi %900, %901 : i64
            %902 = arith.extsi %899 : i64 to i128
            llvm.store %902, %821 : i128, !llvm.ptr
            cf.br ^bb173
          ^bb172:
            %903 = llvm.load %821 : !llvm.ptr -> i128
            %905 = arith.trunci %903 : i128 to i64
            %906 = arith.trunci %879 : i128 to i64
            %904 = arith.addi %905, %906 : i64
            %907 = arith.extsi %904 : i64 to i128
            llvm.store %907, %821 : i128, !llvm.ptr
            cf.br ^bb173
          ^bb173:
          cf.br ^bb170
        ^bb170:
        func.call @free(%849) : (!llvm.ptr) -> ()
        cf.br ^bb161
      ^bb160:
        cf.br ^bb161
      ^bb161:
      %909 = llvm.load %680 : !llvm.ptr -> i64
      %910 = arith.constant 1 : i32
      %912 = arith.extsi %910 : i32 to i64
      %911 = arith.addi %909, %912 : i64
      llvm.store %911, %680 : i64, !llvm.ptr
      cf.br ^bb156
    ^bb158:
    func.call @free(%664) : (!llvm.ptr) -> ()
    func.call @free(%715) : (!llvm.ptr) -> ()
    func.call @free(%719) : (!llvm.ptr) -> ()
    func.call @free(%723) : (!llvm.ptr) -> ()
    func.call @free(%727) : (!llvm.ptr) -> ()
    %918 = llvm.load %821 : !llvm.ptr -> i128
    %919 = arith.trunci %918 : i128 to i64
    func.return %919 : i64
  }
  func.func @main() -> i32 {
    %920 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %922 = arith.constant 3800 : i32
    %923 = arith.extsi %922 : i32 to i64
    %921 = func.call @S(%923) : (i64) -> i64
    %924 = llvm.call @printf(%920, %921) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    %925 = arith.constant 0 : i32
    func.return %925 : i32
  }
}