// code for MAF
struct Task1aAutomated@m@n{};

void Task1aAutomated@m@n.funct(int@m[public n] alice_data, int@m[public n] bob_data,
      int@m[public n] ret, public int@m total_instances) {
   int@m total = total_instances;
   int@m half = total_instances / 2;
   for(public int32 i = 0; i < n; i = i + 1) {
      ret[i] = alice_data[i] + bob_data[i];
      if(ret[i] > half)
         ret[i] = total - ret[i];
   }
}



//code for chi square test
struct Task1bAutomated@n{};

float32[public n] Task1bAutomated@n.func(
      float32[public n][public 3] alice_case, float32[public n][public 3] alice_control,
      float32[public n][public 3] bob_case, float32[public n][public 3] bob_control) {
   float32[public n] ret;

   for(public int32 i = 0; i < n; i = i + 1) {
      float32 a = alice_case[i][0] + bob_case[i][0];
      float32 b = alice_case[i][1] + bob_case[i][1];

      float32 c = alice_control[i][0] + bob_control[i][0];
      float32 d = alice_control[i][1] + bob_control[i][1];

      float32 g = a + c, k = b + d;
      float32 tmp = a*d - b*c;
      tmp = tmp*tmp;
      ret[i] = tmp / (g * k);
   }
   return ret;
}


//code for oblivious merge
// m : bit length of every entry
// n : bit length of the result
struct Task2Automated@m@n{};

int32 Task2Automated@m@n.funct(int@m[public n] key) {
   this.obliviousMerge(key, 0, n);
   int32 ret = 1;
   for(public int32 i = 1; i < n; i = i + 1) {
      if(key[i-1] != key[i])
         ret = ret + 1;
   }
   return ret;
}

void Task2Automated@m@n.obliviousMerge(int@m[public n] key, public int32 lo, public int32 l) {
   if (l > 1) {
      public int32 k = 1;
      while (k < l) k = k << 1;
      k = k >> 1;
      for (public int32 i = lo; i < lo + l - k; i = i + 1)
         this.compare(key, i, i + k);
      this.obliviousMerge(key, lo, k);
      this.obliviousMerge(key, lo + k, l - k);
   }
}

void Task2Automated@m@n.compare(int@m[public n] key, public int32 i, public int32 j) {
   int@m tmp = key[j];
   int@m tmp2 = key[i];
   if( key[i] < key[j] )
      tmp = key[i];
   tmp = tmp ^ key[i];
   key[i] = tmp ^ key[j];
   key[j] = tmp ^ tmp2;
}


//code solution based on bloom fitler
struct Pair< T1, T2 > {
   T1 left;
   T2 right;
};

struct bit {
   int1 v;
};

struct Int@n {
   int@n v;
};

struct BF_circuit{};

Pair< bit, Int@n > BF_circuit.add@n(int@n x, int@n y) {
   bit cin;
   Int@n ret;
   bit t1, t2;
   for(public int32 i=0; i< n; i = i+1) {
      t1.v = x$i$ ^ cin.v;
      t2.v = y$i$ ^ cin.v;
      ret.v$i$ = x$i$ ^ t2.v;
      t1.v = t1.v & t2.v;
      cin.v = cin.v ^ t1.v;
   }
   return Pair{bit, Int@n}(cin, ret);
}

int@log(n+1) BF_circuit.countOnes@n(int@n x) {
   if(n==1) return x;
   int@log(n-n/2+1) first = this.countOnes@(n/2)(x$0~n/2$);
   int@log(n-n/2+1) second = this.countOnes@(n-n/2)(x$n/2~n$);
   Pair< bit, Int@log(n-n/2) > ret = this.add@log(n-n/2+1)(first, second);

   int@log(n+1) r = ret.right.v;
   r$log(n+1)-1$ = ret.left.v;
   return r;
}

int@log(n+1) BF_circuit.merge@n(int@n x, int@n y) {
   int@n tmp;
   for(public int32 i = 0; i < n; i = i +1 ) {
      tmp$i$ = x$i$ | y$i$;
   }
   return this.countOnes@n(tmp);
}