BKZ_reduction.cpp

#include<iostream>
#include <vector>
#include <cmath>
#include<random>
#include<time.h>
#include<tuple>
#include<NTL/ZZ.h>
#include<NTL/mat_ZZ.h>
#include<NTL/matrix.h>
#include<NTL/vector.h>
#include<NTL/LLL.h>
#define EPSILON 1e-6
/*
~$ g++ -O3 -o BKZ BKZ_reduction.cpp -lntl -lgmp -lm
~$ ./BKZ
*/

using namespace std;
using namespace NTL;

//単位行列の作成
vector<vector<double>> identity_mat(int n){
  vector<vector<double>> A(n, vector<double>(n));
  for(int i = 0; i < n; i++){
    A.at(i).at(i) = 1.0;
  }
  return A;
}

//行列の表示
void print_mat(vector<vector<auto>> A){
  cout << "[\n";
  for(int i = 0; i < A.size(); i++){
    cout << "[";
    for(int j = 0; j < A.at(0).size(); j++) cout << A.at(i).at(j) << " ";
    cout << "]" << endl;
  }
  cout << "]\n";
}

//vectorの表示
void print_vec(vector<auto> v){
  cout << "[";
  for(int i = 0; i < v.size(); i++) cout << v.at(i) << " ";
  cout << "]\n";
}

//内積
double dot(vector<double> x, vector<double> y)
{
  double z = 0.0;
  for(int i = 0; i < x.size(); i++){
    z += x.at(i) * y.at(i);
  }
  return z;
}

//転置行列
vector<vector<double>> trans(vector<vector<double>> A)
{
  vector<vector<double>> B(A.at(0).size(), vector<double>(A.size()));
  for(int i = 0; i < A.at(0).size(); i++){
    for(int j = 0; j < A.size(); j++) B.at(i).at(j) = A.at(j).at(i);
  }
  return B;
}

//行列式
double det(vector<vector<double>> A){
  int n = A.size();
  double det = 1.0, buf;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(i < j){
        buf = A.at(j).at(i) / A.at(i).at(i);
        for(int k = 0; k < n; k++) A.at(j).at(k) -= A.at(i).at(k) * buf;
      }
    }
  }
  for(int i = 0; i < n; i++) det *= A.at(i).at(i);
  return det;
}

//行列の積
vector<vector<double>> mul_mat(vector<vector<double>> A, vector<vector<double>> B)
{
  int n = A.size(), m = B.at(0).size();
  vector<vector<double>> C(n, vector<double>(m));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      for(int k = 0; k < B.size(); k++) C.at(i).at(j) += A.at(i).at(k) * B.at(k).at(j);
    }
  }
  return C;
}

//Gram_Schmidtの直交化
tuple<vector<vector<double>>, vector<vector<double>>> Gram_Schmidt(vector<vector<double>> b)
{
  int n = b.size(), m = b.at(0).size();
  vector<vector<double>> GSOb(n, vector<double>(m));
  vector<vector<double>> mu = identity_mat(n);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++) GSOb.at(i).at(j) = b.at(i).at(j);
    for(int j = 0; j < i; j++){
      mu.at(i).at(j) = dot(b.at(i), GSOb.at(j)) / dot(GSOb.at(j), GSOb.at(j));
      for(int k = 0; k < m; k++) GSOb.at(i).at(k) -= mu.at(i).at(j) * GSOb.at(j).at(k);
    }
  }
  return forward_as_tuple(GSOb, mu);
}

//二乗normの作成
vector<double> make_square_norm(vector<vector<double>> GSOb){
  vector<double> B(GSOb.size());
  for(int i = 0; i < GSOb.size(); i++) B.at(i) = dot(GSOb.at(i), GSOb.at(i));
  return B;
}

//体積
double vol(vector<vector<double>> b){
  double v = 1.0;
  vector<vector<double>> GSOb, mu;
  tie(GSOb, mu) = Gram_Schmidt(b);
  for(int i = 0; i < b.size(); i++) v *= sqrt(dot(GSOb.at(i), GSOb.at(i)));
  return v;
}

//LLL簡約（using NTL）
vector<vector<double>> LLL_reduce(vector<vector<double>> b, double delta){
  int n = b.size(), m = b.at(0).size();
  int v = vol(b) * vol(b);
  ZZ det2 = to_ZZ(v);
  Mat<ZZ> c; c.SetDims(n, m);
  for(long i = 0; i < n; i++){
    for(long j = 0; j < m; j++) c[i][j] = to_ZZ((double)b.at(i).at(j));
  }
  LLL_FP(c, delta);
  for(long i = 0; i < n; i++){
    for(long j = 0; j < m; j++) b.at(i).at(j) = to_double(c[i][j]);
  }
  return b;
}

//Randomな正方正則行列を作成する。
vector<vector<double>> random_mat(int n){
  vector<vector<double>> A(n, vector<double>(n));
  for(int i = 0; i < n; i++) A.at(i).at(i) = 1;
  for(int i = 0; i < n; i++) A.at(i).at(0) = (2 * (rand() % 2) - 1) * (rand() % 100);
  return A;
}

//係数vectorを格子に変換
vector<double> coef2lat(vector<double> v, vector<vector<double>> b){
  vector<double> x(b.at(0).size());
  for(int i = 0; i < b.size(); i++){
    for(int j = 0; j < b.at(0).size(); j++) x.at(j) += v.at(i) * b.at(i).at(j);
  }
  return x;
}

//射影格子の基底の出力
vector<vector<double>> project_basis(int k, int l, vector<vector<double>> b){
  int n = b.size(), m = b.at(0).size();
  vector<vector<double>> GSOb, mu, pi_b(l - k + 1, vector<double>(m));
  tie(GSOb, mu) = Gram_Schmidt(b);
  for(int i = k; i < l + 1; i++){
    for(int j = k; j < n; j++){
      for(int h = 0; h < m; h++) pi_b.at(i - k).at(h) += (dot(b.at(i), GSOb.at(j))) / dot(GSOb.at(j), GSOb.at(j)) * GSOb.at(j).at(h);
    }
  }
  return pi_b;
}

//与えられた上階より小さいvectorの数え上げ
vector<double> ENUM(vector<vector<double>> mu, vector<double> B, double R){
  int n = B.size();
  vector<vector<double>> sigma(n + 2, vector<double>(n + 1));
  vector<int> r(n + 1), w(n + 1);
  vector<double> c(n + 1), rho(n + 2);
  vector<double> x(n), v(n + 1);
  int k = 1, last_nonzero = 1;
  v.at(1) = 1;
  for(int i = 0; i < n + 1; i++) r.at(i) = i;
  
  while(1){
    rho.at(k) = rho.at(k + 1) + (v.at(k) - c.at(k)) * (v.at(k) - c.at(k)) * B.at(k - 1);
    if((rho.at(k) < R * R) || (fabs(rho.at(k) - R * R) <= EPSILON)){
      if(k == 1){
        for(int i = 0; i < n; i++) x.at(i) = v.at(i + 1);
        return x;
      }
      k--;
      r.at(k - 1) = max(r.at(k - 1), r.at(k));
      for(int i = r.at(k) ; i >= k + 1; i--){
        sigma.at(i).at(k) = sigma.at(i + 1).at(k) + mu.at(i - 1).at(k - 1) * v.at(i);
      }
      c.at(k) = -sigma.at(k + 1).at(k);
      v.at(k) = round(c.at(k));
      w.at(k) = 1;
    }else{
      k ++;
      if(k == n + 1){
        v.clear();
        return v;
      }
      r.at(k - 1) = k;
      if(k >= last_nonzero){
        last_nonzero = k;
        v.at(k)++;
      }else{
        if((v.at(k) > c.at(k)) && (fabs(v.at(k) - c.at(k)) > EPSILON)){v.at(k) -= (double)w.at(k);}else{v.at(k) += (double)w.at(k);}
        w.at(k)++;
      }
    }
  }
}

//最短vectorの数え上げ
vector<double> ENUM_all(vector<vector<double>> mu, vector<double> B, double R, double eps){
  int n = B.size();
  vector<double> ENUM_v(n), pre_ENUM_v(n);
  while(1){
    for(int i = 0; i < n; i++) pre_ENUM_v.at(i) = ENUM_v.at(i);
    ENUM_v = ENUM(mu, B, R);
    if(ENUM_v.empty()) return pre_ENUM_v;
    R *= eps;
    //cout << R <<endl;
  }
}

//BKZ-reduction
vector<vector<double>> BKZ(vector<vector<double>> b, int beta, double delta){
  int n = b.size(), m = b.at(0).size();
  double R, eps = 0.99;
  b = LLL_reduce(b, delta);
  int z = 0, k = 0, h, l;
  while(z < n - 1){
    k = k % (n - 1) + 1;
    l = min(k + beta - 1, n);
    h = min(l + 1, n);
    vector<double> w(l - k + 1), v(m);
    vector<double> s(m);
    vector<vector<double>> GSOb, mu; tie(GSOb, mu) = Gram_Schmidt(b);
    vector<double> B = make_square_norm(GSOb);
    vector<vector<double>> proj_b = project_basis(k - 1, l - 1, b);
    vector<vector<double>> proj_GSOb, proj_mu; tie(proj_GSOb, proj_mu) = Gram_Schmidt(proj_b);
    vector<double> proj_B = make_square_norm(proj_GSOb);
    R = sqrt(proj_B.at(0));
    while(dot(w, w) == 0){
      w = ENUM_all(proj_mu, proj_B, R, eps);
      R++;
    }
    for(int i = 0; i < l - k + 1; i++){
      for(int j = 0; j < m; j++){
        v.at(j) += w.at(i) * b.at(i + k - 1).at(j);
        s.at(j) += w.at(i) * proj_b.at(i).at(j);
      }
    }
    if((B.at(k - 1) > dot(s, s)) && (fabs(B.at(k - 1) - dot(s, s)) > EPSILON)){
      z = 0;
      vector<vector<double>> c(h + 1, vector<double>(m));
      for(int i = 0; i < k - 1; i++) c.at(i) = b.at(i);
      c.at(k - 1) = v;
      for(int i = k; i < h + 1; i++) c.at(i) = b.at(i - 1);
      c = LLL_reduce(c, delta);
      for(int i = 1; i < h + 1; i++) b.at(i - 1) = c.at(i);
    }else{
      z++;
      b = LLL_reduce(b, delta);
    }
    //cout << "z = " << z << endl;
  }
  return b;
}

bool check_HKZ(vector<vector<double>> b){
  int n = b.size(), m = b.at(0).size();
  double R;
  vector<vector<double>> GSOb, mu;
  tie(GSOb, mu) = Gram_Schmidt(b);
  for(int i = 0; i < n; i++){
    vector<vector<double>> proj_b = project_basis(i, n - 1, b);
    vector<vector<double>> proj_GSOb, proj_mu;
    tie(proj_GSOb, proj_mu) = Gram_Schmidt(proj_b);
    vector<double> B = make_square_norm(proj_GSOb);
    R = sqrt(dot(proj_b.at(0), proj_b.at(0)));
    vector<double> coef_vec;
    while(dot(coef_vec, coef_vec) == 0){
      coef_vec = ENUM_all(proj_mu, B, R, 0.99);
      R++;
    }
    vector<double> lat_vec(m);
    for(int j = 0; j < n - i; j++){
      for(int k = 0; k < m; k++){
        lat_vec.at(k) += coef_vec.at(j) * proj_b.at(j).at(k);
      }
    }
    if(fabs(dot(GSOb.at(i), GSOb.at(i)) - dot(lat_vec, lat_vec)) > EPSILON){
      cout << "##########################################\n";
      cout << i << endl; print_vec(GSOb[i]); print_vec(lat_vec);
      cout << dot(GSOb.at(i), GSOb.at(i)) - dot(lat_vec, lat_vec) << endl;
      cout <<"###########################################\n";
      return false;
    }
  }
  return true;
}


bool check_BKZ(vector<vector<double>> b, int beta){
  int n = b.size(), m = b.at(0).size();
  for(int i = 0; i < n - beta + 1; i++){
    vector<vector<double>> proj_b = project_basis(i, beta + i - 1, b);
    if(not check_HKZ(proj_b)) return false;
  }
  return true;
}

vector<double> SVP_BKZ(vector<vector<double>> b, int beta1, double delta, double norm){
  //vector<vector<double>> BKZb;
  for(int i = beta1; i <= b.size(); i++){
    b = BKZ(b, i, 0.99);
    cout << "processing\n" << "block size = " << i << "\n" << "BKZb_" << i << " = ";
    print_vec(b.at(0));
    if(dot(b.at(0), b.at(0)) <= norm * norm){
      cout << i << endl;
      return b.at(0);
    }
  }
}

int main(){
  vector<vector<double>> b, BKZb;
  vector<double> sv;
  bool random;
  int n, beta;
  double delta;
  cout << "Random?" <<endl;
  cin >> random;
  if(random){
    cout << "lattice dimension：" << endl;
    cin >> n;
    b = random_mat(n);
  }else{
    //SVP-challenge
    cout << "lattice dimension: " << endl;
    cin >> n;
    //50次元：OK(55秒、beta=28)
    if(n == 50){
      b = {{-248, 715, -114, -530, 176, -231, 215, -142, 18, 247, -147, 227, 181, -185, -458, 742, 339, -444, 373, 154, 290, -281, 37, -3, -262, 12, -156, 64, -275, 618, 286, 71, 255, 166, -5, 116, 271, -188, 10, 385, 165, 242, 215, -331, 20, -222, 146, -543, 209, -177}, 
{-123, -12, 574, -279, -80, -3, -33, -238, 100, -349, -134, -393, 388, -113, 340, 48, 83, 40, 407, -679, 638, 17, -27, -482, -148, 112, -219, 243, -737, 130, 264, 81, 491, 167, 610, -189, 875, 254, 168, -34, -338, -456, 356, -419, -178, -246, -132, -38, 106, -1}, 
{722, -296, -134, 761, 37, 90, -87, 152, -279, -973, 496, -147, -207, 210, -21, -177, 332, -91, -91, -377, 128, 229, -15, -527, 417, -117, -8, 487, 2, 12, 18, -4, -289, 313, 169, -80, 628, 10, 427, 271, 216, -1219, 159, -489, -238, -343, 91, -185, -142, -125}, 
{-173, -750, 97, 299, -558, 350, 212, -348, 256, -469, 602, 299, -191, -44, 966, -111, 734, -349, 557, -319, -404, 113, 188, -298, 281, 176, 547, 197, -536, 358, -443, -398, -181, -111, 155, 104, -76, 399, 413, 414, 119, -274, 49, -108, -472, -327, -4, -102, 291, 2}, 
{-205, -155, 415, 386, -2, -255, -175, 92, 868, -204, -422, 271, -23, -196, 643, -366, 1189, 34, 788, -307, 238, 8, -208, -226, 717, 619, 163, 103, -1005, 10, -68, 325, -168, -702, 393, -431, -7, 342, -37, -755, -301, 472, 144, -29, -322, -114, -18, -12, 106, -1}, 
{-61, 178, -409, -529, 89, -649, -186, 404, 111, 581, -266, -72, 884, -426, 459, -54, 725, -96, 427, 325, -270, -303, 71, 859, 482, 300, -194, 546, -350, -78, -19, 106, -2, -310, -279, -503, -707, 23, 642, -204, 35, 1028, -63, 542, 179, 389, -357, -234, 98, 121}, 
{-272, -265, 173, -410, 19, -655, -130, -202, 382, 120, 80, -230, 427, -228, 805, -241, 172, 237, -75, -780, -498, 197, 672, 522, -404, 228, 251, 169, 121, -338, 121, -587, -488, -550, -197, 49, -914, 130, 629, 214, -434, -263, 19, 664, 340, -28, 72, 305, 63, 184}, 
{7, 33, 113, -475, -69, -311, 56, 770, 397, 595, -66, -125, 226, -661, 126, -44, 596, 15, 876, 576, 54, 40, -625, 662, 695, -43, 64, 44, -761, -464, -797, 93, 276, 25, -81, 332, -606, -42, -337, -259, 230, 1036, 214, 192, -512, 2, -532, -6, 271, 123}, 
{-615, 304, 130, -439, -170, -317, 585, -27, 186, -11, -96, -10, -124, 419, -426, 3, -624, -165, -351, -72, 974, 269, -274, -295, -180, -363, 152, 179, -254, 51, 146, -27, 435, 313, 107, 467, 234, -231, -523, 818, -324, 19, 359, -490, -657, 213, -321, -335, 280, -59}, 
{183, 200, 85, -10, 379, -141, -132, 49, 559, 282, 213, 572, -666, -99, 216, 283, 56, -399, 231, -258, -365, -680, 271, 84, -264, 864, -164, -407, 312, -101, 575, -320, 247, -939, -67, 24, -202, -158, -266, -984, 226, 288, -163, 197, 327, 30, 448, -37, -105, -117}, 
{10, -391, -94, -10, 691, 93, -59, 181, 5, -252, -75, 273, -58, 73, 1006, -662, -342, 17, 249, -188, -254, -229, -237, -187, -71, 61, -422, 113, -210, -99, 186, -367, 121, -208, 77, -373, -51, 604, 192, -896, -146, 316, 15, -10, -145, 313, 288, -544, -43, 89}, 
{226, -357, -538, -84, -909, 17, -181, 648, -84, -72, 450, -143, -147, -122, 63, 225, 424, -492, 933, 97, 210, 273, 5, 223, 360, 368, 450, 522, -133, -127, -278, -214, 764, -463, -230, 190, -171, -599, -43, 237, -161, 93, 43, -181, -455, 565, -316, -314, 525, -152}, 
{-528, 43, 129, -383, -105, 517, 285, 382, 379, 363, 44, -10, -36, 233, 172, 86, 658, -58, 742, 61, 499, 801, -490, -401, 318, 209, 2, -83, -849, 492, -272, 536, 846, -151, 70, -190, 204, 492, 48, 59, -258, 305, 263, -593, 162, 297, -466, -304, 554, -127}, 
{122, 200, 259, 14, -8, 166, 466, -263, -255, 213, -359, 307, -76, 269, 419, 360, -264, -794, 296, 139, -46, -699, 605, 148, 24, -129, -359, 13, -521, 522, -357, -383, -597, 555, 70, -373, 73, 377, 250, 674, 228, 558, -80, 266, -495, -162, -3, -648, -125, 69}, 
{538, 34, 176, 138, 24, -130, 256, 225, 362, -283, 219, -173, -602, 254, 326, -196, -309, -374, 489, -178, 198, -427, -304, 81, 284, 22, -502, 505, -141, 203, -153, -390, 67, 580, 316, -396, 668, 141, -527, -578, -403, -567, -116, -250, -818, -409, 185, -98, -114, 160}, 
{169, 205, -464, 682, 87, -85, 483, -387, 171, 16, -288, 176, 105, -363, 1, 416, 278, 88, 619, -69, -703, -97, 88, 662, -430, -336, -50, 336, 182, 859, -228, -284, -511, 239, -202, 109, 161, 114, 479, 84, -246, -195, 286, -191, -64, -449, 980, -560, 245, -23}, 
{-684, 158, -480, -828, 37, 350, -267, 195, -298, -373, -124, -13, 929, -593, 323, 431, 403, 421, 768, 829, -194, -23, -231, 154, -444, -337, 215, -279, -621, 194, -517, -292, 550, 399, -70, 60, 16, 161, 311, -331, 619, 498, 256, -104, -388, 517, -143, -176, 348, -38}, 
{511, -198, 420, 1166, -516, -123, 455, 232, 294, -33, -44, -68, 27, 354, -84, -516, 216, 268, 132, -245, 300, -161, -205, 190, 437, 58, 214, -62, -1060, -212, -641, 547, -200, 161, -203, -263, 182, 283, -316, -216, 148, -411, 26, -84, -906, -513, -787, 575, -164, 179}, 
{339, -187, -407, -201, -510, 426, -210, -196, -305, -112, -124, -23, 606, -246, 269, 679, 106, -353, 199, 580, -229, 291, 425, 512, 230, 382, 102, 341, 214, 692, -269, -184, -692, 109, -50, -707, 734, -324, 508, -157, 82, 58, -123, 545, -19, 502, 44, -12, -86, -11}, 
{49, 143, -43, 427, -142, -127, -43, 240, -199, -371, -151, -226, 488, 27, 276, -311, 1199, 141, -411, 330, -513, -901, 168, 104, 413, 191, -314, 300, -507, 377, 42, 376, 459, 362, -53, -919, 594, -84, 584, -430, -8, -256, -303, -287, -51, 5, -264, 532, -256, 209}, 
{-489, 27, -143, -93, 379, -1063, -160, -371, -39, -576, -584, 332, 811, 197, -445, -166, 963, -357, -257, -498, 485, -1073, 451, -162, 326, 451, -214, 511, -126, 62, 394, 844, -180, -196, -359, -566, -295, -183, 357, 663, 44, 142, 78, -142, -185, -161, -168, -290, -254, -196}, 
{241, -114, -511, 1066, -73, -421, -149, 307, 98, -95, -220, -350, -114, 166, 150, -440, 21, 72, -45, 220, -786, -299, 145, 547, 117, -136, 176, 387, -179, 561, -209, -704, -542, 59, -233, -529, 151, 36, 443, -282, -279, -148, -287, 36, 365, 280, -17, -180, 83, 332}, 
{-297, 677, -706, -139, -282, -1096, -348, 40, 302, 37, -728, 236, 338, 92, 76, 255, -141, -78, 350, 475, 11, 17, -538, 448, -146, 222, 888, 214, 121, 76, 512, -347, 143, -333, -313, -364, -551, -226, -134, -608, 31, 647, 34, 201, 48, 642, -255, -406, 283, -53}, 
{122, 165, -80, -1, 61, 203, -289, -504, 282, 378, 161, -499, 363, -42, -1000, 306, 666, 59, -275, -662, -54, -171, 89, -138, -839, 451, -101, 167, -222, 631, 203, 406, 19, -69, -214, 346, 673, 43, 217, 246, -340, -680, -119, -612, 816, -916, 250, 205, 222, -37}, 
{-187, 384, -640, -271, -516, 213, 149, -148, -27, 203, 481, 658, -305, 357, 409, -643, 33, -512, -484, 208, -340, -270, 197, 162, -138, -328, -33, 498, -15, 76, 144, -328, -542, 202, -464, -24, -537, 382, 452, 528, -90, 264, -663, 226, -114, -302, 377, -288, -312, 248}, 
{20, 695, -83, -674, 43, -53, 291, 486, -593, -287, -353, 3, 671, -28, -263, 112, -136, -299, 224, 439, 363, 245, -363, -204, -9, -103, 370, 0, -618, -109, 5, 287, 183, 752, 193, 223, 226, 61, -238, 252, 357, -242, 56, -189, -315, 466, -413, -111, 276, -136}, 
{128, -460, 52, 385, -115, -129, -760, 49, -634, -161, -492, -852, 517, -10, 442, -228, -22, 147, 466, -255, 714, 440, -28, 82, -40, -281, 9, 28, -684, -621, -56, -94, 42, 11, 179, -397, -366, 500, 483, -412, -453, 706, -48, 211, -15, 71, -838, -321, 316, -48}, 
{-636, -141, -48, -227, 153, -106, 304, -746, 73, 427, 623, 723, 147, -83, -538, 768, -419, -817, -245, 15, -454, -602, 620, 155, -496, -123, 199, -179, 486, 581, 209, -44, -503, -36, 86, 455, 173, 5, -152, 142, 204, 327, -702, 475, 596, -331, 384, 482, -19, -76}, 
{552, -344, 681, -551, 413, 201, 121, 1030, 286, 384, 57, -485, -47, 144, 932, 402, 787, 316, -91, -379, -400, -294, 363, -45, -111, 14, -590, -339, -161, -844, -501, -284, 79, -167, -3, -3, -666, 310, 442, -219, 361, 504, 403, 424, 320, 349, 18, 440, -244, -23}, 
{-516, -376, -531, 347, -214, 31, -163, -692, 232, -175, 110, 407, 70, -74, -276, -171, 576, -63, 524, 196, 81, -698, 33, -758, 56, 309, 117, -241, -188, 407, -33, 653, -171, -258, 497, -343, -104, -163, -950, -187, 158, 474, -214, -201, -60, 368, 590, 98, 330, -218}, 
{-551, -743, -51, -903, -94, 578, 74, -420, -502, 36, 130, 249, 345, 54, 477, -968, -21, 332, -400, 12, -92, -191, -373, -242, 109, -497, 261, -31, -14, 465, -165, 411, -223, -30, -392, -141, 137, 535, -139, -201, -58, -21, -223, 168, 47, -297, -35, 66, -115, 183}, 
{-64, -316, -421, 232, -538, -792, -366, -14, -231, -84, 290, -432, -171, -266, -176, -518, -656, 219, -288, -30, 245, -21, 336, 537, -353, -562, -83, 581, 546, -568, 53, -466, -550, -407, -385, 252, -765, -601, 244, 214, 127, 323, 84, 480, 456, 399, 278, -568, 235, 192}, 
{266, 436, 113, -658, -244, 245, -93, -349, -202, 280, -387, -138, 552, -514, 252, 408, -121, -111, 369, 321, 116, 131, -456, 726, -29, 343, -462, -145, 165, -357, -13, 22, 557, 677, -219, 176, 516, -476, -58, -333, -101, 547, 102, 46, -97, 99, -333, 107, -302, -198}, 
{-287, -199, 117, 367, 151, 361, 173, -685, 59, 484, -257, 649, -236, 3, -31, 195, -155, 29, -108, -273, -506, -519, 1107, -109, -271, -73, -1, -680, 551, 725, -364, -339, -113, -657, -319, -14, -527, 341, 59, 706, 4, 297, 182, 268, 19, 47, 129, -237, -63, 89}, 
{116, -507, 102, 177, 138, 834, 2, 31, -540, -64, 449, 474, 1, -218, -161, 83, -589, 305, 587, -154, -350, 494, -232, -632, -106, -87, 78, -351, -547, 197, -444, 64, -290, -21, 493, 644, 375, 711, -299, -157, 87, -100, 268, -281, -59, -590, 298, 150, 225, 191}, 
{84, 13, -410, 36, -360, -1116, -410, 635, -179, -115, -114, -391, 402, -607, -156, -756, 73, 540, -233, -117, 24, 110, -212, 232, 327, -196, 392, 14, 108, -502, 367, -125, -451, -179, 438, 185, -91, -807, -299, 225, -662, 44, 116, 551, 510, 127, 80, 236, -95, 383}, 
{290, 533, -626, 877, 393, -450, -426, -18, -162, -317, -274, 117, 6, 251, -392, 121, 172, 749, -70, -172, 331, 715, 8, -58, -100, 71, 202, -53, 485, 168, 190, 648, 52, 296, 2, -988, -250, 231, -41, -609, -717, -413, -10, 1, 54, 44, 357, 109, 13, -131}, 
{-165, -41, 96, -679, 126, 91, 513, -267, -446, 982, -299, 87, 101, -139, 413, -191, 119, -592, 34, 700, -748, 358, -115, 1032, 306, -254, -172, -181, 395, 870, -191, 242, -64, 289, -452, -293, -181, 396, 505, 634, -246, 333, 178, 326, 485, 109, -190, -449, 121, 429}, 
{-181, -30, -193, -395, 48, 767, -42, -233, -400, 667, 139, 197, -18, -147, -614, -35, -348, -302, -466, 669, -122, -431, -264, -275, -288, 129, -251, -524, 760, 761, 27, 466, 349, 655, -70, 127, 401, -654, -441, -139, -238, 220, -821, -134, 1096, 205, 189, 109, -95, -188}, 
{-111, 341, 400, -303, 202, 223, 313, 151, -187, 220, 224, 210, -101, -228, -486, 687, 54, -195, -729, 503, 51, -673, 226, -154, -157, -345, -344, 129, -54, -137, -350, -355, -162, 51, 342, 644, -73, -368, 283, 488, 540, 497, 343, -145, -153, 52, 272, 108, 239, -269}, 
{-225, -847, -112, -216, -427, 161, 4, 175, -179, -542, 818, -675, 495, -421, 518, 15, 333, -100, 301, -21, -462, 583, -570, 97, 527, -730, 33, 656, 409, 96, -853, 69, 23, 676, 76, 118, 237, 391, 254, 454, -82, -935, 250, 364, 516, -197, -226, 191, 412, 307}, 
{-77, 375, 179, 112, -755, 234, -254, -459, 555, 9, -297, 189, 39, -91, -51, -64, 794, 398, 113, 835, 187, 142, -48, 48, -81, 118, 116, -262, -646, -14, -93, 413, 136, -279, -49, -88, -237, 246, 367, -178, 83, 447, -153, -191, -359, -4, -516, 432, -267, 16}, 
{-572, 625, -64, 246, -410, -441, 361, -44, 1474, 456, -267, 280, -339, -28, -206, -22, 538, 272, -80, 326, -142, -47, 100, 1035, 726, -57, 33, 118, -263, -109, -165, -462, -620, -386, 201, -103, -950, -176, -123, 393, -137, 331, 659, 245, -320, -14, -12, 216, -484, 383}, 
{-177, 224, 209, -585, 123, -44, -48, -14, 25, 201, -163, -8, 445, -431, -153, 807, 222, 169, -83, 469, 277, 320, 434, 731, 239, 205, -177, 45, -87, 27, -273, 270, 29, 336, -113, -109, 292, 329, 787, 476, 527, 510, 59, 65, 725, 142, -589, 393, 40, 5}, 
{-898, -284, -710, 33, 47, -769, -207, -343, -388, 365, -154, 801, 557, -246, 113, -105, -89, -55, -26, 727, -176, -68, -271, 645, -71, -771, 296, -205, -537, 649, 27, -224, 178, 44, -509, 329, -72, -559, 248, 527, -341, 1315, 67, -28, -163, 246, 14, -172, 460, 115}, 
{-481, 405, -228, -74, 17, -481, 301, -275, 636, -254, -20, 150, 622, 444, 728, 199, 730, 60, -8, -202, 184, -153, -27, -191, 501, -35, 37, 385, 134, 83, 443, -31, -237, 243, 480, -749, -224, 115, 332, -29, 256, 423, -101, 21, 188, 555, -231, -650, 254, 47}, 
{-643, -270, -418, -169, 154, 157, -112, -885, -687, -26, 7, 6, 327, -368, -625, -550, -529, -481, -562, 669, 129, -478, 156, 46, 482, -297, -13, 473, -119, -42, -155, 166, -187, 766, 372, -1, 207, 83, -83, 378, 141, 369, -88, 362, 272, -28, -69, -30, 144, 268}, 
{271, -5, 414, 699, 12, -754, 437, 246, 326, 203, -773, 535, -621, 261, -262, -181, 354, -255, -317, -344, -83, -707, 3, -69, 318, 472, 114, -503, -136, 511, 0, -92, -101, -247, -41, -210, -607, -70, -531, 280, 298, 334, -65, -77, -396, 2, -282, -359, -309, 402}, 
{-337, 493, -47, -61, -227, -360, 618, 177, 332, 749, -499, 754, 314, -18, 467, -140, 484, -40, 29, 318, -91, -406, -103, 468, 355, 596, 294, 119, -1098, 130, 84, 127, 696, 130, -243, 1, -419, 659, 371, -192, -276, 568, 299, -200, -504, 256, -217, -482, 376, 347}, 
{302, -441, 142, -111, -3, 239, -375, -265, -893, -39, -131, -239, 627, 66, -174, 510, 365, -707, -355, 108, -293, 211, 364, -136, 241, -5, -828, 228, 529, 32, 151, 641, -689, 710, -55, -698, 227, -108, 680, 319, 491, -130, -119, -86, 901, -440, -148, -70, -374, -545}} ;
    }
    if(n == 60){//OK (blocksize=22)
      b = {{28, 83, 556, 413, 619, 366, 495, -152, 392, -25, -197, -241, 203, 899, 359, 708, -11, 300, -392, 122, -721, -213, 561, 704, 417, 143, 155, -489, 751, 502, -66, 366, 295, 148, 490, -337, 138, 246, 360, -59, 1047, -36, -516, -503, 145, 864, -472, 354, 102, -175, 188, -924, 698, -126, 452, -55, -33, 1, 0, 0},
{372, -127, 258, 285, 135, 85, -115, 332, -421, 643, 470, 155, 409, 382, 1013, 1382, 79, 331, -256, 532, 540, -416, 635, 389, 247, -313, 97, -378, 183, 188, -168, -132, 91, 528, -199, -214, 161, 437, -238, -800, -221, -305, -560, 536, 422, 291, -814, -175, 585, -164, 383, 228, 584, -6, 259, -195, 284, -526, -434, -25},
{-688, 507, 604, 55, 78, 572, 739, -199, 569, -767, 98, -1160, -754, -106, -856, -557, -589, 173, 110, -106, -331, -493, -520, -309, -564, -233, 787, -326, 346, 505, 0, 463, -681, 150, -402, 134, -80, -250, 324, 381, 234, -287, -956, -6, -398, 527, 404, 554, 173, 73, -22, -213, 500, 348, 237, 68, -31, -19, 0, 0},
{-247, -749, -229, 315, -474, 611, -1092, 862, -422, 498, 174, 161, 76, -183, 12, -163, -142, 427, -905, 58, 433, -185, 401, -149, -935, 226, 121, 766, -661, 108, -519, -560, -46, 465, -449, -55, -757, 306, -318, -423, -555, -256, -125, 699, -424, 206, 155, 319, 31, 384, 1204, 738, -198, 27, -234, 274, -328, -751, -266, -26},
{567, 672, 365, 52, -160, -348, 596, -351, 8, 455, 553, -237, 476, -523, 712, -99, -216, 424, -248, -48, 904, 148, 166, -199, -108, -1051, -715, -388, 147, -229, 112, 953, 21, 31, 475, 248, 767, -178, -258, -657, -327, -133, -1168, 672, 730, 411, -216, 215, 316, -17, -335, 168, 613, 566, 645, -506, 709, 243, -168, 1},
{-267, 3, -222, 589, -482, 422, -582, -46, 70, -81, 305, 213, 170, 244, 231, -471, 540, 267, -383, -1274, -44, 780, -117, 671, -1105, 542, -596, 192, -928, -257, -126, 324, -63, -308, 655, 210, -409, -1024, -212, -62, -53, 254, 853, -315, 213, -116, 536, 953, -846, 220, 167, -439, -668, -296, 169, 682, -325, 545, 434, 25},
{-24, 309, -547, 157, 442, -280, 469, -756, -191, 355, 365, 786, -188, 213, -83, -76, 241, -9, 594, -295, -781, 96, -310, 716, 109, 130, -409, -706, -752, 187, 671, -132, 84, -375, -15, 47, 297, -570, 180, 1117, 767, 807, 21, -597, 181, -1399, -627, 42, -173, -154, -397, -763, -498, -574, 233, 265, -307, -8, 0, 0},
{-273, -27, 268, -141, 955, 190, -231, 705, 15, 45, -1134, 394, -29, 251, 320, -369, -376, -44, -571, -44, -1219, 559, 43, 124, 271, -435, -1142, 449, 385, 355, 421, -12, 1168, -680, 89, -462, -826, 125, 778, 421, 1176, 248, -583, -710, 37, -105, -178, 221, -526, 379, 280, -538, -90, -576, -339, 164, -490, -228, 168, -1},
{912, -151, -858, -200, 391, -718, 311, -261, -459, 613, 168, 642, -855, -14, -589, 520, 222, 110, 650, 352, 317, -725, 12, 4, 253, 329, 448, 377, -486, -231, -226, -295, 284, 46, -306, 79, 583, 303, 34, 610, -147, -267, 381, 267, 58, -1017, -192, -123, 488, -795, 609, 7, -596, 754, -382, -89, -21, -360, -434, -22},
{304, -429, -537, 16, -475, 322, 35, 287, -474, -681, -10, 76, 44, 412, -476, 42, -541, -185, -343, -78, 861, -88, -211, -280, 106, 386, 957, 257, 103, 81, -453, -273, -1678, 219, -422, 633, -280, -543, 60, -13, -132, -158, 1237, 142, -369, 139, -260, -138, -21, -355, 374, 407, -239, -116, 218, 474, -152, -238, 136, -1},
{-888, 76, 180, -217, -732, 570, 748, -449, 792, -436, 25, -82, -179, 504, -719, -751, -759, 213, -564, 173, -222, 265, -59, -213, -90, 465, 896, -725, 89, -14, 15, 23, -1323, 283, -73, -149, -639, -367, 27, 860, 825, -337, 544, 22, -860, -112, 21, 442, -383, 220, 675, 193, 359, -329, 384, 199, 158, -206, 83, 12},
{-649, 306, 825, 696, 523, 814, -240, 439, -491, -57, 763, -220, 91, -14, 150, 672, 239, 304, -380, -369, -678, -399, -193, 574, -1237, -611, -37, 39, -483, 551, 518, -193, -183, 465, 174, -209, -518, 239, 684, -253, -80, -103, -1643, 21, 10, 9, -85, 238, 512, 390, 32, -213, 557, 143, 37, 425, -1136, -193, -299, -79},
{465, -89, -828, 465, -356, -679, 535, -560, 286, 964, 43, 995, -588, 32, 23, -147, -55, -95, 80, -35, 928, -77, 54, -523, 253, 859, -443, -226, -106, -251, 175, 407, -396, -207, -379, -111, 806, -234, -407, 268, -145, 14, 946, -326, 524, -1178, -617, 113, -548, -899, 109, 318, -501, -24, 604, 326, 352, -45, -24, 3},
{1336, -684, -491, -401, -17, -805, -435, -479, -492, 554, -286, 189, 354, -418, 250, 167, -168, 54, -102, 179, -483, -394, 492, 277, 239, -330, -658, -106, -572, 155, -423, 291, 1245, 55, 98, 163, 553, 808, -630, 19, -253, -20, -1107, 794, 318, 263, -122, 549, 479, 164, 737, 285, 134, 644, 169, -647, 580, -124, -218, 42},
{-151, -1354, 196, 293, 350, 420, -205, -368, 578, -131, -431, -296, -190, 522, 72, -350, -141, 132, -511, 39, -622, -589, 328, -275, 109, 426, 194, 471, 235, -138, -784, 196, 307, 109, 21, -126, -371, 1077, 280, 211, 175, 3, 451, -35, -86, 722, 295, 391, 280, 193, 405, 286, 72, -39, 134, 89, 98, -211, -633, 0},
{-224, -15, 328, 73, 1034, 330, -325, -411, -22, -711, 294, -11, 169, -249, 143, -276, 263, -487, 49, -219, -1037, 53, -662, 162, 23, -153, -123, -476, -679, 56, 938, -286, 437, -403, 131, -1, -585, 104, 626, 387, -113, 804, -172, -825, 319, -198, 690, -468, 267, 1186, -1005, -565, -87, -566, -590, -371, -601, 246, -196, 22},
{-509, -133, 173, 94, 142, 321, -14, 443, 405, 119, -45, -423, 313, 113, 714, 491, 15, -152, -82, 223, -800, -18, 229, 370, 345, 268, -230, 421, 948, -337, -291, -374, 693, 503, 929, -718, -503, 161, 898, -144, 362, 235, 662, -675, 200, 418, -249, -380, -219, 204, -492, -495, 394, -639, 274, 27, -569, 169, -19, -49},
{124, -490, 144, 632, -87, 57, 468, -347, 750, -52, 5, -292, -481, -157, 234, 282, 143, 23, -716, -471, -452, 8, -53, 201, 123, 619, 432, -88, 205, -267, -353, -106, 138, 355, 550, -478, 122, 108, 160, 192, -409, 159, 528, -523, 212, 116, 300, 188, -174, 429, -304, -134, -436, -329, 169, 223, -406, 344, -414, -44},
{928, 130, 277, 59, -24, -625, 970, -973, -290, 904, -800, 132, 14, -90, -266, 501, 1, 712, -126, 191, 329, -143, 399, 340, 494, -488, -77, -163, 460, 313, 26, 399, -56, 296, 306, -151, 1066, 1011, -250, 99, 245, -888, -1402, 151, 196, 35, -888, 64, 120, -582, 412, 365, 397, 675, 259, -245, 605, -321, 21, -26},
{24, 1167, -170, -39, 774, -547, 432, 302, -104, 100, 146, 259, -604, -276, -216, -48, -795, -232, 263, 588, 771, -972, -524, -663, 106, -208, -111, -697, -44, -54, 36, 290, -372, -258, -768, 206, -107, -159, 172, 322, 408, 55, -611, 269, 186, -130, -301, -460, 224, -584, -338, -246, 158, 516, 82, -526, 52, -501, -299, -26},
{-5, 717, 457, -422, 466, 156, 147, 635, 542, -25, -773, -672, 262, -239, 303, 1060, -153, 51, -58, 615, -181, -150, -333, 303, 675, 531, 396, -381, 922, -269, 74, -452, 526, 275, 365, -573, -375, 272, 173, 73, -236, -594, 50, -401, 374, 527, 137, -1119, 331, -5, -388, -88, 121, -264, -611, -530, -212, -161, -143, -69},
{6, 370, -192, 31, -192, -259, -290, 491, -815, 55, 64, -513, -511, -124, -553, -301, -51, 105, 137, -502, 1136, 157, -689, -523, -430, -14, 10, 410, 419, -135, -465, -130, -975, 280, -299, 621, 333, -788, -359, -198, -554, -241, -1, 429, 46, 110, 263, -310, 112, -765, -529, 175, -356, 25, -429, 125, 138, -212, 199, -2},
{667, 147, -713, 102, -582, -323, 97, 156, -632, -403, -263, -234, 1032, -65, 22, 232, 52, -387, 439, -109, 841, -19, 42, 578, 490, 201, 810, -238, 76, -456, -297, -274, -709, 534, 763, 197, 116, 366, 226, -370, -303, 206, 537, -62, 303, 511, -469, -590, -400, -531, -590, 155, 71, 249, 238, -205, -200, 402, 428, -98},
{863, -275, -286, 46, 336, 125, -91, -63, -391, 232, 57, -366, 814, 89, 109, -385, 321, 267, 28, 32, 1229, -227, 91, -677, 308, -235, 105, 274, 558, -235, 299, -10, -599, -205, -148, 550, 693, 6, -625, -845, -764, 312, 375, -85, 882, 620, -138, -264, 466, -300, -452, 338, -99, 15, -310, -330, 1052, 535, 343, 23},
{-331, -221, 949, 187, 276, -657, -146, -899, 358, -388, -239, -188, 81, 364, 153, -45, 212, -858, 469, -1140, -537, 604, -272, -382, 90, 66, -943, -246, 60, -418, 38, 487, 184, -722, 255, 147, 174, 116, -175, 0, -30, 168, 152, -350, -386, 108, 178, -418, -167, 147, -1307, 269, 120, -525, 479, 164, -143, 418, 206, 15},
{-11, -1044, 255, -141, -58, -59, -25, 249, -138, -1199, 0, -741, -438, -385, -966, -587, -350, -392, -12, -534, -324, -91, -581, -688, -447, -319, 176, 998, 56, -466, -352, -101, -626, 61, 211, 676, -278, 359, 483, 197, -791, 70, 2, 384, -324, -56, 923, 699, 501, 794, 406, 397, -145, -18, -252, 74, -445, 265, 382, 13},
{-360, 557, -83, 345, -735, -159, 397, 169, 52, 532, -29, 607, 290, -839, -55, -851, -420, 75, -1084, 653, 1705, 439, -21, -1136, 117, -379, -43, -437, 227, -348, -45, -220, -591, 260, -872, 51, 67, -524, -336, -563, -117, -366, -222, 316, 260, 253, -91, -265, -202, 189, -180, 978, 31, 490, -75, -265, 817, -221, -483, 20},
{436, -753, -311, 783, -561, 177, 157, 441, 91, 164, 145, 612, 201, 812, -232, 954, 421, -535, -426, -299, -89, 458, 455, 949, -161, 967, 312, -78, -811, 384, 37, -788, 96, 297, 457, -643, -235, -96, -144, 115, 481, -561, 700, -396, -163, -598, -712, 519, -368, -94, 1118, -145, -275, 403, 211, 662, -875, 70, 64, -1},
{-383, 100, -537, -8, -668, 584, -422, 677, -257, -300, -290, 403, 54, -220, -818, 275, -294, -254, -565, 248, -316, -178, 202, -38, -136, 790, 713, 609, 215, -228, 122, -522, -154, 527, 73, -159, -178, 491, 477, -13, 363, 198, 317, -51, -189, 558, 346, -486, -248, -124, 469, 147, 136, 31, -273, 127, -901, -340, 189, -79},
{149, -411, 299, 424, 453, 698, 160, 568, -270, 105, -920, -281, -435, 565, 154, 139, -948, -410, 12, 21, 116, -73, 91, -332, 223, 96, -205, 529, 368, 194, -228, 14, 1039, -6, -661, -451, -491, 636, 335, 97, 768, -786, -546, 346, 64, 589, -417, 401, -70, -632, 789, 176, 441, 306, -381, 79, 9, -650, -11, -39},
{-783, 295, -572, 231, -1459, -229, -100, -545, 446, 207, -285, 441, 237, -302, -470, -1289, -234, -282, 315, -710, 348, 392, 364, -42, -353, 1060, -483, -205, -669, -183, 258, 479, 131, 2, 266, -149, 205, -69, -621, 403, -143, 299, -16, 465, -668, -121, 281, 645, -531, -36, 526, 477, 357, 137, 664, 85, 262, 202, 871, -18},
{938, 48, 42, 117, -58, 4, 409, -307, -247, -199, 587, -187, 44, 134, 500, 236, -38, 570, -451, 40, 535, 40, 15, 338, 171, -529, 357, -721, 177, -67, -135, 1151, -617, 744, 745, 375, 427, -100, 328, -344, -678, -181, -264, -131, 880, 279, 307, 113, -146, 77, -458, 290, 313, -159, 363, -246, -347, 300, -485, -113},
{374, -24, -86, 91, -35, 106, -69, 611, -512, -866, -108, -275, -597, 674, 464, 437, 77, -10, -189, -407, 616, 300, 52, 379, 724, -136, 466, -132, 16, 460, -187, 285, -423, 143, 510, 6, -189, -362, 94, 13, 256, -597, 427, 503, -20, -228, -121, 919, 64, -430, 808, -983, 191, -13, -477, -309, 361, -255, 155, 153},
{-825, -307, -145, 507, 312, -161, -271, -272, 482, 897, 821, -286, 117, -180, -56, 261, 56, -71, 376, 629, 103, -438, -245, 251, -546, 496, -185, -36, -275, -169, 119, -803, 405, 103, -955, -74, 92, -6, -479, -52, -408, 206, -93, -5, -131, -402, -374, -877, -39, 31, -370, 40, 8, -753, 315, 166, -166, -943, -617, -27},
{770, -508, -319, -63, 733, 640, -639, 446, -399, -76, -670, 222, 419, 186, 188, 165, -381, -29, -787, -138, 181, 336, 394, -327, 457, 209, 398, 564, -537, 398, -558, -217, 278, -972, -588, 357, -175, 390, 387, 5, 441, 139, 582, -377, -401, 457, -337, -706, -72, 93, -191, -237, -464, -484, -454, 9, -268, -778, 10, 75},
{133, 194, -37, 703, 121, -329, 537, 381, -251, 670, 203, 34, -744, 286, 412, 125, -238, 328, 9, 119, 73, -582, 36, -65, 32, 559, 391, 65, 558, 388, -592, -85, -220, 693, -207, -341, 388, -527, 553, 189, 880, 528, -183, -106, 247, -120, -589, 709, -33, -1148, 232, -674, -440, -149, 515, 260, 316, -165, -257, 14},
{-674, 440, -422, -254, -267, -464, -606, -104, 582, 255, 562, 531, 732, -582, -217, -1123, 46, 142, 302, 324, -100, 179, 367, -433, -148, 11, -586, -62, -863, -810, 637, -526, 969, -33, 455, -292, -539, -450, 11, 729, 108, 752, 596, -90, -645, -755, 123, 177, -190, 475, 488, 361, -478, -436, 293, -224, -288, 168, 249, -6},
{-238, 475, -319, 512, -204, 76, -113, 100, 200, -457, -53, -260, -80, 242, -647, -626, -18, -547, -62, 177, 392, 117, -326, -392, 156, 701, 1105, -612, 534, 335, 116, -170, -565, -195, -1117, 161, 809, -185, -233, 329, 190, 1016, 144, -246, -418, 599, 110, -958, -230, -904, -813, -394, -135, -30, 102, 208, -97, 143, 285, 10},
{-227, 255, 298, 284, 546, 465, -247, 24, 394, -745, -460, -385, -353, 377, -223, -431, 25, 356, 13, -871, 248, 332, -185, 535, -193, -108, 171, 413, -265, -159, 48, 855, 237, -506, 549, 135, -351, -621, 167, -240, -225, 177, 34, -62, 203, 545, 729, 788, -497, 373, 163, -207, -738, -300, -287, 581, -392, 219, 153, -123},
{17, 755, -96, -652, 19, -685, -179, 336, 376, 639, -227, -420, -163, -260, -8, -1165, -382, -71, 165, -75, 358, 554, 225, -700, 30, -580, -888, 155, -67, 332, 439, 309, 309, -344, 669, -474, 35, -967, -14, -22, 288, 169, -92, -373, -282, -112, -435, -327, -665, 652, -1101, -22, 138, -271, -235, -364, 358, 358, 436, 5},
{-267, -199, -413, -156, 445, 439, 110, 881, 135, -112, -395, -104, -158, 63, -212, -285, -1167, 85, 139, 472, -8, 168, 427, -177, 146, -316, 175, 93, 524, -225, 159, -513, 426, -143, -679, 82, -1053, -745, 802, 1, 444, 14, 472, -171, -292, -128, -287, 40, 92, 61, 778, 241, -227, -447, -13, -108, -228, -704, 128, -125},
{145, -626, -190, -413, -364, 277, -302, -290, -121, 101, 87, 397, 389, 215, -153, -811, -158, -267, -451, 87, -190, 813, 464, -266, 773, 233, 315, 62, -200, 165, 440, -809, 379, 153, 328, -741, -368, 552, -234, 305, 697, 428, 1119, 14, -1167, 238, 217, -379, 172, 431, 132, -104, -170, -423, -587, -648, 81, -468, 180, 249},
{-231, -67, 765, 420, -60, 1076, -298, -73, -53, 353, 378, -386, 355, 407, 928, 618, -92, 616, -930, -288, -68, 150, 647, 333, 164, -293, 45, -415, -225, 600, 14, -49, 817, 276, -544, 7, 64, -148, -255, -504, 303, -263, -36, 14, -146, 924, 30, 61, 629, 544, 47, 225, 288, -868, -379, -26, 571, -742, -272, 181},
{298, -531, -495, 549, 52, -350, -563, -403, -74, -485, 414, 201, 534, 341, 633, 1552, -149, 1, 263, -14, 255, -463, 262, 1088, 111, 230, 358, -149, -653, -232, -873, -173, -358, 343, 428, 354, -576, 352, 706, -265, -176, -275, 887, -127, -81, 264, -219, -91, -37, 303, 87, -282, 379, -309, 477, -269, -170, -156, 139, -169},
{-775, -528, 6, 197, -503, 198, -1224, 643, -226, 8, -273, -195, 55, -638, 455, 31, 90, -815, -207, 41, -27, 49, 6, -861, -698, 100, -938, 860, -113, 405, -232, -818, 852, -73, -677, -405, -582, -16, 52, -669, -707, -80, 333, -171, -387, -15, -9, -111, 23, 157, 21, 1115, 494, -154, 245, 105, -92, -511, 98, 117},
{-150, -92, -186, 461, 77, -119, 124, 19, 88, -798, -226, 154, 282, 51, -162, 33, 29, -489, 452, -69, 619, -270, -723, -196, 932, 505, 250, 31, 487, -694, 449, -534, -333, -445, 181, 13, 37, -208, 547, 268, 142, 253, 1470, -520, 295, -217, -99, -816, -123, -704, -519, -138, -405, -195, -114, -51, 202, 383, 316, -108},
{25, -67, 366, -90, 56, -371, 588, -632, -479, 268, 436, 382, -196, 716, 210, 642, 545, 151, 231, -543, 60, 527, 310, 464, -26, -471, 365, -594, 153, -814, -784, 418, -126, -50, 333, 215, -452, -574, 277, 408, 6, -80, 596, 207, -201, -745, -201, 342, 489, -79, 125, -51, -43, -407, 241, -22, 41, 184, -407, -26},
{267, -110, -443, 353, -380, 571, -112, -641, -515, -239, 152, -206, -363, -526, -620, -1363, -286, 164, 77, -679, 41, -114, -139, -597, -810, 449, 489, 362, -896, 653, 105, 823, -1058, -405, -768, 883, 180, -193, 121, 69, -508, -98, -419, -102, -378, -193, 370, 540, -608, -345, 488, 335, -480, 836, 639, 239, -4, -270, 113, 157},
{360, -73, 124, -589, 73, -312, -563, -200, 432, -168, -148, 169, 902, -702, 550, -796, 492, 175, 246, 394, 471, 348, 283, -224, 869, -362, -559, 481, -348, -702, -212, 423, 861, -531, 844, 18, 444, 768, -88, -50, -119, 167, 287, 721, -32, 356, 886, -908, 129, 499, -72, 175, -254, -91, -169, -660, 351, 349, -206, -63},
{710, 40, -218, -2, -317, -969, 168, 548, -250, -286, 101, 522, -630, -641, 331, 496, -462, -668, 151, 339, 655, -472, -551, -325, 57, -366, -291, -143, -758, 323, 392, 346, -695, 254, -429, 73, -146, -51, 183, -69, -305, -328, 64, 425, -10, -1430, -250, 58, -421, -475, -455, 310, -479, 368, -150, -89, -705, -106, -227, -113},
{468, 542, 497, 490, 81, -1, 134, -36, 410, 168, 327, -424, -786, 352, -640, 505, -78, -49, -103, -67, -916, -498, 12, 282, -749, 334, 390, 178, 321, 259, 1, 134, 478, 614, 627, -624, 335, 507, -11, 485, 343, -150, -1179, 247, -29, 522, 223, 495, 26, -185, 578, -401, 118, 310, 106, 19, -929, 414, 316, 21},
{558, 365, -539, -214, 73, -676, 155, 155, -20, 144, 469, 136, -766, -442, -422, 425, 763, -26, 1042, -485, -335, 180, -537, 634, -342, 611, -335, 407, -629, -174, -53, -290, 317, -203, 382, 195, 923, -685, -596, -10, 131, 400, 572, -462, 43, -1009, 270, -381, -163, -577, -651, -1082, -891, -150, -304, -149, -164, 32, 500, 38},
{-151, 583, -23, -40, -1169, 92, -47, 662, -232, 120, 538, 541, -726, -564, -222, 73, -523, -69, -295, 521, 1030, -464, -60, -866, -206, 410, 241, 42, -397, -217, 71, 203, -856, 637, -221, -68, -107, -600, 117, -252, -371, -707, 253, 983, -294, -529, 112, -310, 475, -373, 723, 640, 336, 605, 344, -202, -2, -373, -123, -397},
{696, -1076, -412, -54, 198, 170, -735, -386, -393, -483, 38, 159, -180, 785, -253, 451, 87, -292, -262, 614, 237, -619, 693, 299, 758, 650, 345, 35, -289, 302, -451, -159, 62, 272, 229, -20, -116, 747, -363, 128, 330, -28, 293, 453, -562, 702, 19, -6, 63, 281, 1069, 212, 384, -266, 118, -601, -106, -847, 23, 168},
{724, 494, -36, 201, -80, -216, 883, -507, 125, 522, -257, 314, 799, 864, 318, 616, 127, 927, -357, 192, 486, 186, 286, 1108, 396, -29, 196, -886, -37, 114, -222, -225, -728, 19, 180, 141, 332, -311, -1323, -96, 884, 197, 90, 163, -81, 392, -684, 349, -605, -621, 65, -622, -122, -675, 319, -130, 385, -267, 295, 96},
{-160, 571, 1117, -8, 209, 621, 337, -305, -320, -515, -284, -82, 601, 760, 763, 377, 236, 87, 302, -444, -474, 537, -412, 586, 3, -719, -686, -986, -85, 210, 566, 92, -225, -370, 483, 12, -451, -189, 231, 118, 563, -358, -385, -338, 339, -79, -381, 625, 113, 211, 222, -540, 636, 592, 139, -201, 538, 128, 193, 130},
{457, -150, -121, -10, -112, -488, -139, 550, -890, 126, -922, 375, -386, -28, 41, 706, 52, 146, 303, 533, -190, -778, -141, 714, 616, 354, 135, 71, 401, 492, -1275, -390, 411, 724, -119, 352, 384, -329, -88, 99, -169, -368, -190, 116, -177, 227, -184, -268, 741, -374, 441, -24, -319, 204, 18, -245, -42, -650, -103, -29},
{481, -385, -266, 8, 179, 31, 6, -1128, -522, -71, 37, 133, 692, -4, 418, -400, 235, -67, -47, -656, -689, 412, -105, 723, -479, 79, -683, 238, -1003, -254, 363, -18, 590, -188, 1104, 466, 54, -281, 512, 359, 180, 424, 51, -337, 419, -102, 282, 156, -50, 1052, -42, -454, 391, -27, 459, -159, 125, 511, 66, 249},
{-830, 121, 225, -393, 272, 1145, -105, -232, 609, 571, -312, -573, -410, 379, 211, 741, 112, 311, -202, -500, -1410, -316, 343, 618, -437, 671, 14, -239, 385, -112, -378, 62, 911, -84, 389, -469, -1186, -278, 152, -40, 435, -373, 581, -319, 216, 303, 273, 639, -236, 245, 675, -341, -205, -233, 39, 331, 366, -237, -126, 68},
{-886, 404, 186, -75, -77, 242, -943, 657, -572, -880, 269, -110, 440, -425, -162, 173, -407, -255, 300, -3, 96, -123, -460, -149, -661, -130, 244, 82, 159, -74, -227, -393, -778, 71, -179, 786, -780, -1105, 74, -393, -481, -59, -42, 730, -750, 245, 770, -455, 238, 142, -214, -15, 156, 24, -162, 432, -386, -387, -197, -345}};
    }
    if(n == 70){
      b = {{-705, 66, -445, -91, -103, 546, -486, 132, -425, -403, -657, -511, 423, -557, 504, -272, -401, -644, 62, 1178, 881, -156, 305, 412, -1009, 8, 281, 144, -558, -34, 103, -972, 517, 573, -1211, -483, -200, 355, -716, -650, 54, -787, 535, -373, -868, -427, -268, 1171, -887, -906, 538, -584, -606, -241, -387, -425, -176, 112, -320, 51, 81, -166, -632, 133, 191, 70, -1, 0, 0, 0},
{538, -860, -23, 70, -46, -331, 185, 956, -346, -602, -230, -504, -40, -955, 34, 1085, 69, -1172, 1043, 252, 581, 79, -195, 640, -666, -439, -20, 976, 558, -423, -50, 76, 887, -279, 209, -243, -54, 634, -70, -1017, -520, -720, 1033, 41, -1054, -96, 212, 1073, -1222, 345, 195, -213, 911, 333, 235, -705, 520, 133, 77, 1644, -163, 949, -491, 27, -2, 23, 147, 0, 0, 0},
{27, -1316, 792, -462, -271, -700, 139, 530, -392, 286, 304, -745, 181, -798, -145, 618, -625, 614, -508, -384, -98, 696, -878, 360, -554, -759, -357, 787, 121, 842, -377, -62, 643, 1651, 167, 244, -633, -446, -403, -300, -676, -431, 692, -68, -1065, -20, -213, -736, -634, 514, 452, -402, -205, 234, 679, -861, 457, -270, -703, 1886, -889, 265, 298, -189, -216, 154, 0, 0, 0, 0},
{495, 646, -184, 326, -460, 3, 714, -393, -496, -360, 1061, 318, 661, 754, -20, -449, 197, 1511, -128, -1849, 4, 0, 278, -724, 108, -374, -632, 1369, 656, -247, -636, 91, 12, 969, 183, 570, -209, -51, 724, -38, -693, 845, -631, -977, 667, -166, -437, -1612, 432, -525, -232, 572, -704, -151, -28, -404, 247, -521, 162, 122, 90, 142, 1472, -306, -226, -250, -19, 0, 0, 0},
{-1023, 851, -974, 5, 617, 253, -241, 459, -1251, 767, 383, 387, 391, 145, 313, -577, 751, 617, -617, 405, 540, -520, 198, 246, 202, 375, 1046, 1108, 834, -277, -186, -653, 659, 440, -1302, 568, -721, 751, 758, -318, 87, 548, 311, -1007, 274, -167, -239, 740, 343, -1222, -22, 592, 378, -774, -1188, -622, -426, -143, 249, -903, -58, -323, -31, 219, -581, -242, -19, 0, 0, 0},
{1019, 522, -685, 47, 820, 366, -101, -1582, 347, -309, -841, -437, 348, -323, 891, -761, 280, -959, 806, -175, 527, -826, -491, 617, 222, -119, -117, 55, -506, -246, 419, 578, 573, -733, 426, -492, 704, -175, 21, 664, 499, -281, -1333, 2, 163, -274, -312, 1895, -997, 681, -591, -796, 503, 287, 995, 1580, 29, 308, 187, -64, -360, 227, -1062, 60, 291, -134, 147, 0, 0, 0},
{-146, 889, -563, -499, -706, 635, -264, -1163, -3, -1012, -626, -437, 1568, 336, 1133, -805, 77, -282, 220, -455, 177, 190, 239, -935, -585, 316, 426, -355, -267, 1124, -920, 220, -12, 1203, -435, -847, 232, -924, -311, 457, 1474, 417, -365, -823, -1090, -1041, -617, 699, -304, -511, 551, -447, -1592, -1139, 934, 1019, 22, -36, -664, 484, -418, -418, 87, 98, 590, -87, -1, 0, 0, 0},
{-553, 1197, -439, -870, 11, 935, 25, 75, -466, -70, -502, -508, 303, 551, 983, -264, 960, -1282, -480, 329, 476, -328, -257, -244, -195, 223, -289, 276, -1110, 396, -1242, 434, -539, -584, 351, -187, 116, 200, 303, 39, 1220, 238, 62, 105, -196, -807, -236, 365, 511, -1393, 888, 184, 111, -132, -39, 196, -119, 75, -418, -79, 678, 87, -593, -162, 393, -74, -105, 0, 0, 0},
{119, 685, 361, -127, -1093, 327, 778, 657, -364, 429, 742, -241, 309, 487, -422, 726, 535, 682, -826, 187, -134, 1068, -590, -1752, 140, -291, -991, 244, 299, 365, -752, 224, -769, -512, 611, 165, -154, 1243, -349, -1043, -404, 307, -37, -72, 261, -221, -457, -766, 889, -262, 937, 776, -193, 94, -750, -402, -361, -266, -369, 215, -126, -337, 449, -356, 4, 41, -227, 0, 0, 0},
{1445, -207, -645, 319, 335, 62, 108, -683, 516, -890, -249, -626, 592, 816, -117, -371, 480, -419, 912, -611, 480, -803, 147, 918, -1404, -1359, 313, 1173, 8, -76, -148, 302, 815, 396, -306, 116, 275, -834, -122, -71, -465, -116, 135, -344, -995, -489, -509, 413, -726, -973, 430, -314, -762, 9, 903, 232, 765, 272, -575, 1047, 80, 716, 17, -891, 541, -34, -87, 0, 0, 0},
{462, 187, -657, -998, -840, -117, 870, 4, 129, -424, 222, -1038, -85, 905, 46, -245, 158, -484, -413, 56, -296, -50, -580, -822, 243, -758, 22, -740, -260, 415, -200, 1000, -259, -594, 526, -439, 663, -219, -357, 88, 709, 86, -345, 69, -786, -941, 379, -6, 472, -520, 1066, -201, -771, -288, 4, 308, -845, -834, -1131, 181, 428, -260, 35, -713, 689, 92, -234, 0, 0, 0},
{439, -826, -603, 41, -1335, -396, 675, -27, -253, -481, 151, -711, -255, -436, 207, 310, -610, 1163, -411, -1437, -81, -53, -320, -369, 344, -433, -1582, -37, -682, -443, 220, 912, -837, 378, 706, -76, 541, 269, -185, 409, -953, 218, -326, 647, 631, -53, 37, -1443, 193, 502, 279, 84, -275, 112, 400, -254, -287, -408, 302, -88, 322, -118, 636, 282, 197, -178, 586, 0, 0, 0},
{-304, 356, 76, -207, 831, 287, 167, -887, -1052, 877, -172, -133, -31, 13, 471, -645, 125, 69, -668, 834, 70, 148, 274, 453, 373, 1019, -533, -33, -104, 131, 356, -1307, 388, -131, -778, -183, -83, -225, -303, 358, -204, -1036, -993, -388, 661, 370, -414, 619, -1053, 399, -543, -934, -624, 497, -305, -132, 216, -282, -240, 257, -434, -934, -295, 400, -115, -237, -146, -161, 23, -1},
{-967, -19, -265, -891, -382, 804, -1109, 353, 5, 277, -1523, -758, -712, -358, 63, 614, -16, -767, -874, 601, -48, 521, 579, 486, -561, 941, -1148, -813, -1491, 258, -469, -1191, -1048, 661, -100, -499, 207, -295, -703, 156, 273, -1020, 486, 1365, 137, -225, 147, -3, -94, -519, 240, 498, -412, 128, 694, -132, 394, 426, -209, 91, 624, 95, -411, -196, 466, -154, 296, -160, 23, -1},
{447, 444, 962, -142, -650, -245, 136, 796, 401, -829, -771, -168, -132, -145, -94, 934, -404, -358, 344, -1366, -279, 496, 543, -1077, -463, 563, -334, 320, 428, -393, -797, 738, -503, 725, 809, -524, 182, -881, 517, -290, 84, 658, 843, 492, -1100, -220, -278, -913, 92, 271, 141, 757, -271, 356, 1268, -406, 568, 93, 333, 729, 116, 1493, 534, -483, 482, -49, 109, 100, -14, 0},
{133, 760, -942, -666, -168, 795, -445, -519, 76, -186, 263, -890, -69, -141, -14, -804, 241, -522, -768, -23, -299, -701, -754, -14, 681, -689, 70, -185, -224, 869, -134, -125, 449, -190, -130, -88, 377, 0, -1088, 376, 700, -463, -196, -142, -141, -996, 200, 544, -304, -147, 185, -249, -812, -202, -458, 518, -401, -364, -205, -1128, -153, -256, -817, 41, -233, -123, -21, 171, -23, 1},
{430, -162, 101, -600, -340, 286, -773, -593, 24, 403, -243, -237, 109, 2, -419, 290, 621, 408, -355, -807, 62, -102, -862, -110, -582, -99, -1047, 398, -1111, 156, -265, -87, 446, 752, -116, -123, 107, -19, -1751, 415, -522, -589, 44, 500, 84, -252, -1162, -452, -824, 680, 161, 403, -785, 126, 781, 51, 3, 5, -302, 1210, -361, -18, -20, -412, 71, -441, 154, 10, 0, 0},
{941, -180, 206, 1133, -1001, -636, 1461, 141, 1150, -79, -176, 228, 11, 168, 238, 157, -267, 652, 169, 875, -925, 244, 338, -951, 521, -74, -15, -1800, 459, -310, 1121, 1186, -794, -882, 870, -434, 1027, 234, 208, 582, 3, 526, -467, 501, -95, -60, 459, 493, 297, 1319, -319, -105, -405, 496, 603, 180, -651, -254, 76, -740, 53, 207, -96, 21, 92, 341, 122, -10, 0, 0},
{-1222, 227, -1167, -520, -1252, 727, -490, -135, -168, -1118, -300, -505, 729, -547, 174, 463, -628, -613, 162, -198, 160, 360, 310, -299, 225, 181, -179, -804, -293, 218, -399, -22, -584, 1071, -131, -225, -221, -114, 884, -486, 967, -603, 303, -89, -44, -612, 554, -44, 843, -37, 570, 6, 551, -711, -78, 794, -195, 226, 213, -177, 719, -99, -334, -63, 332, -330, 4, 20, 1, 0},
{-522, 81, 348, 610, 1035, 777, 615, 442, -51, 587, 143, 719, -155, 418, 568, -244, 1023, -325, -910, 877, 379, -728, 476, 1308, 823, 100, -350, 213, -209, -489, -18, -14, -47, -1011, 32, 914, -673, 116, 1977, 358, 85, -135, -208, 107, 1047, 1022, 326, -218, 505, 496, -545, -306, 496, 910, -106, -726, 612, -262, 448, -5, -69, -194, -176, 477, -390, 25, -328, -11, 0, 0},
{127, -843, -88, -555, 1090, -1298, 536, 300, -1083, 1632, 108, -381, -419, -148, 737, -307, 236, 747, -548, -617, -23, -116, -816, 1681, -177, 243, -1605, 1326, -443, 31, -156, 1115, 263, -184, 176, 260, 71, -48, 524, 645, -632, 535, -210, 403, 575, -322, -315, -441, -276, 9, -278, -417, 1145, 675, 730, -353, 781, 133, -23, 550, -538, 153, -295, -105, -329, -289, 337, -191, 22, -1},
{-797, 1262, -518, -237, 741, 146, 35, -949, -996, 1038, -45, -374, 14, 370, 434, -1034, -46, 1084, -910, -161, 302, 716, -404, 785, -21, 551, -735, 1571, 295, 270, -443, -1072, 100, 647, -789, 996, -455, -722, 1057, -271, -625, -393, -490, -643, 776, -83, -963, -173, 466, -798, -528, -512, 314, 0, -158, 602, 1100, 19, 213, 82, -237, -761, 134, -600, -266, -601, -183, -332, 46, -2},
{-364, -666, -2, 1008, -32, -77, -110, 165, -378, -628, -34, 459, -493, -65, 125, 303, 443, 277, 243, -330, -475, 369, 1130, 705, -452, 862, -915, 473, -383, 155, -186, -1271, -370, 399, -338, -413, 316, 221, -230, 324, -683, -56, -104, 669, 740, -428, 580, -547, -654, -360, -1009, 389, -407, 573, 333, -749, 928, 471, 564, -809, 881, 559, 245, 447, -182, 88, -272, -298, 36, -1},
{417, 6, -70, 27, -102, -848, 870, 814, -499, 1576, 859, 754, -247, 686, -273, 164, 659, 414, 41, 680, 204, -416, 467, 192, 499, -312, 65, 487, 494, -855, 18, 78, 85, -1882, 321, 604, -584, 1279, 434, 174, -458, 138, -502, -119, 767, 210, 333, 375, -175, -429, -44, 614, 704, 372, -589, -644, -440, -431, -172, 520, 145, 63, 592, -611, -411, -391, 419, -211, -21, -1},
{-520, -1308, -329, -1086, 749, -377, -459, -513, -305, 63, 299, -145, -1099, -213, -263, -171, 345, 224, -1058, -793, 198, -304, -1213, 689, 683, 547, 318, -281, -631, 515, 756, -202, -83, 677, 207, -72, 190, -515, -75, 1146, -283, -186, -550, 492, 387, 832, 813, -371, 277, 132, -468, 549, 455, -519, 375, -143, -738, -826, -416, 43, -159, -41, 135, 50, -249, 138, -26, -276, 37, -1},
{346, -6, -15, 213, -542, -408, 168, 270, -289, 447, -264, -85, 369, -154, 799, -23, -53, 664, 160, 81, 100, -460, 117, 144, -1013, 173, 1139, 683, 266, 732, -765, 490, 113, 1272, -483, 520, -350, -769, -109, -83, -51, 243, 1114, 36, -856, -112, -386, 666, -540, -768, 886, 60, 20, -378, 547, -462, 595, 505, -395, 542, 52, 499, 298, -193, 197, -266, 752, 65, -58, 0},
{508, -1125, -213, -251, 40, -593, 180, -717, 579, -12, -360, -115, -322, 779, -641, -180, -123, -110, 245, -681, -251, -238, 1073, 125, 477, 407, -499, -791, -151, 115, 617, 624, -59, -979, 181, -312, 256, -1104, 381, 712, -629, 21, -1089, 892, 835, 567, 546, -474, -332, 713, 253, 332, 180, -163, 441, 560, 112, -19, -550, -39, 235, -40, 540, -354, 601, -381, -75, -112, -35, -1},
{294, 194, 422, -9, -94, 356, -626, 328, 652, -181, -811, -293, -69, -396, -587, 57, 22, -1211, 119, -4, 930, 615, -859, -232, -354, -404, 86, 1084, 111, -117, -302, 808, 719, -1819, 273, -729, 363, 610, -800, -703, -5, 588, 217, 846, -820, -673, -771, 1002, -399, 367, 146, 581, 301, 208, 337, 506, -43, -410, 391, 45, -848, 59, -755, 32, 237, -56, -407, -162, 62, 11},
{47, -786, -302, 381, 552, -987, 294, -617, -398, 485, 439, 285, -645, 325, -607, 312, 503, 1751, -324, -442, -516, -426, 273, 543, 7, 486, 545, -205, 260, -418, 304, -234, -748, 1514, -516, 553, -313, -547, 211, 462, -1364, 430, -228, 337, 987, 918, 409, -317, 553, -262, -783, 500, 507, -215, 344, 229, 10, 569, 278, -619, 254, 51, 1100, -236, -210, -139, 50, 76, 24, -2},
{-429, -235, -439, 898, -68, -471, 73, -506, -771, 728, -823, 28, 411, -579, 793, -273, 256, 1414, -327, 410, -427, 64, -214, -255, 618, 772, -109, 235, 1, 150, 129, -235, -140, 1150, -753, 279, -353, -547, 642, 828, -202, 204, -379, -242, 289, 45, -757, 802, -468, 614, -244, -1042, -348, -12, 252, 119, 297, 537, 151, 308, -569, -353, -138, 321, 434, -66, 367, -37, -40, -12},
{-1148, -1271, 486, 361, -95, -405, -417, 216, -183, -265, 82, 441, 350, -113, -654, 55, -901, 365, 324, 928, 97, -316, 188, 883, -939, -45, -395, -432, -1495, -39, -315, -929, -294, 1176, -1068, 488, -1026, -278, -452, -57, -754, -335, 943, -167, -344, 121, -236, -1452, 490, -1203, 194, -907, 42, 205, -598, -668, -36, 318, -154, 415, 553, -206, 200, 109, -177, 488, 76, 56, -63, -11},
{-1562, -104, 743, -240, -847, -200, -506, -330, 199, -206, 138, 507, 882, -298, -76, -433, -1437, 631, -190, 408, 350, 937, 767, -767, -1286, 1229, 462, -469, -246, 939, -642, -470, -796, 2136, -673, -663, -731, -897, 313, -533, 547, -137, 570, -325, -602, -499, 54, -445, 283, -388, -81, 304, -1163, -549, 144, 40, 122, 83, -315, -493, 12, 19, 963, -94, 88, -183, 165, -118, 111, 16},
{540, 752, 211, -277, -131, -216, 631, -1110, 676, -106, -326, 489, 500, 576, 693, -1103, -54, -381, 248, -926, -10, -110, 748, -414, -33, 842, -412, 168, -287, 173, 69, 582, 239, -958, 969, -948, 546, -254, 1063, 846, 839, 302, -1607, 231, -61, -930, 38, 50, -158, 305, -728, 224, -679, 506, 1077, 506, -837, -936, -360, -215, 217, 808, -80, -725, 352, -144, -456, -444, -47, 5},
{503, -85, 43, 790, 246, 357, -308, -171, 587, 151, 462, 639, -792, 901, -1022, 65, 718, 634, -313, 294, -497, -355, 272, -12, 217, 510, -38, -475, 62, 78, 357, 446, -1324, -357, -438, 121, 424, -325, 457, 467, -274, 86, -51, 371, 1162, 185, -4, -265, 1246, 44, -136, 326, 335, 359, -48, 826, 753, 1179, 425, -1852, 49, 583, -308, -436, 264, -184, 58, 60, 96, -2},
{-84, 1549, -138, -1450, 832, 425, 422, -48, 182, 855, 569, -233, -181, 1466, -449, -338, 1400, 156, -1209, -548, -388, -669, -237, -842, 801, -125, 990, 47, 476, -693, 39, 894, 212, -226, 88, 444, -352, 366, 548, -133, 436, 473, -736, -257, 294, 83, -442, -499, 1231, 177, 174, 650, 221, -326, -606, 496, -1208, -117, -691, -258, -130, 248, 29, -779, -69, -316, -902, 350, 34, -1},
{-333, 457, -43, 696, 15, 372, 353, 91, -248, 739, 411, 472, -241, -493, -168, 131, 10, 772, -185, 966, -748, 991, 312, -910, 1036, 386, -281, -584, 1384, -450, 856, -1116, -769, -90, 74, 543, 548, 687, 262, 386, -527, -186, 287, -862, 1129, 877, -119, 238, 474, 210, -691, 688, -7, -497, -731, 195, -103, 388, 534, -200, -114, -504, 360, 148, -737, 116, 114, -184, 38, -1},
{241, 180, -447, -307, -40, 286, 26, -72, -406, 670, 550, -563, 73, 421, -832, -137, -742, 579, -390, 1026, 343, -148, 549, 116, -164, -395, 516, 182, 308, -110, 35, -1551, -97, 620, -494, 487, -716, 405, 533, -424, -339, -1065, -649, -607, 125, -272, 135, -18, 283, -1512, -212, -813, -318, 432, -923, -576, -639, -555, -453, -353, 410, 340, -84, -679, -97, -183, 279, -276, 20, -1},
{525, -257, -264, -38, -180, -269, 104, 65, 26, -265, -89, -954, -876, -638, -1144, 130, -422, -884, -144, 487, -86, -387, -667, 405, 752, -871, 631, 271, 59, -395, 570, 328, -40, -1176, 518, 383, -62, -736, -324, 127, -647, -1184, 19, 752, -273, -292, -70, 260, -112, 585, 381, -392, 544, 689, -397, 835, -96, -83, 169, -494, 710, 105, -629, 185, 33, -65, 148, 304, 6, 0},
{959, 84, -1215, 184, 407, -212, 981, -345, 200, -211, -424, -261, 104, 151, 117, -440, 407, -176, 136, -768, -46, -795, 1199, 342, 917, 103, -655, 126, 676, -913, 389, 490, 337, -416, -115, -4, 71, -1027, 1479, 1002, -758, 494, -1060, 651, 486, -140, 519, 360, -602, 217, -535, 29, 97, 453, 1035, 457, 159, -319, 431, -638, 340, 344, 16, -616, 469, -385, 39, -324, -270, -17},
{-273, 894, -1107, 425, -129, 722, 265, -526, -353, 432, -28, 538, 1323, 444, 1000, -737, 1260, 495, 62, -369, 226, -885, -451, -774, 636, 722, 717, -13, -97, 390, -442, 850, -169, -368, -173, 592, 367, 884, 902, 222, 535, 1141, -179, -67, 580, 104, -377, 550, 767, -334, 145, 505, 897, -1334, -399, 335, -639, 39, -227, -165, 237, -880, -153, 764, 213, -20, 205, -267, -66, 7},
{389, 31, 459, -571, 543, 621, -694, -299, 1184, 199, -215, 64, -1143, 972, -242, 206, 953, -367, -545, -267, -916, -27, -243, -159, -188, 273, 307, -644, -1084, 763, -862, -423, -547, 837, 518, -137, 100, -709, -1313, 422, 883, 28, 117, 834, 75, -387, 45, -916, 468, 138, -57, 225, -953, 336, 527, -24, 553, -13, -711, -84, 175, 137, 452, 196, 611, 514, -307, 20, 155, 6},
{-991, 431, -709, -133, 1284, -418, -446, -322, -879, 297, -1189, -436, 177, -1216, 723, -740, -493, -330, 50, 818, 595, 167, -436, 317, 343, 847, 972, -459, 750, -690, 946, -172, 250, 166, -731, -235, 398, 178, 612, 63, 636, 250, -440, -683, -80, 782, -167, 2138, -490, -408, -755, -611, 304, -1191, -429, 803, -493, 223, 284, -395, -371, -773, -554, 404, -37, 244, 59, -303, 246, 16},
{877, -1297, 730, 220, 20, -90, 94, -828, 512, -876, 316, 713, 98, 166, -115, 551, -270, -514, 1297, 243, 311, 372, -364, 301, -490, 277, 578, -675, -274, 141, 93, 351, -36, 591, 400, -317, -77, -531, -461, -366, 63, -361, -328, -277, -453, 1002, 193, 259, -338, 1335, -170, -575, -44, 125, 1071, 180, 184, -668, -53, 1716, -525, -171, 390, 657, 255, 574, 33, 333, -101, -22},
{-761, 601, -340, -351, 135, 1189, 429, -241, -1469, 72, 813, -175, 1197, -39, 912, -467, 864, 618, -1598, 692, 610, 35, -130, -157, 620, -189, -584, 872, -338, 437, -256, -1343, 482, 1148, -734, 54, -660, 657, 407, 336, 361, -516, -1142, -1612, 206, -421, -111, 60, -65, -649, 694, -1183, -781, 275, -756, -616, -453, -749, -808, 776, -601, -651, -233, 593, -146, 407, -447, -136, -20, -12},
{-221, 340, -952, 591, 960, 613, 190, -535, -857, -492, -628, -319, -218, -394, 984, -574, 629, -130, -336, -316, 972, -594, -380, 356, 466, 342, 168, 605, -207, -814, 670, 150, -218, -289, -635, 417, 172, -11, 1599, -361, -207, 8, 57, 46, 684, 734, -452, 741, 226, -140, -48, -591, 268, 1, -620, 298, 55, 259, 502, -447, 726, -976, -414, 415, 911, -195, -17, -426, 89, 24},
{199, -2036, 187, 50, 25, -176, -130, 94, 171, -123, -14, -597, -426, -1162, 37, 1002, -634, 199, 564, 708, 1031, 117, -1399, 179, -412, -883, -399, 64, -1122, -73, 144, -138, 36, 764, 446, -361, -465, 1468, -727, -1160, -1230, -636, -45, 513, -271, 770, 599, 604, -582, 351, 464, -172, 573, 179, 86, -740, -604, 178, -547, 413, -445, 63, 428, 170, 318, 638, 4, 480, -3, 20},
{-872, 802, 202, -50, -60, -422, 563, -314, 406, 210, -58, 418, 579, -597, 1218, -1136, -901, -193, -79, -429, -1000, -339, 426, -789, 769, -27, 1054, -164, 209, 592, -257, 144, 274, 650, 1023, 181, -245, -1134, 865, 1138, 1440, 832, 277, -870, -470, -302, 285, -206, -242, -195, -63, -283, -214, -208, -89, -139, -325, -121, 44, 134, 49, 247, -65, 47, -179, -31, -107, 141, -194, -36},
{1033, 1034, 424, 477, 493, 969, 806, -2242, 34, 119, 966, -111, -3, 1373, 385, -957, 305, 601, -584, -759, 70, -356, -321, -136, 131, -599, -802, 1029, -437, 1078, -188, 61, -307, -115, 169, 1172, -306, -1005, 252, 485, -616, -259, -1272, -370, 1331, 211, -1064, -1111, 323, -768, 105, -324, -181, 853, 294, 759, 493, -217, -215, -330, 337, -295, 68, -1019, -128, -358, -635, -402, 62, -2},
{683, -125, -97, -612, -141, -734, 431, -728, 49, -860, 89, -405, 25, 3, 703, -129, 137, 368, 288, -1373, -434, -61, -197, 52, -38, 65, 166, 426, 227, 794, -428, 1118, 653, 943, 563, -104, 282, -1442, 12, 753, -13, 357, 6, 204, -956, -672, 104, -758, -222, 1140, -405, -659, -311, -244, 1077, 654, 295, -629, -170, 635, -287, 239, 75, 208, -134, -19, 65, 202, -161, 20},
{-360, 601, -164, -236, 12, -135, -276, -84, 147, -429, 339, 191, -232, 142, -528, -529, 191, -450, 173, -448, -720, -631, -463, -175, 610, 238, 485, -164, 385, 153, -249, 781, -176, 145, 157, 380, 133, -1088, 656, 696, 862, 43, 522, -286, -258, -311, -19, 8, 488, -178, -276, 628, 354, -321, 233, 429, 115, -52, 132, -230, 437, 984, -260, -526, -309, -190, 506, 36, 248, -51},
{620, 153, -342, 645, -741, -321, 917, 933, 161, -600, -91, 650, 218, 763, -66, 788, 925, -209, 706, 626, -450, 488, -177, -1018, 98, 146, 1078, -329, 1075, -996, 939, 1219, 351, -796, 178, -198, 583, 480, 34, -187, 499, 763, 529, -75, -865, -100, -343, 416, 455, 770, 152, 79, -191, 41, -749, -550, -850, -452, -59, 635, 459, -204, -439, -60, 550, 16, -228, 47, -302, -3},
{-810, 367, 119, -30, 556, -120, 1070, 998, -1036, 80, -186, -10, -229, 97, 716, 268, 794, -73, -487, -95, 168, -340, -197, 57, 465, 116, -348, 1060, 85, -1154, 276, -32, 563, 353, 254, 749, 116, -15, 1406, 126, -312, -15, -372, -409, -52, 239, 16, -409, -261, -237, 8, 479, 442, 293, -18, -1169, -69, -568, -16, 958, 1131, 900, 286, -663, -99, 515, -695, -158, 215, 11},
{-807, 143, -156, 157, 457, -96, 119, 570, -921, 711, 55, -509, -600, -209, -566, 101, -217, -831, -633, 1347, 72, 380, 914, 893, -132, 246, 321, 137, 536, -551, 149, -623, -154, -353, -931, -301, -283, 545, 824, -866, -311, -721, 968, -8, -314, -589, -211, 369, 375, -668, -77, -110, -215, 657, -791, -327, 34, 40, -53, -910, 315, -207, -710, -229, 178, -138, -687, -378, 129, 74},
{1168, -52, 555, -28, -387, 413, 642, -783, 543, 693, 150, -455, 242, -674, 948, -282, -280, 1076, -1028, -779, -602, 267, -1060, 385, 93, -641, -1552, -21, -614, 848, 578, 1152, -455, 393, 989, 150, 629, -441, -748, 1223, -522, 69, -540, 897, 501, 8, -253, -794, -171, 1176, -29, -398, -318, 806, 1128, 483, -87, 78, -166, -301, -483, -263, -566, -40, -97, 44, 14, 229, -233, 49},
{-545, 47, -338, -36, -48, 258, -286, 244, 323, 634, -116, 706, -682, 389, 117, -308, -823, 151, -350, 856, -180, 119, 310, 217, 532, 407, 13, -1555, -555, -1237, 1122, -370, -502, -283, -119, 38, 558, 523, 712, 346, 540, -620, -120, 269, 1203, -72, 434, -33, 1157, 765, -756, 618, 390, 563, -280, 195, -823, -27, 443, -1615, 949, -428, -221, -263, -328, -414, 323, -372, 94, -54},
{-863, -89, 1147, -754, 1399, -160, -62, 229, -263, 712, -295, -1, -779, 285, 1030, -688, 472, -381, -900, 850, -11, -437, -183, 1206, -660, 377, 558, 94, -963, 201, -309, 60, 937, 322, -823, 188, -266, -503, 59, 8, 626, -288, 560, 447, -588, 199, -593, 124, -679, 974, -425, -1101, -603, 698, 391, -783, 76, -369, -283, 399, -359, -332, -465, 506, -250, 17, -204, 146, -100, 143},
{110, -764, 247, 547, 195, -555, 629, 378, -624, 521, 380, 97, -267, -897, -16, 137, -107, 705, -495, 818, -242, 69, -990, -266, 559, -288, 295, 68, 814, 975, 116, -355, 117, -5, -80, 413, -347, 294, -503, -545, -989, 75, 45, -52, -279, 677, 498, 625, -574, 827, 32, -687, 676, 61, -885, -681, 152, -410, -117, -255, -1233, -492, -268, 781, -328, 801, 256, 226, -262, -52},
{437, -654, -682, -624, 1290, 11, 388, 280, -330, -562, -299, -596, 22, 42, 718, 303, 387, -2000, 865, 616, 61, -384, 24, 1122, -148, 342, 1044, -767, 330, 359, 525, 493, 31, -668, 311, -736, 381, -66, 782, 314, 1446, -1128, -60, 48, -1087, -377, 1091, 1389, -597, -376, 1, -374, 704, 350, 794, 103, 186, 330, -867, 743, 940, 517, -1036, 226, 173, -36, 156, -368, 356, -148},
{90, -327, -985, 318, 1111, -1004, -29, -1014, -662, 305, -393, -793, -533, 273, 450, -598, 24, 251, 23, 257, -221, -1403, -60, 1292, -157, -396, 1028, 164, -202, -710, 1077, -62, 985, -122, -1281, -232, 324, -514, -657, 241, -722, -293, 216, -82, -429, -140, -166, 869, -962, 444, -271, -947, -543, 228, -282, 133, -368, 389, 457, -1417, 240, -635, -734, 64, -110, -500, -136, 459, -181, 133},
{-308, -626, 442, -1309, -382, -223, -806, 880, -225, -232, 110, -482, -479, -682, -377, 312, -88, -605, -295, -630, 618, -87, -372, 486, -304, -743, -839, 260, -858, 46, -979, -573, 116, 408, 718, -290, -48, 434, -281, 49, 527, -731, 105, 106, -580, -355, 654, -557, -8, -511, 159, -4, -826, -494, 309, -434, -263, -391, -696, 1632, -103, 311, 705, -552, -78, 271, 364, -56, 108, 77},
{350, -317, -609, -186, 135, 255, 176, 439, -575, -70, -228, -1088, -258, -241, -110, 987, 603, -387, -103, 490, -265, 280, 605, -198, -104, 295, -212, -565, 745, -35, -18, -113, -488, -601, -533, -682, 586, 717, -277, -682, -295, -323, 511, 541, 38, 554, 181, 767, -308, -380, 1043, 107, 213, -808, -619, 465, -51, 914, -171, -489, 1, -784, -710, 249, 372, 87, -136, -5, 132, -77},
{-640, 572, 41, 327, -696, 1052, 185, 184, -64, -1216, -285, 678, 1165, 107, 298, -192, 226, -708, 1073, 115, 1180, 260, 517, -575, -1283, 658, -648, 13, -936, -728, -651, 924, -228, -751, -321, -295, -110, 1224, -412, -1789, 374, 324, 161, 215, 318, -144, -561, -389, 755, -694, 835, 658, 601, -44, -790, 309, -441, 394, 280, -230, 896, -450, 10, 271, 532, 59, -62, 13, 25, -47},
{-763, -653, 1018, -574, 101, -385, -1121, 785, -644, 675, -283, 548, -891, -64, -747, 1894, 368, 428, -877, -224, -490, 760, 130, 260, 99, 1033, 1324, -458, 1046, 354, 8, -239, -59, 959, -406, 121, -303, -811, -4, -146, 166, -265, 1329, 508, -618, 1427, -34, -307, 662, 1429, 504, 504, 739, -591, 553, -576, 609, 36, -123, 1562, -920, -329, 459, 133, 23, -51, -273, -231, 411, 38},
{101, -440, -553, 57, 160, 28, 44, 667, 20, -637, -854, -494, -655, -680, 726, -127, -585, -553, 685, 236, 700, -817, 13, 182, 321, -293, 564, 347, -187, -1035, 116, 138, -66, 338, -84, -179, -55, 138, 322, -369, 12, -33, -128, 572, -714, 108, 732, 1172, -967, -110, -123, 3, 313, 447, 243, -215, -512, 347, 169, -30, 690, 935, -329, 175, 664, 401, 587, 220, -17, 1},
{228, -897, -1196, 669, 357, -575, 114, 213, -779, -50, 396, -243, -280, -348, -404, -809, -529, 1123, -213, -1136, -342, -40, -309, 929, 1054, -13, -380, 1032, 1022, -400, 769, -182, 351, 726, 95, 246, 614, 311, 563, 672, -678, 819, -891, -451, 1033, -439, 415, -136, -30, 146, -1548, 372, 439, 95, -70, -388, 249, -575, 561, -1309, 257, 485, 329, 589, -589, 176, 202, -67, 97, 102},
{220, 113, 43, -334, 952, 327, -1396, -412, 697, 1013, -602, 761, 225, 45, 21, -893, -70, 144, 91, 88, 525, -496, 524, 1408, -819, 216, 779, -25, -130, -440, 285, -131, 790, 640, -880, 169, -465, 17, -298, 230, 147, 341, -821, 189, 805, 251, -219, 897, -405, 77, -1033, 143, 242, -573, 1035, 245, -179, 13, 320, -95, -954, 170, -135, 114, -446, -210, -51, 466, -194, -69},
{70, 47, -281, 297, 801, -138, 493, 133, -181, -139, -252, 64, -537, -163, -324, -734, 475, -272, 230, 65, 759, -943, -478, 997, -333, -146, 289, 995, 161, -1245, 135, 263, 1747, -776, -1409, 485, -361, 277, -424, -1145, -1096, -214, 857, 368, -111, 248, -463, 366, -731, 597, 58, -463, 692, 413, -1200, -295, 102, -79, 330, 166, -254, -403, -203, 295, 227, 71, -364, -135, -93, 204},
{193, 865, -23, 51, 50, -28, -210, -10, 1335, -269, -473, 179, 188, 190, -62, 219, -24, -549, 337, -103, -712, -304, 682, -346, 697, -95, 857, -260, 393, -522, 198, 517, 19, 183, 659, 166, -23, -1217, 1034, 892, 568, -96, 129, -140, -268, 6, 127, 131, -2, 814, -361, -120, -174, -117, 758, 431, 385, 157, 351, 732, 186, 717, 322, -98, -35, -249, -245, 363, -351, -105},
{81, 130, -853, 232, -1104, -239, 332, 578, 419, -836, -42, 959, 314, 1381, -212, 128, 302, 508, 910, -330, -382, -49, 927, 9, -340, -189, -268, -1108, -182, -1154, 332, 554, -892, -5, -571, 231, 312, -464, 198, -207, 116, 471, 634, -324, 297, -8, 305, -856, 914, -103, 255, 50, -1094, -691, 333, -320, 623, -414, 162, 996, 746, -1064, 1245, -433, 676, -409, 216, 543, 44, 87},
{-275, 259, -87, -214, 235, 436, 416, 819, -1053, -797, 491, -379, -161, 128, -178, 760, -123, -1018, 147, 772, 960, -304, 872, -113, -38, 484, 815, -552, 717, -668, 204, -787, 133, -275, -721, -103, -568, 76, 682, -1184, 0, -972, 306, -710, -523, 369, 636, 85, 168, -535, 516, -335, -75, 6, -964, -707, 165, -508, 86, 9, 705, -699, -37, 659, 347, 174, -49, -215, 9, 38}};
    }
  }
  cout << "input basis matrices：" << endl;
  print_mat(b);
  
  cout << "blocksize?" <<endl;
  cin >> beta;
  cout << "reduce parameter?" << endl;
  cin >> delta;
  clock_t start = clock();
  //BKZb = BKZ(b, beta, delta);
  sv = SVP_BKZ(b, beta, delta, 2143);
  clock_t end = clock();
  cout << "----------------------------------------" << endl;
  print_vec(sv);
  /*
  cout << "\nBKZ_reduced basis matrices:" << endl;
  print_mat(BKZb);
  cout << "----------------------------------------" << endl;
  cout << "The 1st vector of this matrices:" << endl;
  print_vec(BKZb.at(0));
  cout << "norm=" << sqrt(dot(BKZb.at(0), BKZb.at(0))) << endl;
  */
  cout << "----------------------------------------" << endl;
  cout << "Run time = " << (double)(end - start) / CLOCKS_PER_SEC << "[secs]" << endl;
  /*
  cout << "----------------------------------------" << endl;
  if(check_BKZ(BKZb, beta)){
    cout << "BKZ-reduction is succes!\n";
  }else{
    cout << "error\n" << check_BKZ(BKZb, beta) <<endl;
  }
  */
  sv.shrink_to_fit();
  b.shrink_to_fit();
  BKZb.shrink_to_fit();
  return 0;
}
/*38~*/