#include <gc.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define grev_malloc GC_malloc

typedef uint64_t u64;
typedef uint32_t u32;
typedef int64_t i64;

static const u64 INT_MASK = 0b1;
static const u64 INT_ZERO = INT_MASK;

static const u64 BOXED_MASK = 0b11;
static const u64 MAX_EV_ID = 128;

static const u64 BOOL_FALSE = 0b010;
static const u64 BOOL_TRUE = 0b110;
static const u64 BOOL_TAG = 0b010;
static const u64 BOOL_MASK = 0b111;

enum error {
  NotImplemented = 10,
  ArrayIndexOutOfBounds = 11,
  TypeMismatch = 12,
  UnexpectedValue = 13,
  EvidenceNotJustify = 14,
  UnexpectedVariantCase = 15,
};

/*
Bitmagic
*/

static const u32 MAX_WIDTH = 64;
static const u32 ALPHABET_SIZE = 16;

typedef unsigned char byte;

// lower num bits
#define lower(val, bits) ((val) & ((((u64)1) << (bits)) - 1))
#define twidth                                                                 \
  16 // width of exponentially-sized tables
     // we spend (2twidth+1) * 2^twidth bytes for all the trees

// we assume tree descriptions fit in 1 word of topology + 1 of labels

// least significant 1

static u32 decode[64] = {0,  1,  56, 2,  57, 49, 28, 3,  61, 58, 42, 50, 38,
                         29, 17, 4,  62, 47, 59, 36, 45, 43, 51, 22, 53, 39,
                         33, 30, 24, 18, 12, 5,  63, 55, 48, 27, 60, 41, 37,
                         16, 46, 35, 44, 21, 52, 32, 23, 11, 54, 26, 40, 15,
                         34, 20, 31, 10, 25, 14, 19, 9,  13, 8,  7,  6};

extern inline u32 lsb(uint64_t x) {
  return decode[(0x03f79d71b4ca8b09 * (x & -x)) >> 58];
}

extern inline u32 popcount(uint64_t y) {
  y -= ((y >> 1) & 0x5555555555555555ull);
  y = (y & 0x3333333333333333ull) + (y >> 2 & 0x3333333333333333ull);
  return ((y + (y >> 4)) & 0xf0f0f0f0f0f0f0full) * 0x101010101010101ull >> 56;
}

// preorder select

// select1[i*twidth + j] tells the bit pos with the (j+1)th 1
// for 0 <= i < 2^twidth, 0 <= j < twidth
static byte *select1 = NULL;

// creates select1 table

extern void prepareSelect(void) {
  u64 i, n;
  u32 r, j;
  byte *ptr;

  n = ((u64)1) << twidth;
  select1 = (byte *)malloc(n * twidth);
  if (select1 == NULL) {
    fprintf(stderr, "Error: could not allocate %li bytes\n", n * twidth);
    exit(1);
  }
  ptr = select1;
  for (i = 0; i < n; i++) {
    r = 0;
    for (j = 0; j < twidth; j++) {
      ptr[r] = j; // rewrites but avoids branching
      r += (i >> j) & 1;
    }
    while (r < twidth)
      ptr[r++] = twidth; // not reached
    ptr += twidth;
  }
}

// where the (j+1)th 1 is in x

extern u32 preorderselect(u64 x, u32 j) {
  u32 pos = 0; // positions already skipped
  u32 r, m;
  while (1) {
    if (j < twidth) // can be found in first block
    {
      m = select1[lower(x, twidth) * twidth + j];
      if (m < twidth)
        return pos + m; // found it
    } else
      m = j; // first j cannot have a solution
    r = popcount(lower(x, m));
    j -= r; // new target
    pos += m;
    x >>= m;
  }
}

// parenthesis close

// minExcess[i(twidth+1) + j] tells the bit pos where i reaches
// excess -j for the first time, for 0 <= i < 2^twidth, 0 <= j <= twidth
static byte *minExcess = NULL;

// creates minExcess table

extern void prepareClose(void) {
  u64 i, n;
  int e, j;
  u32 k;
  byte *ptr;

  n = ((u64)1) << twidth;
  minExcess = (byte *)malloc(n * (twidth + 1));
  if (minExcess == NULL) {
    fprintf(stderr, "Error: could not allocate %li bytes\n", n * (twidth + 1));
    exit(1);
  }
  ptr = minExcess;
  for (i = 0; i < n; i++) {
    e = 1 - ((i & 1) << 1);
    if (e == -1)
      j = 0; // next cell to write, excess 0 not yet found
    else {
      ptr[0] = ptr[1] = 0;
      j = 2; // 0 and -1 found at zero
    }
    for (k = 0; k < twidth; k++) {
      e += 1 - ((i >> k) & 2);
      if (e >= j)
        ptr[j++] = k + 1; // reached new excess -j
    }
    while (j <= twidth)
      ptr[j++] = twidth; // not reached
    ptr += twidth + 1;
  }
}

// where the ( at x[0] closes, may fail if x is not balanced

extern u32 close(u64 x) {
  u32 pos = 0; // positions already skipped
  u32 r, m;
  int e = 0; // excess sought, later can be only positive
  while (1) {
    if (e <= twidth) // can be found in first block
    {
      m = minExcess[lower(x, twidth) * (twidth + 1) + e];
      if (m < twidth)
        return pos + m; // found it
    } else
      m = e - 1; // first e-1 cannot have a solution
    r = popcount(lower(x, m));
    e += 2 * r - m; // new target
    pos += m;
    x >>= m;
  }
}

/*
Succinct Trees
*/

static const u32 width = 4;

typedef struct {
  u64 topol;  // parenthesis of the tree topology, 1 = (, 0 = )
  u64 labels; // sequence of node labels, 0 means variable leaf
} typeTree;

/*
Unify
*/

// unifies two trees; returns if it could

bool unify(typeTree tree1, typeTree tree2, typeTree *treeUnif) {
  u64 labs, topol, ctopol, clab;
  u32 clpos, lpos, tpos, cpos;
  u32 lab1, lab2;
  u64 topol1, topol2;
  u64 labels1, labels2;
  u32 topolen, lablen;

  labels1 = tree1.labels;
  labels2 = tree2.labels;
  topol1 = tree1.topol;
  topol2 = tree2.topol;
  treeUnif->topol = 0;
  treeUnif->labels = 0;
  topolen = 0;
  lablen = 0;

  while (1) {
    // first see where the labels differ
    labs = labels1 ^ labels2;

    // if they don't, then the topologies must be identical
    if (labs == 0) {
      if (topol1 == topol2) { // note: no need to check lengths
        treeUnif->topol |= topol1 << topolen;
        treeUnif->labels |= labels1 << (lablen * width);
        return true;
      } else
        return false;
    }

    // extract the differing labels
    lpos = lsb(labs) / width; // label position that differs
    lab1 = lower(labels1 >> (width * lpos), width);
    lab2 = lower(labels2 >> (width * lpos), width);

    // if the differing values are nonzero, fail§
    if (lab1 && lab2) {
      // probar con dos arboles con un nodo unknown
      return false;
    }

    // variable substitution seems possible, first check trees are
    // equal up to that point

    // find the preorder pos in tree1
    tpos = preorderselect(topol1, lpos);

    // check that both trees are identical up to tpos
    if (lower(topol1, tpos) != lower(topol2, tpos))
      return false;

    // unify, one label is zero and the other is not
    if (lab1 == 0) { // see where the nonzero subtree closes
      cpos = tpos + close(topol2 >> tpos) + 1;
      // output up to there
      ctopol = lower(topol2, cpos);
      clpos = popcount(ctopol);
      clab = lower(labels2, clpos * width);
      // pass processed input
      topol1 >>= tpos + 2; // to pass the () leaf with the 0
      topol2 >>= cpos;
      labels1 >>= width * (lpos + 1); // to pass the 0
      labels2 >>= width * clpos;
    } else { // lab2 == 0 is symmetric
             // see where the nonzero subtree closes
      cpos = tpos + close(topol1 >> tpos) + 1;
      // output up to there
      ctopol = lower(topol1, cpos);
      clpos = popcount(ctopol);
      clab = lower(labels1, clpos * width);
      // pass processed input
      topol2 >>= tpos + 2; // to pass the () leaf with the 0
      topol1 >>= cpos;
      labels2 >>= width * (lpos + 1); // to pass the 0
      labels1 >>= width * clpos;
    }
    treeUnif->topol |= ctopol << topolen;
    treeUnif->labels |= clab << (lablen * width);
    topolen += cpos;
    lablen += clpos;
  }
}

void debug_print(typeTree tree) {
  u64 num_nodes = popcount(tree.topol);
  printf("Tree:\n  topol=");
  char lparen = '(';
  char rparen = ')';
  u64 x = tree.topol;
  for (size_t i = 0; i < 2 * num_nodes; ++i) {
    printf("%c", (x & 0b1L) ? lparen : rparen);
    x >>= 1;
  }
  printf("\n  labels=");
  u64 labels = tree.labels;
  for (size_t i = 0; i < num_nodes; ++i) {
    u32 label = lower(labels, width);
    labels >>= width;
    if (label < MAX_EV_ID) {
      printf("%u ", label);
    } else {
      printf("0x%" PRIx32 " ", label);
    }
  }
  printf(" (0x%" PRIx64 ")", tree.labels);
  printf("\n");
}

/*
Additional operations
*/

// creates a tree that consists of just one label
typeTree typeTree_singleton(u32 label) {
  return (typeTree){
      .labels = label,
      .topol = 0b01L,
  };
}

bool typeTree_equal(typeTree t1, typeTree t2) {
  return t1.labels == t2.labels && t1.topol == t2.topol;
}

// Creates a subtree using the nodes represented by the parenthesis from i to j.
typeTree typeTree_subtree(typeTree tree, u32 i, u32 j) {
  u32 num_labels_pre = popcount(lower(tree.topol, i));
  u32 num_labels = popcount(lower(tree.topol >> i, j - i));

  u64 topol = lower(tree.topol >> i, j - i);
  u64 labels = lower(tree.labels >> num_labels_pre * width, num_labels * width);

  return (typeTree){
      .labels = labels,
      .topol = topol,
  };
}

/*
Evidence
*/
const u64 Any = 0;
const u64 Int = 1;
const u64 Bool = 2;
const u64 Vec = 3;
const u64 Arrow = 4;
const u64 Tuple = 5;
const u64 Float = 6;

typedef typeTree ev_t;

/*
Values
*/
typedef struct {
  ev_t ev;
  u64 len;
  u64 *vals;
} tuple_t;

typedef struct {
  u64 captured_vals[];
} free_vars_t;

typedef struct {
  ev_t ev;
  u64 fptr;
  free_vars_t *free_vars;
} closure_t;

typedef struct {
  ev_t ev;
  u64 size;
  u64 *vals;
} vec_t;

typedef struct {
  ev_t ev;
  u64 case_id;
  u64 vals[];
} variant_t;

typedef struct {
  ev_t ev;
  double val;
} float_t;

typedef struct {
  ev_t ev;
} header_t;

typedef union value {
  uint64_t imm;
  tuple_t *tuple;
  closure_t *closure;
  vec_t *vec;
  variant_t *variant;
  float_t *float_;
  header_t *header;
} val_t;

u64 print(u64 value);

__attribute__((noreturn)) void error(enum error e) {
  printf("Runtime error, ");
  switch (e) {
  case NotImplemented:
    printf("not implemented\n");
    break;
  case ArrayIndexOutOfBounds:
    printf("array index out of bounds\n");
    break;
  case TypeMismatch:
    printf("type mismatch\n");
    break;
  case UnexpectedValue:
    printf("unexpected value\n");
    break;
  case EvidenceNotJustify:
    printf("evidence does not justify the typing judgement\n");
    break;
  case UnexpectedVariantCase:
    printf("unexpected variant case\n");
    break;
  default:
    printf("unknown error code %d\n", (int)e);
    break;
  };
  exit(e);
}

u64 print_int(u64 val) {
  printf("%" PRIi64, (((i64)val) >> 1));
  return val;
}

u64 print_bool(u64 val) {
  if (val == BOOL_FALSE) {
    printf("false");
  } else if (val == BOOL_TRUE) {
    printf("true");
  } else {
    printf("'%" PRIx64 "'", val);
    error(UnexpectedValue);
  }
  return val;
}

u64 print_vec(u64 val) {
  struct vec *vec = (struct vec *)val;
  printf("<vec>");
  return val;
}

u64 print_closure(u64 val) {
  struct closure *closure_ptr = (struct closure *)val;
  printf("<closure>");
  return val;
}

u64 print_tuple(u64 val) {
  tuple_t *tuple_ptr = (tuple_t *)val;
  u64 length = tuple_ptr->len;
  printf("(");
  for (size_t i = 0; i < length; i++) {
    print(tuple_ptr->vals[i]);
    if (i < length - 1) {
      printf(", ");
    }
  }
  printf(")");
  return val;
}

u64 print_float(u64 val) {
  float_t *flt_ptr = (float_t *)val;
  double value = flt_ptr->val;
  printf("%g", (double)value);
  return val;
}

u64 print_variant(u64 val) {
  struct variant *variant_ptr = (struct variant *)val;
  printf("<variant>");
  return val;
}

u64 print_char(u64 val) {
  char c = (char)val;
  printf("%c", c);
  return val;
}

u64 print(u64 value) {
  val_t val = (val_t)value;
  if (val.imm & INT_MASK) {
    print_int(value);
  } else if ((val.imm & BOOL_TAG) == BOOL_TAG) {
    print_bool(value);
  } else {
    u32 tag = lower(val.header->ev.labels, width);
    if (tag == Float) {
      print_float(value);
    } else if (tag == Vec) {
      print_vec(value);
    } else if (tag == Arrow) {
      print_closure(value);
    } else if (tag == Tuple) {
      print_tuple(value);
    } else if (tag < MAX_EV_ID) {
      print_variant(value);
    } else {
      printf("'%" PRIx64 "'", value);
      error(UnexpectedValue);
    }
  }
  printf("\n");
  return value;
}

ev_t ev_of_value(u64 value) {
  if (value & INT_MASK) {
    return typeTree_singleton(Int);
  } else if ((value & BOOL_TAG) == BOOL_TAG) {
    return typeTree_singleton(Bool);
  } else {
    val_t val = (val_t)value;
    return val.header->ev;
  }
}

u64 make_vector(u64 size, u64 initial_value) {
  u64 size_untagged = size >> 1;
  // init ev
  typeTree ev = ev_of_value(initial_value);
  ev.topol <<= 1;
  ev.topol |= 1;
  ev.labels <<= width;
  ev.labels |= Vec;
  // init vals
  val_t *vals = grev_malloc(size_untagged * sizeof(val_t));
  for (u32 i = 0; i < size_untagged; ++i) {
    vals[i].imm = initial_value;
  }
  // init vec
  vec_t *vec = grev_malloc(sizeof(vec_t));
  vec->ev = ev;
  vec->size = size_untagged;
  vec->vals = (u64 *)vals;
  return (u64)vec;
}

u64 vector_get(u64 vector, u64 idx) {
  vec_t *vec = (vec_t *)vector;
  u64 idx_untagged = idx >> 1;
  if (idx_untagged < 0 || idx_untagged >= vec->size) {
    error(ArrayIndexOutOfBounds);
  }
  return vec->vals[idx_untagged];
}

u64 vector_set(u64 vector, u64 idx, u64 val) {
  vec_t *vec = (vec_t *)vector;
  u64 idx_untagged = idx >> 1;
  if (idx_untagged < 0 || idx_untagged >= vec->size) {
    error(ArrayIndexOutOfBounds);
  }
  vec->vals[idx_untagged] = val;
  return vector;
}

u64 vector_length(u64 vector) {
  vec_t *vec = (vec_t *)vector;
  u64 size_tagged = (vec->size << 1) | INT_MASK;
  return size_tagged;
}

u64 make_variant(u64 id, u64 case_id, u64 num_args) {
  variant_t *variant = (variant_t *)grev_malloc(
      sizeof(variant_t) + sizeof(variant->vals[0]) * num_args);
  variant->ev = typeTree_singleton(id);
  variant->case_id = case_id;
  return (u64)variant;
}

u64 make_float(double f) {
  float_t *ptr = (float_t *)grev_malloc(sizeof(float_t));
  ptr->ev = typeTree_singleton(Float);
  ptr->val = f;
  return (u64)ptr;
}

u64 make_tuple(u64 len, u64 *vals) {
  // allocate tuple
  tuple_t *tuple = (tuple_t *)grev_malloc(sizeof(tuple_t));
  tuple->len = len;
  tuple->vals = vals;

  typeTree ev = {0};

  // build evidence
  for (int i = len - 1; i >= 0; --i) {
    typeTree ev_arg = ev_of_value(tuple->vals[i]);
    u32 num_nodes = popcount(ev_arg.topol);
    ev.topol <<= num_nodes * 2;
    ev.topol |= ev_arg.topol;
    ev.labels <<= num_nodes * width;
    ev.labels |= ev_arg.labels;
  }
  ev.topol <<= 1;
  ev.topol |= 1;
  ev.labels <<= width;
  ev.labels |= Tuple;

  tuple->ev = ev;
  return (u64)tuple;
}

u64 read_int() {
  i64 val;
  scanf("%" SCNi64, &val);
  return (val << 1) | INT_MASK;
}

u64 read_float() {
  double val;
  scanf("%lf", &val);
  return make_float(val);
}

u64 read_char() {
  char c;
  scanf(" %c", &c);
  return (u64)c << 1 | INT_MASK;
}

u64 tuple_get(u64 value, int64_t idx) {
  val_t val = (val_t)value;
  return val.tuple->vals[idx];
}

u64 allocate_closure(void *fptr, u64 num_captured_vals) {
  free_vars_t *free_vars = NULL;
  // allocate free vars
  if (num_captured_vals > 0) {
    free_vars = (free_vars_t *)grev_malloc(
        sizeof(free_vars_t) +
        num_captured_vals * sizeof(free_vars->captured_vals[0]));
  }
  // allocate closure
  closure_t *closure = (closure_t *)grev_malloc(sizeof(closure_t));
  closure->fptr = (u64)fptr;
  closure->free_vars = free_vars;
  return (u64)closure;
}

ev_t interior(ev_t ev1, ev_t ev2) {
  ev_t result;
  if (!unify(ev1, ev2, &result)) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  return result;
}

u64 ascribe_int(u64 value) {
  if (value & INT_MASK) {
    return value;
  } else {
    error(EvidenceNotJustify);
    exit(-1);
  }
}

u64 ascribe_bool(u64 value) {
  if ((value & BOOL_TAG) == BOOL_TAG) {
    return value;
  } else {
    error(EvidenceNotJustify);
    exit(-1);
  }
}

u64 ascribe_imm_evidence(u64 value, u64 tag) {
  val_t val = (val_t)value;
  if (val.imm & INT_MASK) {
    error(EvidenceNotJustify);
    exit(-1);
  } else if ((val.imm & BOOL_TAG) == BOOL_TAG) {
    error(EvidenceNotJustify);
    exit(-1);
  } else {
    u64 id = lower(val.header->ev.labels, width);
    if (id == tag) {
      return value;
    } else {
      error(EvidenceNotJustify);
      exit(-1);
    }
  }
}

u64 ascribe_vec(u64 value, u64 labels, u64 topol) {
  val_t val = (val_t)value;
  if (val.imm & INT_MASK) {
    error(EvidenceNotJustify);
    exit(-1);
  } else if ((val.imm & BOOL_TAG) == BOOL_TAG) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  ev_t inner_ev = {
      .labels = labels,
      .topol = topol,
  };
  ev_t ev_reference = {
      .topol = (inner_ev.topol << 1) | 1,
      .labels = (inner_ev.labels << width) | Vec,
  };
  vec_t *new_vec = grev_malloc(sizeof(vec_t));
  *new_vec = *val.vec;
  new_vec->ev = interior(new_vec->ev, ev_reference);
  return (u64)new_vec;
}

u64 ascribe_closure(u64 value, u64 labels, u64 topol) {
  val_t val = (val_t)value;
  if (val.imm & INT_MASK) {
    error(EvidenceNotJustify);
    exit(-1);
  } else if ((val.imm & BOOL_TAG) == BOOL_TAG) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  ev_t ev = {
      .labels = labels,
      .topol = topol,
  };
  closure_t *new_closure = grev_malloc(sizeof(closure_t));
  *new_closure = *val.closure;
  new_closure->ev = interior(new_closure->ev, ev);
  return (u64)new_closure;
}

u64 ascribe_tuple(u64 value, u64 labels, u64 topol) {
  val_t val = (val_t)value;
  if (val.imm & INT_MASK) {
    error(EvidenceNotJustify);
    exit(-1);
  } else if ((val.imm & BOOL_TAG) == BOOL_TAG) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  ev_t ev = {
      .labels = labels,
      .topol = topol,
  };
  tuple_t *new_tuple = grev_malloc(sizeof(tuple_t));
  *new_tuple = *val.tuple;
  new_tuple->ev = interior(new_tuple->ev, ev);
  return (u64)new_tuple;
}

u64 ascribe_value(u64 value, typeTree ev_reference) {
  u32 tag = lower(ev_reference.labels, width);
  if (tag == Any) {
    return value;
  } else if (tag == Int) {
    return ascribe_int(value);
  } else if (tag == Bool) {
    return ascribe_bool(value);
  } else if (tag == Vec) {
    return ascribe_vec(value, ev_reference.labels >> width,
                       ev_reference.topol >> 1);
  } else if (tag == Arrow) {
    return ascribe_closure(value, ev_reference.labels, ev_reference.topol);
  } else if (tag == Tuple) {
    return ascribe_tuple(value, ev_reference.labels, ev_reference.topol);
  } else {
    return ascribe_imm_evidence(value, tag);
  }
}

u64 ascribe_value2(u64 value, u64 topol, u64 labels) {
  return ascribe_value(value, (typeTree){.topol = topol, .labels = labels});
}

typedef struct {
  typeTree *tree;
  u32 i;
  u32 stop;
} typeTree_iter;

typeTree_iter typeTree_children_begin(typeTree *tree) {
  typeTree_iter iter = {0};
  iter.tree = tree;
  iter.i = 1;
  iter.stop = close(tree->topol) + 1;
  return iter;
}

// alternative to begin
void typeTree_children_init(typeTree_iter *iter_ptr, typeTree *tree_ptr) {
  *iter_ptr = typeTree_children_begin(tree_ptr);
}

u32 typeTree_iter_get_i(typeTree_iter *iter) { return iter->i; }

bool typeTree_children_has_next(typeTree_iter *iter) {
  return iter->i < iter->stop;
}

typeTree typeTree_children_next(typeTree_iter *iter) {
  u32 i = iter->i;
  u32 j = i + close(iter->tree->topol >> i) + 1;
  typeTree subtree = typeTree_subtree(*iter->tree, i, j);
  iter->i = j;
  return subtree;
}

u32 typeTree_children_next_j(typeTree_iter *iter) {
  u32 i = iter->i;
  u32 j = i + close(iter->tree->topol >> i) + 1;
  iter->i = j;
  return j;
}

u64 ascribe_arg(u64 arg, typeTree_iter *iter) {
  if (!typeTree_children_has_next(iter)) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  return ascribe_value(arg, typeTree_children_next(iter));
}

void assert_arrow(typeTree *tree) {
  uint64_t root_label = lower(tree->labels, width);
  if (root_label != Arrow) {
    error(EvidenceNotJustify);
    exit(-1);
  }
}

void assert_single_type_remaining(typeTree_iter *iter) {
  if (!typeTree_children_has_next(iter)) {
    error(EvidenceNotJustify);
    exit(-1);
  }
  u32 i = iter->i;
  u32 j = i + close(iter->tree->topol >> i) + 1;
  if (j + 1 != iter->stop) {
    error(EvidenceNotJustify);
    exit(-1);
  }
}

void preamble() {
  prepareClose();
  prepareSelect();
}

u64 print_time(u64 *ptr) {
  closure_t *closure = (closure_t *)ptr;
  u64 (*fptr)(u64 *, u64) = (u64 (*)(u64 *, u64))closure->fptr;

  struct timespec start, end;
  clock_gettime(CLOCK_MONOTONIC, &start);

  fptr(ptr, INT_ZERO);

  clock_gettime(CLOCK_MONOTONIC, &end);

  double elapsed =
      (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;
  fprintf(stderr, "Execution time: %.6f seconds\n", elapsed);

  return INT_ZERO;
}
