Problem 375

M(2e9) for minima of PRNG subsequences; period 6308948, quadratic fit.

View problem on Project Euler

Performance comparison

Flow source

# Project Euler 375
# M(2e9) for minima of PRNG subsequences; period 6308948, quadratic fit.

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

function M_small(n: i64) -> i64 {
    let MOD: i64 = 50515093
    let SEED: i64 = 290797
    let mut s: i64 = SEED
    let vals: ptr<i64> = calloc(n + 10, 8)
    let cnts: ptr<i64> = calloc(n + 10, 8)
    if vals == null || cnts == null { return 0 }
    let mut top: i64 = 0
    let mut cur_sum: i64 = 0
    let mut total: i64 = 0
    let mut i: i64 = 0
    while i < n {
        s = (s * s) % MOD
        let x: i64 = s
        let mut cnt: i64 = 1
        while top > 0 && vals[top - 1] >= x {
            top = top - 1
            let v: i64 = vals[top]
            let c: i64 = cnts[top]
            cur_sum = cur_sum - v * c
            cnt = cnt + c
        }
        vals[top] = x
        cnts[top] = cnt
        top = top + 1
        cur_sum = cur_sum + x * cnt
        total = total + cur_sum
        i = i + 1
    }
    free(cnts)
    free(vals)
    return total
}

function main() -> i32 {
    let CYCLE_LEN: i64 = 6308948
    let MOD: i64 = 50515093
    let SEED: i64 = 290797
    let N: i64 = 2000000000
    let k: i64 = N / CYCLE_LEN
    let r: i64 = N % CYCLE_LEN

    # Build one cycle S1..CYCLE_LEN
    let cycle: ptr<i32> = calloc(CYCLE_LEN, 4)
    if cycle == null { return 1 }
    let mut s: i64 = SEED
    let mut i: i64 = 0
    while i < CYCLE_LEN {
        s = (s * s) % MOD
        cycle[i] = s as i32
        i = i + 1
    }

    # Sample M at CYCLE+r, 2*CYCLE+r, 3*CYCLE+r in one pass
    let t1: i64 = CYCLE_LEN + r
    let t2: i64 = 2 * CYCLE_LEN + r
    let t3: i64 = 3 * CYCLE_LEN + r
    let vals: ptr<i64> = calloc(100, 8)
    let cnts: ptr<i64> = calloc(100, 8)
    if vals == null || cnts == null { return 1 }
    let mut top: i64 = 0
    let mut cur_sum: i64 = 0
    let mut total: i64 = 0
    let mut y1: i64 = 0
    let mut y2: i64 = 0
    let mut y3: i64 = 0
    let mut idx: i64 = 0
    let mut pos: i64 = 0

    while pos < t3 {
        let x: i64 = cycle[idx] as i64
        idx = idx + 1
        if idx == CYCLE_LEN { idx = 0 }
        pos = pos + 1
        let mut cnt: i64 = 1
        while top > 0 && vals[top - 1] >= x {
            top = top - 1
            cur_sum = cur_sum - vals[top] * cnts[top]
            cnt = cnt + cnts[top]
        }
        vals[top] = x
        cnts[top] = cnt
        top = top + 1
        cur_sum = cur_sum + x * cnt
        total = total + cur_sum
        if pos == t1 { y1 = total }
        if pos == t2 { y2 = total }
        if pos == t3 { y3 = total }
    }

    let second: i64 = y3 - 2 * y2 + y1
    let a: i64 = second / 2
    let b: i64 = (y2 - y1) - 3 * a
    let c: i64 = y1 - a - b
    let ans: i64 = a * k * k + b * k + c
    printf("%lld\n", ans)

    free(cnts)
    free(vals)
    free(cycle)
    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; }

int64_t M_small_i64(int64_t n);
int32_t main(void);



int64_t M_small_i64(int64_t n) {
    int64_t MOD = 50515093;
    int64_t SEED = 290797;
    int64_t s = SEED;
    int64_t* vals = (int64_t*)(calloc((n + 10), 8));
    int64_t* cnts = (int64_t*)(calloc((n + 10), 8));
    if ((vals == NULL || cnts == NULL)) {
        return 0;
    }
    int64_t top = 0;
    int64_t cur_sum = 0;
    int64_t total = 0;
    int64_t i = 0;
    while (i < n) {
        s = FLOW_CHECKED_MOD(((s * s)), (MOD));
        int64_t x = s;
        int64_t cnt = 1;
        while ((top > 0 && vals[(top - 1)] >= x)) {
            top = (top - 1);
            int64_t v = vals[top];
            int64_t c = cnts[top];
            cur_sum = (cur_sum - (v * c));
            cnt = (cnt + c);
        }
        vals[top] = x;
        cnts[top] = cnt;
        top = (top + 1);
        cur_sum = (cur_sum + (x * cnt));
        total = (total + cur_sum);
        i = (i + 1);
    }
    free(cnts);
    free(vals);
    return total;
}

int32_t main(void) {
    int64_t CYCLE_LEN = 6308948;
    int64_t MOD = 50515093;
    int64_t SEED = 290797;
    int64_t N = 2000000000;
    int64_t k = FLOW_CHECKED_DIV((N), (CYCLE_LEN));
    int64_t r = FLOW_CHECKED_MOD((N), (CYCLE_LEN));
    int32_t* cycle = (int32_t*)(calloc(CYCLE_LEN, 4));
    if (cycle == NULL) {
        return 1;
    }
    int64_t s = SEED;
    int64_t i = 0;
    while (i < CYCLE_LEN) {
        s = FLOW_CHECKED_MOD(((s * s)), (MOD));
        cycle[i] = ((int32_t)(s));
        i = (i + 1);
    }
    int64_t t1 = (CYCLE_LEN + r);
    int64_t t2 = ((2 * CYCLE_LEN) + r);
    int64_t t3 = ((3 * CYCLE_LEN) + r);
    int64_t* vals = (int64_t*)(calloc(100, 8));
    int64_t* cnts = (int64_t*)(calloc(100, 8));
    if ((vals == NULL || cnts == NULL)) {
        return 1;
    }
    int64_t top = 0;
    int64_t cur_sum = 0;
    int64_t total = 0;
    int64_t y1 = 0;
    int64_t y2 = 0;
    int64_t y3 = 0;
    int64_t idx = 0;
    int64_t pos = 0;
    while (pos < t3) {
        int64_t x = ((int64_t)(cycle[idx]));
        idx = (idx + 1);
        if (idx == CYCLE_LEN) {
            idx = 0;
        }
        pos = (pos + 1);
        int64_t cnt = 1;
        while ((top > 0 && vals[(top - 1)] >= x)) {
            top = (top - 1);
            cur_sum = (cur_sum - (vals[top] * cnts[top]));
            cnt = (cnt + cnts[top]);
        }
        vals[top] = x;
        cnts[top] = cnt;
        top = (top + 1);
        cur_sum = (cur_sum + (x * cnt));
        total = (total + cur_sum);
        if (pos == t1) {
            y1 = total;
        }
        if (pos == t2) {
            y2 = total;
        }
        if (pos == t3) {
            y3 = total;
        }
    }
    int64_t second = ((y3 - (2 * y2)) + y1);
    int64_t a = FLOW_CHECKED_DIV((second), (2));
    int64_t b = ((y2 - y1) - (3 * a));
    int64_t c = ((y1 - a) - b);
    int64_t ans = ((((a * k) * k) + (b * k)) + c);
    printf("%lld\n", ans);
    free(cnts);
    free(vals);
    free(cycle);
    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 @M_small(%arg0: i64) -> i64 {
    %0 = arith.constant 50515093 : i32
    %1 = arith.extsi %0 : i32 to i64
    %2 = arith.constant 290797 : i32
    %3 = arith.extsi %2 : i32 to i64
    %4 = llvm.mlir.constant(1 : i64) : i64
    %5 = llvm.alloca %4 x i64 : (i64) -> !llvm.ptr
    llvm.store %3, %5 : i64, !llvm.ptr
    %7 = arith.constant 10 : i32
    %9 = arith.extsi %7 : i32 to i64
    %8 = arith.addi %arg0, %9 : i64
    %10 = arith.constant 8 : i32
    %11 = arith.extsi %10 : i32 to i64
    %6 = func.call @calloc(%8, %11) : (i64, i64) -> !llvm.ptr
    %13 = arith.constant 10 : i32
    %15 = arith.extsi %13 : i32 to i64
    %14 = arith.addi %arg0, %15 : i64
    %16 = arith.constant 8 : i32
    %17 = arith.extsi %16 : i32 to i64
    %12 = func.call @calloc(%14, %17) : (i64, i64) -> !llvm.ptr
    %18 = llvm.mlir.zero : !llvm.ptr
    %19 = llvm.icmp "eq" %6, %18 : !llvm.ptr
    %20 = scf.if %19 -> (i1) {
      %21 = arith.constant true
      scf.yield %21 : i1
    } else {
      %22 = llvm.mlir.zero : !llvm.ptr
      %23 = llvm.icmp "eq" %12, %22 : !llvm.ptr
      scf.yield %23 : i1
    }
    cf.cond_br %20, ^bb0, ^bb1
    ^bb0:
      %24 = arith.constant 0 : i32
      %25 = arith.extsi %24 : i32 to i64
      func.return %25 : i64
    ^bb1:
      cf.br ^bb2
    ^bb2:
    %26 = arith.constant 0 : i32
    %27 = arith.extsi %26 : i32 to i64
    %28 = llvm.mlir.constant(1 : i64) : i64
    %29 = llvm.alloca %28 x i64 : (i64) -> !llvm.ptr
    llvm.store %27, %29 : i64, !llvm.ptr
    %30 = arith.constant 0 : i32
    %31 = arith.extsi %30 : i32 to i64
    %32 = llvm.mlir.constant(1 : i64) : i64
    %33 = llvm.alloca %32 x i64 : (i64) -> !llvm.ptr
    llvm.store %31, %33 : i64, !llvm.ptr
    %34 = arith.constant 0 : i32
    %35 = arith.extsi %34 : i32 to i64
    %36 = llvm.mlir.constant(1 : i64) : i64
    %37 = llvm.alloca %36 x i64 : (i64) -> !llvm.ptr
    llvm.store %35, %37 : i64, !llvm.ptr
    %38 = arith.constant 0 : i32
    %39 = arith.extsi %38 : i32 to i64
    %40 = llvm.mlir.constant(1 : i64) : i64
    %41 = llvm.alloca %40 x i64 : (i64) -> !llvm.ptr
    llvm.store %39, %41 : i64, !llvm.ptr
    cf.br ^bb3
    ^bb3:
    %42 = llvm.load %41 : !llvm.ptr -> i64
    %43 = arith.cmpi slt, %42, %arg0 : i64
    cf.cond_br %43, ^bb4, ^bb5
    ^bb4:
      %44 = llvm.load %5 : !llvm.ptr -> i64
      %45 = llvm.load %5 : !llvm.ptr -> i64
      %46 = arith.muli %44, %45 : i64
      %47 = arith.remsi %46, %1 : i64
      llvm.store %47, %5 : i64, !llvm.ptr
      %48 = llvm.load %5 : !llvm.ptr -> i64
      %49 = arith.constant 1 : i32
      %50 = arith.extsi %49 : i32 to i64
      %51 = llvm.mlir.constant(1 : i64) : i64
      %52 = llvm.alloca %51 x i64 : (i64) -> !llvm.ptr
      llvm.store %50, %52 : i64, !llvm.ptr
      cf.br ^bb6
      ^bb6:
      %53 = llvm.load %29 : !llvm.ptr -> i64
      %54 = arith.constant 0 : i32
      %56 = arith.extsi %54 : i32 to i64
      %55 = arith.cmpi sgt, %53, %56 : i64
      %57 = scf.if %55 -> (i1) {
        %59 = llvm.load %29 : !llvm.ptr -> i64
        %60 = arith.constant 1 : i32
        %62 = arith.extsi %60 : i32 to i64
        %61 = arith.subi %59, %62 : i64
        %63 = llvm.getelementptr %6[%61] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %58 = llvm.load %63 : !llvm.ptr -> i64
        %64 = arith.cmpi sge, %58, %48 : i64
        scf.yield %64 : i1
      } else {
        %65 = arith.constant false
        scf.yield %65 : i1
      }
      cf.cond_br %57, ^bb7, ^bb8
      ^bb7:
        %66 = llvm.load %29 : !llvm.ptr -> i64
        %67 = arith.constant 1 : i32
        %69 = arith.extsi %67 : i32 to i64
        %68 = arith.subi %66, %69 : i64
        llvm.store %68, %29 : i64, !llvm.ptr
        %71 = llvm.load %29 : !llvm.ptr -> i64
        %72 = llvm.getelementptr %6[%71] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %70 = llvm.load %72 : !llvm.ptr -> i64
        %74 = llvm.load %29 : !llvm.ptr -> i64
        %75 = llvm.getelementptr %12[%74] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %73 = llvm.load %75 : !llvm.ptr -> i64
        %76 = llvm.load %33 : !llvm.ptr -> i64
        %77 = arith.muli %70, %73 : i64
        %78 = arith.subi %76, %77 : i64
        llvm.store %78, %33 : i64, !llvm.ptr
        %79 = llvm.load %52 : !llvm.ptr -> i64
        %80 = arith.addi %79, %73 : i64
        llvm.store %80, %52 : i64, !llvm.ptr
        cf.br ^bb6
      ^bb8:
      %81 = llvm.load %29 : !llvm.ptr -> i64
      %82 = llvm.getelementptr %6[%81] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %48, %82 : i64, !llvm.ptr
      %83 = llvm.load %52 : !llvm.ptr -> i64
      %84 = llvm.load %29 : !llvm.ptr -> i64
      %85 = llvm.getelementptr %12[%84] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %83, %85 : i64, !llvm.ptr
      %86 = llvm.load %29 : !llvm.ptr -> i64
      %87 = arith.constant 1 : i32
      %89 = arith.extsi %87 : i32 to i64
      %88 = arith.addi %86, %89 : i64
      llvm.store %88, %29 : i64, !llvm.ptr
      %90 = llvm.load %33 : !llvm.ptr -> i64
      %91 = llvm.load %52 : !llvm.ptr -> i64
      %92 = arith.muli %48, %91 : i64
      %93 = arith.addi %90, %92 : i64
      llvm.store %93, %33 : i64, !llvm.ptr
      %94 = llvm.load %37 : !llvm.ptr -> i64
      %95 = llvm.load %33 : !llvm.ptr -> i64
      %96 = arith.addi %94, %95 : i64
      llvm.store %96, %37 : i64, !llvm.ptr
      %97 = llvm.load %41 : !llvm.ptr -> i64
      %98 = arith.constant 1 : i32
      %100 = arith.extsi %98 : i32 to i64
      %99 = arith.addi %97, %100 : i64
      llvm.store %99, %41 : i64, !llvm.ptr
      cf.br ^bb3
    ^bb5:
    func.call @free(%12) : (!llvm.ptr) -> ()
    func.call @free(%6) : (!llvm.ptr) -> ()
    %103 = llvm.load %37 : !llvm.ptr -> i64
    func.return %103 : i64
  }
  func.func @main() -> i32 {
    %104 = arith.constant 6308948 : i32
    %105 = arith.extsi %104 : i32 to i64
    %106 = arith.constant 50515093 : i32
    %107 = arith.extsi %106 : i32 to i64
    %108 = arith.constant 290797 : i32
    %109 = arith.extsi %108 : i32 to i64
    %110 = arith.constant 2000000000 : i32
    %111 = arith.extsi %110 : i32 to i64
    %112 = arith.divsi %111, %105 : i64
    %113 = arith.remsi %111, %105 : i64
    %115 = arith.constant 4 : i32
    %116 = arith.extsi %115 : i32 to i64
    %114 = func.call @calloc(%105, %116) : (i64, i64) -> !llvm.ptr
    %117 = llvm.mlir.zero : !llvm.ptr
    %118 = llvm.icmp "eq" %114, %117 : !llvm.ptr
    cf.cond_br %118, ^bb9, ^bb10
    ^bb9:
      %119 = arith.constant 1 : i32
      func.return %119 : i32
    ^bb10:
      cf.br ^bb11
    ^bb11:
    %120 = llvm.mlir.constant(1 : i64) : i64
    %121 = llvm.alloca %120 x i64 : (i64) -> !llvm.ptr
    llvm.store %109, %121 : i64, !llvm.ptr
    %122 = arith.constant 0 : i32
    %123 = arith.extsi %122 : i32 to i64
    %124 = llvm.mlir.constant(1 : i64) : i64
    %125 = llvm.alloca %124 x i64 : (i64) -> !llvm.ptr
    llvm.store %123, %125 : i64, !llvm.ptr
    cf.br ^bb12
    ^bb12:
    %126 = llvm.load %125 : !llvm.ptr -> i64
    %127 = arith.cmpi slt, %126, %105 : i64
    cf.cond_br %127, ^bb13, ^bb14
    ^bb13:
      %128 = llvm.load %121 : !llvm.ptr -> i64
      %129 = llvm.load %121 : !llvm.ptr -> i64
      %130 = arith.muli %128, %129 : i64
      %131 = arith.remsi %130, %107 : i64
      llvm.store %131, %121 : i64, !llvm.ptr
      %132 = llvm.load %121 : !llvm.ptr -> i64
      %133 = arith.trunci %132 : i64 to i32
      %134 = llvm.load %125 : !llvm.ptr -> i64
      %135 = llvm.getelementptr %114[%134] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      llvm.store %133, %135 : i32, !llvm.ptr
      %136 = llvm.load %125 : !llvm.ptr -> i64
      %137 = arith.constant 1 : i32
      %139 = arith.extsi %137 : i32 to i64
      %138 = arith.addi %136, %139 : i64
      llvm.store %138, %125 : i64, !llvm.ptr
      cf.br ^bb12
    ^bb14:
    %140 = arith.addi %105, %113 : i64
    %141 = arith.constant 2 : i32
    %143 = arith.extsi %141 : i32 to i64
    %142 = arith.muli %143, %105 : i64
    %144 = arith.addi %142, %113 : i64
    %145 = arith.constant 3 : i32
    %147 = arith.extsi %145 : i32 to i64
    %146 = arith.muli %147, %105 : i64
    %148 = arith.addi %146, %113 : i64
    %150 = arith.constant 100 : i32
    %151 = arith.constant 8 : i32
    %152 = arith.extsi %150 : i32 to i64
    %153 = arith.extsi %151 : i32 to i64
    %149 = func.call @calloc(%152, %153) : (i64, i64) -> !llvm.ptr
    %155 = arith.constant 100 : i32
    %156 = arith.constant 8 : i32
    %157 = arith.extsi %155 : i32 to i64
    %158 = arith.extsi %156 : i32 to i64
    %154 = func.call @calloc(%157, %158) : (i64, i64) -> !llvm.ptr
    %159 = llvm.mlir.zero : !llvm.ptr
    %160 = llvm.icmp "eq" %149, %159 : !llvm.ptr
    %161 = scf.if %160 -> (i1) {
      %162 = arith.constant true
      scf.yield %162 : i1
    } else {
      %163 = llvm.mlir.zero : !llvm.ptr
      %164 = llvm.icmp "eq" %154, %163 : !llvm.ptr
      scf.yield %164 : i1
    }
    cf.cond_br %161, ^bb15, ^bb16
    ^bb15:
      %165 = arith.constant 1 : i32
      func.return %165 : i32
    ^bb16:
      cf.br ^bb17
    ^bb17:
    %166 = arith.constant 0 : i32
    %167 = arith.extsi %166 : i32 to i64
    %168 = llvm.mlir.constant(1 : i64) : i64
    %169 = llvm.alloca %168 x i64 : (i64) -> !llvm.ptr
    llvm.store %167, %169 : i64, !llvm.ptr
    %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 0 : i32
    %175 = arith.extsi %174 : i32 to i64
    %176 = llvm.mlir.constant(1 : i64) : i64
    %177 = llvm.alloca %176 x i64 : (i64) -> !llvm.ptr
    llvm.store %175, %177 : i64, !llvm.ptr
    %178 = arith.constant 0 : i32
    %179 = arith.extsi %178 : i32 to i64
    %180 = llvm.mlir.constant(1 : i64) : i64
    %181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
    llvm.store %179, %181 : i64, !llvm.ptr
    %182 = arith.constant 0 : i32
    %183 = arith.extsi %182 : i32 to i64
    %184 = llvm.mlir.constant(1 : i64) : i64
    %185 = llvm.alloca %184 x i64 : (i64) -> !llvm.ptr
    llvm.store %183, %185 : i64, !llvm.ptr
    %186 = arith.constant 0 : i32
    %187 = arith.extsi %186 : i32 to i64
    %188 = llvm.mlir.constant(1 : i64) : i64
    %189 = llvm.alloca %188 x i64 : (i64) -> !llvm.ptr
    llvm.store %187, %189 : i64, !llvm.ptr
    %190 = arith.constant 0 : i32
    %191 = arith.extsi %190 : i32 to i64
    %192 = llvm.mlir.constant(1 : i64) : i64
    %193 = llvm.alloca %192 x i64 : (i64) -> !llvm.ptr
    llvm.store %191, %193 : i64, !llvm.ptr
    %194 = arith.constant 0 : i32
    %195 = arith.extsi %194 : i32 to i64
    %196 = llvm.mlir.constant(1 : i64) : i64
    %197 = llvm.alloca %196 x i64 : (i64) -> !llvm.ptr
    llvm.store %195, %197 : i64, !llvm.ptr
    cf.br ^bb18
    ^bb18:
    %198 = llvm.load %197 : !llvm.ptr -> i64
    %199 = arith.cmpi slt, %198, %148 : i64
    cf.cond_br %199, ^bb19, ^bb20
    ^bb19:
      %201 = llvm.load %193 : !llvm.ptr -> i64
      %202 = llvm.getelementptr %114[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i32
      %200 = llvm.load %202 : !llvm.ptr -> i32
      %203 = arith.extsi %200 : i32 to i64
      %204 = llvm.load %193 : !llvm.ptr -> i64
      %205 = arith.constant 1 : i32
      %207 = arith.extsi %205 : i32 to i64
      %206 = arith.addi %204, %207 : i64
      llvm.store %206, %193 : i64, !llvm.ptr
      %208 = llvm.load %193 : !llvm.ptr -> i64
      %209 = arith.cmpi eq, %208, %105 : i64
      cf.cond_br %209, ^bb21, ^bb22
      ^bb21:
        %210 = arith.constant 0 : i32
        %211 = arith.extsi %210 : i32 to i64
        llvm.store %211, %193 : i64, !llvm.ptr
        cf.br ^bb23
      ^bb22:
        cf.br ^bb23
      ^bb23:
      %212 = llvm.load %197 : !llvm.ptr -> i64
      %213 = arith.constant 1 : i32
      %215 = arith.extsi %213 : i32 to i64
      %214 = arith.addi %212, %215 : i64
      llvm.store %214, %197 : i64, !llvm.ptr
      %216 = arith.constant 1 : i32
      %217 = arith.extsi %216 : i32 to i64
      %218 = llvm.mlir.constant(1 : i64) : i64
      %219 = llvm.alloca %218 x i64 : (i64) -> !llvm.ptr
      llvm.store %217, %219 : i64, !llvm.ptr
      cf.br ^bb24
      ^bb24:
      %220 = llvm.load %169 : !llvm.ptr -> i64
      %221 = arith.constant 0 : i32
      %223 = arith.extsi %221 : i32 to i64
      %222 = arith.cmpi sgt, %220, %223 : i64
      %224 = scf.if %222 -> (i1) {
        %226 = llvm.load %169 : !llvm.ptr -> i64
        %227 = arith.constant 1 : i32
        %229 = arith.extsi %227 : i32 to i64
        %228 = arith.subi %226, %229 : i64
        %230 = llvm.getelementptr %149[%228] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %225 = llvm.load %230 : !llvm.ptr -> i64
        %231 = arith.cmpi sge, %225, %203 : i64
        scf.yield %231 : i1
      } else {
        %232 = arith.constant false
        scf.yield %232 : i1
      }
      cf.cond_br %224, ^bb25, ^bb26
      ^bb25:
        %233 = llvm.load %169 : !llvm.ptr -> i64
        %234 = arith.constant 1 : i32
        %236 = arith.extsi %234 : i32 to i64
        %235 = arith.subi %233, %236 : i64
        llvm.store %235, %169 : i64, !llvm.ptr
        %237 = llvm.load %173 : !llvm.ptr -> i64
        %239 = llvm.load %169 : !llvm.ptr -> i64
        %240 = llvm.getelementptr %149[%239] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %238 = llvm.load %240 : !llvm.ptr -> i64
        %242 = llvm.load %169 : !llvm.ptr -> i64
        %243 = llvm.getelementptr %154[%242] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %241 = llvm.load %243 : !llvm.ptr -> i64
        %244 = arith.muli %238, %241 : i64
        %245 = arith.subi %237, %244 : i64
        llvm.store %245, %173 : i64, !llvm.ptr
        %246 = llvm.load %219 : !llvm.ptr -> i64
        %248 = llvm.load %169 : !llvm.ptr -> i64
        %249 = llvm.getelementptr %154[%248] : (!llvm.ptr, i64) -> !llvm.ptr, i64
        %247 = llvm.load %249 : !llvm.ptr -> i64
        %250 = arith.addi %246, %247 : i64
        llvm.store %250, %219 : i64, !llvm.ptr
        cf.br ^bb24
      ^bb26:
      %251 = llvm.load %169 : !llvm.ptr -> i64
      %252 = llvm.getelementptr %149[%251] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %203, %252 : i64, !llvm.ptr
      %253 = llvm.load %219 : !llvm.ptr -> i64
      %254 = llvm.load %169 : !llvm.ptr -> i64
      %255 = llvm.getelementptr %154[%254] : (!llvm.ptr, i64) -> !llvm.ptr, i64
      llvm.store %253, %255 : i64, !llvm.ptr
      %256 = llvm.load %169 : !llvm.ptr -> i64
      %257 = arith.constant 1 : i32
      %259 = arith.extsi %257 : i32 to i64
      %258 = arith.addi %256, %259 : i64
      llvm.store %258, %169 : i64, !llvm.ptr
      %260 = llvm.load %173 : !llvm.ptr -> i64
      %261 = llvm.load %219 : !llvm.ptr -> i64
      %262 = arith.muli %203, %261 : i64
      %263 = arith.addi %260, %262 : i64
      llvm.store %263, %173 : i64, !llvm.ptr
      %264 = llvm.load %177 : !llvm.ptr -> i64
      %265 = llvm.load %173 : !llvm.ptr -> i64
      %266 = arith.addi %264, %265 : i64
      llvm.store %266, %177 : i64, !llvm.ptr
      %267 = llvm.load %197 : !llvm.ptr -> i64
      %268 = arith.cmpi eq, %267, %140 : i64
      cf.cond_br %268, ^bb27, ^bb28
      ^bb27:
        %269 = llvm.load %177 : !llvm.ptr -> i64
        llvm.store %269, %181 : i64, !llvm.ptr
        cf.br ^bb29
      ^bb28:
        cf.br ^bb29
      ^bb29:
      %270 = llvm.load %197 : !llvm.ptr -> i64
      %271 = arith.cmpi eq, %270, %144 : i64
      cf.cond_br %271, ^bb30, ^bb31
      ^bb30:
        %272 = llvm.load %177 : !llvm.ptr -> i64
        llvm.store %272, %185 : i64, !llvm.ptr
        cf.br ^bb32
      ^bb31:
        cf.br ^bb32
      ^bb32:
      %273 = llvm.load %197 : !llvm.ptr -> i64
      %274 = arith.cmpi eq, %273, %148 : i64
      cf.cond_br %274, ^bb33, ^bb34
      ^bb33:
        %275 = llvm.load %177 : !llvm.ptr -> i64
        llvm.store %275, %189 : i64, !llvm.ptr
        cf.br ^bb35
      ^bb34:
        cf.br ^bb35
      ^bb35:
      cf.br ^bb18
    ^bb20:
    %276 = llvm.load %189 : !llvm.ptr -> i64
    %277 = arith.constant 2 : i32
    %278 = llvm.load %185 : !llvm.ptr -> i64
    %280 = arith.extsi %277 : i32 to i64
    %279 = arith.muli %280, %278 : i64
    %281 = arith.subi %276, %279 : i64
    %282 = llvm.load %181 : !llvm.ptr -> i64
    %283 = arith.addi %281, %282 : i64
    %284 = arith.constant 2 : i32
    %286 = arith.extsi %284 : i32 to i64
    %285 = arith.divsi %283, %286 : i64
    %287 = llvm.load %185 : !llvm.ptr -> i64
    %288 = llvm.load %181 : !llvm.ptr -> i64
    %289 = arith.subi %287, %288 : i64
    %290 = arith.constant 3 : i32
    %292 = arith.extsi %290 : i32 to i64
    %291 = arith.muli %292, %285 : i64
    %293 = arith.subi %289, %291 : i64
    %294 = llvm.load %181 : !llvm.ptr -> i64
    %295 = arith.subi %294, %285 : i64
    %296 = arith.subi %295, %293 : i64
    %297 = arith.muli %285, %112 : i64
    %298 = arith.muli %297, %112 : i64
    %299 = arith.muli %293, %112 : i64
    %300 = arith.addi %298, %299 : i64
    %301 = arith.addi %300, %296 : i64
    %302 = llvm.mlir.addressof @str_0 : !llvm.ptr
    %303 = llvm.call @printf(%302, %301) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
    func.call @free(%154) : (!llvm.ptr) -> ()
    func.call @free(%149) : (!llvm.ptr) -> ()
    func.call @free(%114) : (!llvm.ptr) -> ()
    %307 = arith.constant 0 : i32
    func.return %307 : i32
  }
}