Changeset 287cc8 in git

Timestamp:

Jan 5, 2010, 5:51:13 PM (13 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

3c38b3810fd61108b01f123f5a91e13ccff52b20

Parents:

1d43d184dd871d77c1ba8e095d768f22a0fbe92f

Message:

ntl 5.5.2

git-svn-id: file:///usr/local/Singular/svn/trunk@12402 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

ntl

Files:

• COPYING (modified) (1 diff)
• doc/ZZ.txt (modified) (1 diff)
• doc/tour-changes.html (modified) (1 diff)
• doc/tour-unix.html (modified) (1 diff)
• include/NTL/ZZ.h (modified) (1 diff)
• include/NTL/c_lip.h (modified) (2 diffs)
• include/NTL/g_lip.h (modified) (2 diffs)
• include/NTL/tools.h (modified) (1 diff)
• include/NTL/version.h (modified) (1 diff)
• src/CanZassTest.c (modified) (1 diff)
• src/DIRNAME (modified) (1 diff)
• src/DoConfig (modified) (3 diffs)
• src/FFT.c (modified) (15 diffs)
• src/FacVec.c (modified) (1 diff)
• src/GF2.c (modified) (1 diff)
• src/GF2E.c (modified) (7 diffs)
• src/GF2EX.c (modified) (62 diffs)
• src/GF2EXFactoring.c (modified) (43 diffs)
• src/GF2X.c (modified) (42 diffs)
• src/GF2X1.c (modified) (106 diffs)
• src/GF2XFactoring.c (modified) (14 diffs)
• src/GF2XTest.c (modified) (2 diffs)
• src/GF2XTimeTest.c (modified) (3 diffs)
• src/GF2XVec.c (modified) (2 diffs)
• src/G_LLL_FP.c (modified) (52 diffs)
• src/G_LLL_QP.c (modified) (69 diffs)
• src/G_LLL_RR.c (modified) (46 diffs)
• src/G_LLL_XD.c (modified) (46 diffs)
• src/HNF.c (modified) (2 diffs)
• src/LLL.c (modified) (17 diffs)
• src/LLL_FP.c (modified) (54 diffs)
• src/LLL_QP.c (modified) (70 diffs)
• src/LLL_RR.c (modified) (40 diffs)
• src/LLL_XD.c (modified) (42 diffs)
• src/MakeDesc.c (modified) (32 diffs)
• src/MakeDescAux.c (modified) (1 diff)
• src/MoreFacTest.c (modified) (1 diff)
• src/MulTimeTest.c (modified) (5 diffs)
• src/Poly1TimeTest.c (modified) (2 diffs)
• src/PolyTimeTest.c (modified) (2 diffs)
• src/QuickTest.c (modified) (9 diffs)
• src/RR.c (modified) (28 diffs)
• src/TestGetTime.c (modified) (2 diffs)
• src/VERSION_INFO (modified) (1 diff)
• src/WINDIR (modified) (1 diff)
• src/WordVector.c (modified) (10 diffs)
• src/ZZ.c (modified) (44 diffs)
• src/ZZVec.c (modified) (2 diffs)
• src/ZZX.c (modified) (14 diffs)
• src/ZZX1.c (modified) (44 diffs)
• src/ZZXFacTest.c (modified) (3 diffs)
• src/ZZXFactoring.c (modified) (108 diffs)
• src/ZZ_p.c (modified) (8 diffs)
• src/ZZ_pE.c (modified) (5 diffs)
• src/ZZ_pEX.c (modified) (57 diffs)
• src/ZZ_pEXFactoring.c (modified) (31 diffs)
• src/ZZ_pEXTest.c (modified) (1 diff)
• src/ZZ_pX.c (modified) (53 diffs)
• src/ZZ_pX1.c (modified) (56 diffs)
• src/ZZ_pXCharPoly.c (modified) (2 diffs)
• src/ZZ_pXFactoring.c (modified) (37 diffs)
• src/c_lip_impl.h (modified) (161 diffs)
• src/ctools.c (modified) (1 diff)
• src/g_lip_impl.h (modified) (109 diffs)
• src/gen_lip_gmp_aux.c (modified) (15 diffs)
• src/lzz_p.c (modified) (5 diffs)
• src/lzz_pE.c (modified) (5 diffs)
• src/lzz_pEX.c (modified) (55 diffs)
• src/lzz_pEXFactoring.c (modified) (31 diffs)
• src/lzz_pEXTest.c (modified) (1 diff)
• src/lzz_pX.c (modified) (55 diffs)
• src/lzz_pX1.c (modified) (48 diffs)
• src/lzz_pXCharPoly.c (modified) (2 diffs)
• src/lzz_pXFactoring.c (modified) (37 diffs)
• src/mat_GF2.c (modified) (15 diffs)
• src/mat_GF2E.c (modified) (10 diffs)
• src/mat_RR.c (modified) (14 diffs)
• src/mat_ZZ.c (modified) (26 diffs)
• src/mat_ZZ_p.c (modified) (11 diffs)
• src/mat_ZZ_pE.c (modified) (9 diffs)
• src/mat_lzz_p.c (modified) (21 diffs)
• src/mat_lzz_pE.c (modified) (9 diffs)
• src/mat_poly_ZZ_p.c (modified) (1 diff)
• src/mat_poly_lzz_p.c (modified) (1 diff)
• src/mfile (modified) (2 diffs)
• src/newnames.c (modified) (1 diff)
• src/quad_float.c (modified) (30 diffs)
• src/subset.c (modified) (7 diffs)
• src/tools.c (modified) (1 diff)
• src/vec_GF2.c (modified) (7 diffs)
• src/vec_GF2E.c (modified) (3 diffs)
• src/vec_ZZ_p.c (modified) (2 diffs)
• src/vec_ZZ_pE.c (modified) (1 diff)
• src/vec_double.c (modified) (1 diff)
• src/vec_long.c (modified) (1 diff)
• src/vec_lzz_p.c (modified) (5 diffs)
• src/vec_lzz_pE.c (modified) (1 diff)
• src/vec_ulong.c (modified) (1 diff)
• src/xdouble.c (modified) (16 diffs)

ntl/COPYING

@@ -1 +1 @@
 
                   COPYRIGHT NOTICE
-                    for NTL 5.4
+                    for NTL 5.5
           (modified for Singular 2-0-6 - 3-1)
 
 NTL -- A Library for Doing Number Theory
-Copyright (C) 1996-2005  Victor Shoup
+Copyright (C) 1996-2009  Victor Shoup
 
 The most recent version of NTL is available at http://www.shoup.net

ntl/doc/ZZ.txt

@@ -141 +141 @@
 // PROMOTIONS: operator * and procedure mul support promotion
 // from long to ZZ on (a, b).
+
+/**************************************************************************\
+
+                            Combined Multiply and Add 
+
+\**************************************************************************/
+
+
+void MulAddTo(ZZ& x, const ZZ& a, const ZZ& b); // x += a*b
+void MulAddTo(ZZ& x, const ZZ& a, long b);      // x += a*b
+
+
+void MulSubFrom(ZZ& x, const ZZ& a, const ZZ& b); // x -= a*b
+void MulSubFrom(ZZ& x, const ZZ& a, long b);      // x -= a*b
+
+// NOTE: these are provided for both convenience and efficiency.
+// The single-precision versions may be significantly
+// faster than the code sequence 
+//   mul(tmp, a, b); add(x, x, tmp);
+
 
 

ntl/doc/tour-changes.html

@@ -17 +17 @@
 </p>
 </h1>
+
+<p> <hr> <p>
+<h3>
+2009.08.14: Changes between NTL 5.5.1 and 5.5.2
+</h3>
+
+<ul>
+<li>
+New routines <tt>MulAddTo</tt> and <tt>MulSubFrom</tt>
+for computing <tt>x += a*b</tt> and <tt>x -= a*b</tt>,
+where <tt>x</tt> and <tt>a</tt> are <tt>ZZ</tt>'s and
+<tt>b</tt> is a <tt>ZZ</tt> or a <tt>long</tt>.
+In the case where <tt>b</tt> is a <tt>long</tt>,
+this may be much faster than writing 
+<tt>mul(t, a, b); add(x, x, t)</tt>.
+See <a href="ZZ.txt">ZZ.txt</a> for details.
+
+These new routines are used in a number of places in
+NTL to get faster algorithms (for example, the <tt>LLL</tt> routine).
+
+<li>
+Fixed a relatively benign indexing bug in <tt>GF2EX</tt>
+discovered by Berend-Benjamin Tams using the <tt>valgrind</tt> tool.
+
+
+
+
+</ul>
 
 <p> <hr> <p>

ntl/doc/tour-unix.html

@@ -502 +502 @@
 in this case, you will want to set
 <tt>LIBTOOL=glibtool</tt>.  
-On other systems, it may be necssary to downlaod and
+On other systems, it may be necssary to download and
 install a fresh copy of the libtool program (which can be obtained from
 <a href="http://www.gnu.org/software/libtool">here</a>). 

ntl/include/NTL/ZZ.h

@@ -421 +421 @@
   { mul(x, x, a); return x; }
 
+// x += a*b
+
+inline void
+MulAddTo(ZZ& x, const ZZ& a, long b)
+{
+   NTL_zsaddmul(a.rep, b, &x.rep);
+}
+
+inline void
+MulAddTo(ZZ& x, const ZZ& a, const ZZ& b)
+{
+   NTL_zaddmul(a.rep, b.rep, &x.rep);
+}
+
+// x -= a*b
+
+inline void
+MulSubFrom(ZZ& x, const ZZ& a, long b)
+{
+   NTL_zssubmul(a.rep, b, &x.rep);
+}
+
+inline void
+MulSubFrom(ZZ& x, const ZZ& a, const ZZ& b)
+{
+   NTL_zsubmul(a.rep, b.rep, &x.rep);
+}
+
 
 // Special routines for implementing CRT in ZZ_pX arithmetic

ntl/include/NTL/c_lip.h

@@ -193 +193 @@
           The division is performed in place (but may sometimes
           cause *r to grow by one digit) */
+
+    void _ntl_zsaddmul(_ntl_verylong x, long y,  _ntl_verylong *ww);
+      /* *ww += x*y */
+
+    void _ntl_zaddmul(_ntl_verylong x, _ntl_verylong y,  _ntl_verylong *ww);
+      /* *ww += x*y */
+
+    void _ntl_zssubmul(_ntl_verylong x, long y,  _ntl_verylong *ww);
+      /* *ww -= x*y */
+
+    void _ntl_zsubmul(_ntl_verylong x, _ntl_verylong y,  _ntl_verylong *ww);
+      /* *ww -= x*y */
+
 
 /********************************************************************
@@ -642 +655 @@
 #define NTL_zzero _ntl_zzero1
 
+#define NTL_zsaddmul _ntl_zsaddmul
+#define NTL_zaddmul _ntl_zaddmul
+#define NTL_zssubmul _ntl_zssubmul
+#define NTL_zsubmul _ntl_zsubmul
+

ntl/include/NTL/g_lip.h

@@ -95 +95 @@
           assumes b > 0 and *r >= 0;
           cause *r to grow by one digit) */
+
+    void _ntl_gsaddmul(_ntl_gbigint x, long y,  _ntl_gbigint *ww);
+      /* *ww += x*y */
+
+    void _ntl_gaddmul(_ntl_gbigint x, _ntl_gbigint y,  _ntl_gbigint *ww);
+      /* *ww += x*y */
+
+    void _ntl_gssubmul(_ntl_gbigint x, long y,  _ntl_gbigint *ww);
+      /* *ww -= x*y */
+
+    void _ntl_gsubmul(_ntl_gbigint x, _ntl_gbigint y,  _ntl_gbigint *ww);
+      /* *ww -= x*y */
+
 
 /********************************************************************
@@ -529 +542 @@
 #define NTL_zzero _ntl_gzero
 
+#define NTL_zsaddmul _ntl_gsaddmul
+#define NTL_zaddmul _ntl_gaddmul
+#define NTL_zssubmul _ntl_gssubmul
+#define NTL_zsubmul _ntl_gsubmul
+
 #define NTL_GMP_LIP
 

ntl/include/NTL/tools.h

@@ -251 +251 @@
 #endif
 long IsWhiteSpace(long c);
+long IsEOFChar(long c);
 
 long CharToIntVal(long c);

ntl/include/NTL/version.h

@@ -3 +3 @@
 #define NTL_version__H
 
-#define NTL_VERSION "5.5.1"
+#define NTL_VERSION "5.5.2"
 
 #define NTL_MAJOR_VERSION  (5)
 #define NTL_MINOR_VERSION  (5)
-#define NTL_REVISION       (1)
+#define NTL_REVISION       (2)
 
 #endif

ntl/src/CanZassTest.c

@@ -73 +73 @@
 
    cerr << "\n";
- 
+
 
    cout << factors << "\n";

ntl/src/DIRNAME

@@ -1 @@
-ntl-5.5.1
+ntl-5.5.2

ntl/src/DoConfig

@@ -86 +86 @@
 
 
+%Variable = ();
+
+
 foreach $arg (@ARGV) {
 
@@ -94 +97 @@
 
    if (($name, $val) = ($arg =~ /(.*?)=(.*)/)) {
+
+      $Variable{$name} = 0;
       
       if (exists($MakeFlag{$name}) && ($val =~ 'on|off')) {
@@ -139 +144 @@
 }
 
-# a special MakeVal value that is determined by NTL_GMP_LIP 
-# and NTL_GMP_HACK
-
+# special GMP variables
+
+$MakeVal{'GMPI'} = '# ';
+$MakeVal{'GMPL'} = '# ';
+$MakeVal{'GMP'} =  '# ';
 
 if ($ConfigFlag{'NTL_GMP_LIP'} eq 'on' || $ConfigFlag{'NTL_GMP_HACK'} eq 'on') {
    $MakeVal{'GMP'} = '';
-}
-else {
-   $MakeVal{'GMP'} = '# ';
-}
-
-# a special MakeVal value that is determined by NTL_GF2X_LIB
+   if (exists($Variable{'DEF_PREFIX'}) ||
+       exists($Variable{'GMP_PREFIX'}) ||
+       exists($Variable{'GMP_INCDIR'})) {
+      $MakeVal{'GMPI'} = '';
+   }
+   if (exists($Variable{'DEF_PREFIX'}) ||
+       exists($Variable{'GMP_PREFIX'}) ||
+       exists($Variable{'GMP_LIBDIR'})) {
+      $MakeVal{'GMPL'} = '';
+   }
+}
+
+# special GF2X variables
+
+
+$MakeVal{'GF2XI'} = '# ';
+$MakeVal{'GF2XL'} = '# ';
+$MakeVal{'GF2X'} =  '# ';
 
 
 if ($ConfigFlag{'NTL_GF2X_LIB'} eq 'on') {
    $MakeVal{'GF2X'} = '';
-}
-else {
-   $MakeVal{'GF2X'} = '# ';
+   if (exists($Variable{'DEF_PREFIX'}) ||
+       exists($Variable{'GF2X_PREFIX'}) ||
+       exists($Variable{'GF2X_INCDIR'})) {
+      $MakeVal{'GF2XI'} = '';
+   }
+   if (exists($Variable{'DEF_PREFIX'}) ||
+       exists($Variable{'GF2X_PREFIX'}) ||
+       exists($Variable{'GF2X_LIBDIR'})) {
+      $MakeVal{'GF2XL'} = '';
+   }
 }
 

ntl/src/FFT.c

@@ -29 +29 @@
 
    if (n % 7 == 0) return 0;
-   
+
    m = n - 1;
    k = 0;
@@ -54 +54 @@
       if (z != 1 || y !=  n-1) return 0;
 
-      if (j == k) 
+      if (j == k)
          break;
    }
@@ -65 +65 @@
    if (TrialBound > 0) {
       if (!ProbPrime(n, 5)) return 0;
-   
+
       /* we have to do trial division by special numbers */
-   
+
       TrialBound = SqrRoot(TrialBound);
-   
+
       long a, b;
-   
+
       for (a = 1; a <= TrialBound; a++) {
          b = (a << k) + 1;
-         if (n % b == 0) return 0; 
+         if (n % b == 0) return 0;
       }
    }
@@ -127 +127 @@
       return NTL_FFTMaxRoot;
    else
-      return k; 
+      return k;
 }
 
@@ -146 +146 @@
    // tables are allocated in increments of 100
 
-   if (index == 0) { 
+   if (index == 0) {
       FFTPrime = (long *) NTL_MALLOC(100, sizeof(long), 0);
       RootTable = (long **) NTL_MALLOC(100, sizeof(long *), 0);
@@ -155 +155 @@
    else if ((index % 100) == 0) {
       FFTPrime = (long *) NTL_REALLOC(FFTPrime, index+100, sizeof(long), 0);
-      RootTable = (long **) 
+      RootTable = (long **)
                   NTL_REALLOC(RootTable, index+100, sizeof(long *), 0);
-      RootInvTable = (long **) 
+      RootInvTable = (long **)
                      NTL_REALLOC(RootInvTable, index+100, sizeof(long *), 0);
-      TwoInvTable = (long **) 
+      TwoInvTable = (long **)
                     NTL_REALLOC(TwoInvTable, index+100, sizeof(long *), 0);
-      FFTPrimeInv = (double *) 
+      FFTPrimeInv = (double *)
                     NTL_REALLOC(FFTPrimeInv, index+100, sizeof(double), 0);
    }
 
    if (!FFTPrime || !RootTable || !RootInvTable || !TwoInvTable ||
-       !FFTPrimeInv) 
+       !FFTPrimeInv)
       Error("out of space");
 
@@ -200 +200 @@
    NumFFTPrimes++;
 }
-   
+
 
 static
@@ -207 +207 @@
    long j, m;
 
-   j = k; 
+   j = k;
    m = 1L << (k-1);
 
@@ -272 +272 @@
    // assume k > 1
 
-   
+
 
    static long tab_size = 0;
@@ -282 +282 @@
 
       wtab = (long *) NTL_MALLOC(1L << (k-2), sizeof(long), 0);
-      wqinvtab = (mulmod_precon_t *) 
+      wqinvtab = (mulmod_precon_t *)
                  NTL_MALLOC(1L << (k-2), sizeof(mulmod_precon_t), 0);
       if (!wtab || !wqinvtab) Error("out of space");
@@ -290 +290 @@
 
       wtab = (long *) NTL_REALLOC(wtab, 1L << (k-2), sizeof(long), 0);
-      wqinvtab = (mulmod_precon_t *) 
+      wqinvtab = (mulmod_precon_t *)
                  NTL_REALLOC(wqinvtab, 1L << (k-2), sizeof(mulmod_precon_t), 0);
       if (!wtab || !wqinvtab) Error("out of space");
@@ -320 +320 @@
    }
 
-   
-  
+
+
    for (s = 2; s < k; s++) {
       m = 1L << s;
@@ -341 +341 @@
       for (i = 0; i < n; i+= m) {
 
-          
+
          t = A[i + m_half];
          u = A[i];
@@ -402 +402 @@
       t = MulModPrecon(A[j + m_half], wtab[j >> 1], q, wqinvtab[j >> 1]);
       u = A[j];
-      t1 = MulModPrecon(A[j + 1+ m_half], wtab[j >> 1], q, 
+      t1 = MulModPrecon(A[j + 1+ m_half], wtab[j >> 1], q,
                         wqinvtab[j >> 1]);
       t1 = MulModPrecon(t1, w, q, wqinv);
@@ -411 +411 @@
       A[j + 1] = AddMod(u1, t1, q);
       A[j + 1 + m_half] = SubMod(u1, t1, q);
-     
+
    }
 }

ntl/src/FacVec.c

@@ -60 +60 @@
             (fvec[NumFactors].a)++;
             fvec[NumFactors].val *= q;
-         }         
+         }
          fvec[NumFactors].link = -1;
          NumFactors++;

ntl/src/GF2.c

@@ -38 +38 @@
    }
 
-   if (e < 0 && a == 0) 
+   if (e < 0 && a == 0)
       Error("GF2: division by zero");
 

ntl/src/GF2E.c

@@ -26 +26 @@
    else if (p.size == 6)
       KarCross = 3;
-   else 
+   else
       KarCross = 2;
 
@@ -57 +57 @@
    else if (p.size <= 13)
       DivCross = 100;
-   else 
+   else
       DivCross = 75;
 
@@ -80 +80 @@
 
 
-GF2EInfoT *GF2EInfo = 0; 
+GF2EInfoT *GF2EInfo = 0;
 
 
@@ -87 +87 @@
 
 
-static 
+static
 void CopyPointer(GF2EInfoPtr& dst, GF2EInfoPtr src)
 {
@@ -95 +95 @@
       dst->ref_count--;
 
-      if (dst->ref_count < 0) 
+      if (dst->ref_count < 0)
          Error("internal error: negative GF2EContext ref_count");
 
@@ -102 +102 @@
 
    if (src) {
-      if (src->ref_count == NTL_MAX_LONG) 
+      if (src->ref_count == NTL_MAX_LONG)
          Error("internal error: GF2EContext ref_count overflow");
 
@@ -111 +111 @@
    dst = src;
 }
-   
+
 
 

ntl/src/GF2EX.c

@@ -56 +56 @@
    long j, m;
 
-   if (i < 0) 
+   if (i < 0)
       Error("SetCoeff: negative index");
 
@@ -63 +63 @@
 
    m = deg(x);
+
+   if (i > m && IsZero(a)) return;
 
    if (i > m) {
@@ -114 +116 @@
    long j, m;
 
-   if (i < 0) 
+   if (i < 0)
       Error("coefficient index out of range");
 
@@ -143 +145 @@
    return deg(a) == 1 && IsOne(LeadCoeff(a)) && IsZero(ConstTerm(a));
 }
-      
-      
+
+
 
 const GF2E& coeff(const GF2EX& a, long i)
@@ -210 +212 @@
 {
    GF2X a = aa; // in case a aliases the rep of a coefficient of x
-   
+
    long n = deg(a)+1;
    long i;
@@ -235 +237 @@
 
    long i;
-   const GF2E *ap, *bp; 
+   const GF2E *ap, *bp;
    GF2E* xp;
 
@@ -326 +328 @@
    const GF2E *ap, *bp;
    GF2E *xp;
-   
+
    GF2EX la, lb;
 
@@ -388 +390 @@
 
 
-static 
+static
 void PlainMul1(GF2X *xp, const GF2X *ap, long sa, const GF2X& b)
 {
@@ -506 +508 @@
 
 static
-void KarMul(GF2X *c, const GF2X *a, 
+void KarMul(GF2X *c, const GF2X *a,
             long sa, const GF2X *b, long sb, GF2X *stk)
 {
@@ -514 +516 @@
    }
 
-   if (sb == 1) {  
-      if (sa == 1) 
+   if (sb == 1) {
+      if (sa == 1)
          mul(*c, *a, *b);
       else
@@ -531 +533 @@
       q_add(c[1], c[1], c[0]);
       q_add(c[1], c[1], c[2]);
-      
+
       return;
    }
@@ -618 +620 @@
          cp[i] = (ap[i+wn] >> bn) | (ap[i+wn+1] << (NTL_BITS_PER_LONG - bn));
 
-      if ((k + n) % NTL_BITS_PER_LONG != 0)
+      if (k > sc*NTL_BITS_PER_LONG - bn)
          cp[sc-1] = (ap[sc+wn-1] >> bn)|(ap[sc+wn] << (NTL_BITS_PER_LONG - bn));
       else
@@ -625 +627 @@
 
    long p = k % NTL_BITS_PER_LONG;
-   if (p != 0) 
+   if (p != 0)
       cp[sc-1] &= ((1UL << p) - 1UL);
 
@@ -649 +651 @@
       paa[i] = 0;
 
-   for (i = 0; i < sa; i++) 
+   for (i = 0; i < sa; i++)
       ShiftAdd(paa, rep(a.rep[i]).xrep.elts(), rep(a.rep[i]).xrep.length(),
                blocksz*i);
 
-   aa.normalize(); 
+   aa.normalize();
 }
 
@@ -736 +738 @@
       return;
    }
-   
+
 
    /* karatsuba */
@@ -751 +753 @@
 
    GF2XVec stk;
-   stk.SetSize(sp + 2*(sa+sb)-1, 2*GF2E::WordLength()); 
+   stk.SetSize(sp + 2*(sa+sb)-1, 2*GF2E::WordLength());
 
    long i;
@@ -761 +763 @@
       stk[i+2*sa+sb-1] = rep(b.rep[i]);
 
-   KarMul(&stk[0], &stk[sa+sb-1], sa, &stk[2*sa+sb-1], sb, 
+   KarMul(&stk[0], &stk[sa+sb-1], sa, &stk[2*sa+sb-1], sb,
           &stk[2*(sa+sb)-1]);
 
@@ -1168 +1170 @@
 
 
-   inv(t, LeadCoeff(x)); 
-   mul(x, x, t); 
-}
-
-
-
-         
+   inv(t, LeadCoeff(x));
+   mul(x, x, t);
+}
+
+
+
+
 
 void XGCD(GF2EX& d, GF2EX& s, GF2EX& t, const GF2EX& a, const GF2EX& b)
@@ -1194 +1196 @@
       long e = max(deg(a), deg(b)) + 1;
 
-      GF2EX temp(INIT_SIZE, e), u(INIT_SIZE, e), v(INIT_SIZE, e), 
-            u0(INIT_SIZE, e), v0(INIT_SIZE, e), 
-            u1(INIT_SIZE, e), v1(INIT_SIZE, e), 
+      GF2EX temp(INIT_SIZE, e), u(INIT_SIZE, e), v(INIT_SIZE, e),
+            u0(INIT_SIZE, e), v0(INIT_SIZE, e),
+            u1(INIT_SIZE, e), v1(INIT_SIZE, e),
             u2(INIT_SIZE, e), v2(INIT_SIZE, e), q(INIT_SIZE, e);
 
@@ -1236 +1238 @@
 void MulMod(GF2EX& x, const GF2EX& a, const GF2EX& b, const GF2EX& f)
 {
-   if (deg(a) >= deg(f) || deg(b) >= deg(f) || deg(f) == 0) 
+   if (deg(a) >= deg(f) || deg(b) >= deg(f) || deg(f) == 0)
       Error("MulMod: bad args");
 
@@ -1350 +1352 @@
 
    for (i = 0; i < n; i++)
-      random(x.rep[i]); 
+      random(x.rep[i]);
 
    x.normalize();
@@ -1381 +1383 @@
 
    x.normalize();
-} 
+}
 
 
@@ -1387 +1389 @@
 void trunc(GF2EX& x, const GF2EX& a, long m)
 
-// x = a % X^m, output may alias input 
+// x = a % X^m, output may alias input
 
 {
@@ -1791 +1793 @@
    return k;
 }
-      
+
 
 
@@ -1857 +1859 @@
 
    v[0] = g;
- 
+
    if (k > 1) {
       GF2EX t;
@@ -1873 +1875 @@
    val = 0;
    for (i = n-1; i >= 0; i--) {
-      val = (val << 1) | bit(e, i); 
+      val = (val << 1) | bit(e, i);
       if (val == 0)
          SqrMod(res, res, F);
@@ -1905 +1907 @@
 }
 
-   
+
 
 
@@ -1938 +1940 @@
 
 
-      
+
 
 
@@ -1958 +1960 @@
    mul(P1, P2, b);
    add(P1, P1, a);
-   
+
    r = P1;
 }
@@ -1979 +1981 @@
    mul(P1, P2, b);
    add(P1, P1, a);
-   
+
    r = P1;
    q = P2;
@@ -1999 +2001 @@
    mul(P2, P1, P2);
    RightShift(P2, P2, da-db);
-   
+
    q = P2;
 }
@@ -2059 +2061 @@
    q = a;
 }
-   
+
 
 
@@ -2121 +2123 @@
    long da = deg(a);
    long i;
- 
+
    if (da < n) {
       clear(x);
@@ -2147 +2149 @@
 
    if (n < 0) {
-      if (n < -NTL_MAX_LONG) 
+      if (n < -NTL_MAX_LONG)
          clear(x);
       else
@@ -2214 +2216 @@
       mul(a[0], a[0], b);
    }
-} 
+}
 
 
@@ -2266 +2268 @@
    b.SetLength(m);
    long i;
-   for (i = 0; i < m; i++) 
+   for (i = 0; i < m; i++)
       eval(b[i], f, a[i]);
 }
@@ -2341 +2343 @@
 }
 
-   
-void InnerProduct(GF2EX& x, const vec_GF2E& v, long low, long high, 
+
+void InnerProduct(GF2EX& x, const vec_GF2E& v, long low, long high,
                    const vec_GF2EX& H, long n, GF2XVec& t)
 {
@@ -2370 +2372 @@
 
 
-void CompMod(GF2EX& x, const GF2EX& g, const GF2EXArgument& A, 
+void CompMod(GF2EX& x, const GF2EX& g, const GF2EXArgument& A,
              const GF2EXModulus& F)
 {
@@ -2420 +2422 @@
    set(A.H[0]);
    A.H[1] = h;
-   for (i = 2; i <= m; i++) 
+   for (i = 2; i <= m; i++)
       MulMod(A.H[i], A.H[i-1], h, F);
 }
@@ -2475 +2477 @@
 }
 
-void Comp3Mod(GF2EX& x1, GF2EX& x2, GF2EX& x3, 
+void Comp3Mod(GF2EX& x1, GF2EX& x2, GF2EX& x3,
               const GF2EX& g1, const GF2EX& g2, const GF2EX& g3,
               const GF2EX& h, const GF2EXModulus& F)
@@ -2527 +2529 @@
       B.shamt_fbi = 0;
    else
-      B.shamt_fbi = F.n-2 - d; 
+      B.shamt_fbi = F.n-2 - d;
 
    CopyReverse(B.fbi, t, d);
 
-   // The following code optimizes the case when 
+   // The following code optimizes the case when
    // f = X^n + low degree poly
 
@@ -2574 +2576 @@
 
 
-void UpdateMap(vec_GF2E& x, const vec_GF2E& a, 
+void UpdateMap(vec_GF2E& x, const vec_GF2E& a,
          const GF2EXTransMultiplier& B, const GF2EXModulus& F)
 {
@@ -2581 +2583 @@
    x = xx.rep;
 }
-   
+
 
 
 static
-void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, 
+void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k,
                    const GF2EXArgument& H, const GF2EXModulus& F)
 {
-   if (k < 0 || NTL_OVERFLOW(k, 1, 0) || deg(a) >= F.n) 
+   if (k < 0 || NTL_OVERFLOW(k, 1, 0) || deg(a) >= F.n)
       Error("ProjectPowers: bad args");
 
@@ -2614 +2616 @@
 
 static
-void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, const GF2EX& h, 
+void ProjectPowers(vec_GF2E& x, const GF2EX& a, long k, const GF2EX& h,
                    const GF2EXModulus& F)
 {
@@ -2639 +2641 @@
 }
 
-void ProjectPowers(vec_GF2E& x, const vec_GF2E& a, long k, 
+void ProjectPowers(vec_GF2E& x, const vec_GF2E& a, long k,
                    const GF2EX& h, const GF2EXModulus& F)
 {
@@ -2704 +2706 @@
    }
 
-   // cerr << "finished: " << L << " " << deg(Lambda) << "\n"; 
+   // cerr << "finished: " << L << " " << deg(Lambda) << "\n";
 
    dl = deg(Lambda);
@@ -2726 +2728 @@
 
 
-void DoMinPolyMod(GF2EX& h, const GF2EX& g, const GF2EXModulus& F, long m, 
+void DoMinPolyMod(GF2EX& h, const GF2EX& g, const GF2EXModulus& F, long m,
                const GF2EX& R)
 {
@@ -2770 +2772 @@
    GF2EX R;
    GF2EXTransMultiplier H1;
-   
+
 
    for (;;) {
@@ -2839 +2841 @@
    GF2EX lq, r;
    DivRem(lq, r, a, b);
-   if (!IsZero(r)) return 0; 
+   if (!IsZero(r)) return 0;
    q = lq;
    return 1;
@@ -2849 +2851 @@
    GF2EX lq, r;
    DivRem(lq, r, a, b);
-   if (!IsZero(r)) return 0; 
+   if (!IsZero(r)) return 0;
    return 1;
 }
@@ -2914 +2916 @@
    res.SetMaxLength(da*e + 1);
    res = 1;
-   
+
    long k = NumBits(e);
    long i;
@@ -3025 +3027 @@
       Error("trace: bad args");
 
-   if (F.tracevec.length() == 0) 
+   if (F.tracevec.length() == 0)
       ComputeTraceVec(F);
 
@@ -3043 +3045 @@
 {
    GF2E res;
- 
+
    if (IsZero(a) || IsZero(b))
       clear(res);
-   else if (deg(a) == 0 && deg(b) == 0) 
+   else if (deg(a) == 0 && deg(b) == 0)
       set(res);
    else {
@@ -3081 +3083 @@
             else
                clear(res);
-        
+
             break;
          }
@@ -3092 +3094 @@
 void resultant(GF2E& rres, const GF2EX& a, const GF2EX& b)
 {
-   PlainResultant(rres, a, b); 
+   PlainResultant(rres, a, b);
 }
 
@@ -3098 +3100 @@
 void NormMod(GF2E& x, const GF2EX& a, const GF2EX& f)
 {
-   if (deg(f) <= 0 || deg(a) >= deg(f)) 
+   if (deg(f) <= 0 || deg(a) >= deg(f))
       Error("norm: bad args");
 
@@ -3179 +3181 @@
 
 
-void CompTower(GF2EX& x, const GF2X& g, const GF2EX& h, 
+void CompTower(GF2EX& x, const GF2X& g, const GF2EX& h,
              const GF2EXModulus& F)
    // x = g(h) mod f
@@ -3213 +3215 @@
 }
 
-void ProjectedInnerProduct(GF2& x, const vec_GF2E& a, 
+void ProjectedInnerProduct(GF2& x, const vec_GF2E& a,
                            const vec_vec_GF2& b)
 {
@@ -3317 +3319 @@
 
    ProjectPowersTower(x, R, 2*m, g, F, proj);
-   
+
    MinPolySeq(h, x, m);
 }
 
 
-void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F, 
+void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F,
                       long m)
 {
@@ -3339 +3341 @@
 }
 
-void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F, 
+void ProbMinPolyTower(GF2X& h, const GF2EX& g, const GF2EXModulus& F,
                       long m, const vec_GF2& proj)
 {
@@ -3380 +3382 @@
    vec_GF2E R;
    GF2EXTransMultiplier H1;
-   
+
 
    for (;;) {
@@ -3393 +3395 @@
       CompTower(h3, h2, g, F);
       MulMod(h1, h3, h1, F);
-      if (IsZero(h1)) { 
-         hh = h; 
-         return; 
+      if (IsZero(h1)) {
+         hh = h;
+         return;
       }
    }

ntl/src/GF2EXFactoring.c

@@ -29 +29 @@
    c = res;
 }
-   
+
 
 
@@ -79 +79 @@
          d = deg(r)/2;
          f.rep.SetLength(d+1);
-         for (k = 0; k <= d; k++) 
+         for (k = 0; k <= d; k++)
             IterSqr(f.rep[k], r.rep[k*2], GF2E::degree()-1);
          m = m*2;
@@ -85 +85 @@
    } while (!finished);
 }
-         
+
 
 
@@ -216 +216 @@
    SetX(res);
    long i;
-   for (i = 0; i < GF2E::degree(); i++) 
+   for (i = 0; i < GF2E::degree(); i++)
       SqrMod(res, res, F);
 
@@ -241 +241 @@
          long m1 = 2*m;
          if (i & d) m1++;
-   
+
          if (m1 >= NTL_BITS_PER_LONG-1 || (1L << m1) >= n) break;
-   
+
          m = m1;
          i = i >> 1;
@@ -290 +290 @@
          long m1 = 2*m;
          if (i & d) m1++;
-   
+
          if (m1 >= NTL_BITS_PER_LONG-1 || (1L << m1) >= n) break;
-   
+
          m = m1;
          i = i >> 1;
@@ -344 +344 @@
 
 
-   
+
 
 
@@ -359 +359 @@
       return;
    }
-      
+
    GF2EX h;
 
    GF2E r;
 
-   
+
    {
       GF2EXModulus F;
@@ -379 +379 @@
 
    RecFindRoots(x, h);
-   div(h, f, h); 
+   div(h, f, h);
    RecFindRoots(x, h);
 }
@@ -435 +435 @@
 static
 void split(GF2EX& f1, GF2EX& g1, GF2EX& f2, GF2EX& g2,
-           const GF2EX& f, const GF2EX& g, 
+           const GF2EX& f, const GF2EX& g,
            const vec_GF2E& roots, long lo, long mid)
 {
@@ -456 +456 @@
 
    GCD(f1, a, f);
-   
+
    div(f2, f, f1);
 
@@ -520 +520 @@
 
 
-   
+
 
 void SFBerlekamp(vec_GF2EX& factors, const GF2EX& ff, long verbose)
@@ -619 +619 @@
       Error("berlekamp: bad args");
 
-   
+
    SquareFreeDecomp(sfd, f);
 
@@ -644 +644 @@
 
 static
-void ProcessTable(GF2EX& f, vec_pair_GF2EX_long& factors, 
+void ProcessTable(GF2EX& f, vec_pair_GF2EX_long& factors,
                   const GF2EXModulus& F, long limit, const vec_GF2EX& tbl,
                   long d, long verbose)
@@ -681 +681 @@
 
    while (2*d <= deg(t1)) {
-      GCD(t2, tbl[i], t1); 
+      GCD(t2, tbl[i], t1);
       if (deg(t2) > 0) {
          AddFactor(factors, t2, d, verbose);
@@ -696 +696 @@
 
 
-void TraceMap(GF2EX& w, const GF2EX& a, long d, const GF2EXModulus& F, 
+void TraceMap(GF2EX& w, const GF2EX& a, long d, const GF2EXModulus& F,
               const GF2EX& b)
 
@@ -710 +710 @@
    while (d) {
       if (d == 1) {
-         if (IsZero(w)) 
+         if (IsZero(w))
             w = y;
          else {
@@ -817 +817 @@
 long GF2EX_BlockingFactor = 10;
 
-void DDF(vec_pair_GF2EX_long& factors, const GF2EX& ff, const GF2EX& hh, 
+void DDF(vec_pair_GF2EX_long& factors, const GF2EX& ff, const GF2EX& hh,
          long verbose)
 {
@@ -836 +836 @@
    }
 
-   long CompTableSize = 2*SqrRoot(deg(f)); 
+   long CompTableSize = 2*SqrRoot(deg(f));
 
    long GCDTableSize = GF2EX_BlockingFactor;
@@ -876 +876 @@
 
          if (deg(f) < old_n) {
-            // f has changed 
+            // f has changed
 
             build(F, f);
@@ -916 +916 @@
    GF2EXModulus F;
    vec_GF2E roots;
-   
+
    build(F, f);
    long n = F.n;
@@ -947 +947 @@
    }
 }
-         
+
 
 void EDF(vec_GF2EX& factors, const GF2EX& ff, const GF2EX& bb,
@@ -978 +978 @@
    }
 
-   
+
    factors.SetLength(0);
 
@@ -1008 +1008 @@
    double t;
 
-   
+
    GF2EXModulus F;
    build(F, f);
@@ -1050 +1050 @@
    }
 }
-   
+
 void CanZass(vec_pair_GF2EX_long& factors, const GF2EX& f, long verbose)
 {
@@ -1060 +1060 @@
    vec_GF2EX x;
 
-   
+
    SquareFreeDecomp(sfd, f);
 
@@ -1121 +1121 @@
 
 static
-void TandemPowerCompose(GF2EX& y1, GF2EX& y2, const GF2EX& h, 
+void TandemPowerCompose(GF2EX& y1, GF2EX& y2, const GF2EX& h,
                         long q1, long q2, const GF2EXModulus& F)
 {
@@ -1201 +1201 @@
    long q1, q2, r1, r2;
 
-   q1 = fvec[fvec[u].link].val; 
+   q1 = fvec[fvec[u].link].val;
    q2 = fvec[fvec[u].link+1].val;
 
@@ -1210 +1210 @@
 }
 
-   
+
 
 
@@ -1218 +1218 @@
    // the common degree of the irreducible factors of f is computed
 {
-   if (F.n == 1 || IsX(h)) 
+   if (F.n == 1 || IsX(h))
       return 1;
 
@@ -1239 +1239 @@
 
    f = ff;
-   
+
    if (!IsOne(LeadCoeff(f)))
       Error("FindRoot: bad args");
@@ -1261 +1261 @@
       }
    }
- 
+
    root = ConstTerm(f);
 }
@@ -1308 +1308 @@
 
 
-   q1 = fvec[fvec[u].link].val; 
+   q1 = fvec[fvec[u].link].val;
    q2 = fvec[fvec[u].link+1].val;
 
    TandemPowerCompose(h1, h2, h, q1, q2, F);
-   return RecIrredTest(fvec[u].link, h2, F, fvec) 
+   return RecIrredTest(fvec[u].link, h2, F, fvec)
           && RecIrredTest(fvec[u].link+1, h1, F, fvec);
 }
@@ -1324 +1324 @@
 
    build(F, f);
-   
+
    GF2EX h;
 
@@ -1350 +1350 @@
 
    build(F, f);
-   
+
    GF2EX h;
 
@@ -1672 +1672 @@
    long i;
 
-   long HexOutput = GF2X::HexOutput; 
+   long HexOutput = GF2X::HexOutput;
    GF2X::HexOutput = 1;
 
@@ -1708 +1708 @@
 }
 
-   
+
 
 
@@ -1778 +1778 @@
    }
 }
-      
+
 
 
@@ -1838 +1838 @@
 
          long i;
-         for (i = 1; i <= k-1; i++) 
+         for (i = 1; i <= k-1; i++)
             rem(BabyStep[i], BabyStep[i], F);
       }
@@ -1847 +1847 @@
    }
 
-   if (deg(f) > 0) 
+   if (deg(f) > 0)
       NewAddFactor(u, f, 0, verbose);
 
@@ -1902 +1902 @@
    NewProcessTable(factors, f, F, buf, size, first_d, 1, verbose);
 
-   if (deg(f) > 0) 
+   if (deg(f) > 0)
       NewAddFactor(factors, f, deg(f), verbose);
 }
-   
+
 
 
@@ -1935 +1935 @@
 }
 
-      
-      
-
-      
+
+
+
+
 
 void NewDDF(vec_pair_GF2EX_long& factors,
@@ -1962 +1962 @@
    if (!GF2EX_stem[0])
       sprintf(GF2EX_stem, "ddf-%ld", RandomBnd(10000));
-      
+
    long B = deg(f)/2;
    long k = SqrRoot(B);

ntl/src/GF2X.c

@@ -55 +55 @@
 }
 
-long IsZero(const GF2X& a) 
+long IsZero(const GF2X& a)
    { return a.xrep.length() == 0; }
 
@@ -133 +133 @@
    x.xrep[wi] |= (1UL << bi);
 }
-   
+
 
 
@@ -157 +157 @@
    long wi = i/NTL_BITS_PER_LONG;
 
-   if (wi >= n) 
+   if (wi >= n)
       return;
 
@@ -204 +204 @@
    return NTL_BITS_PER_LONG*(n-1) + i - 1;
 }
-   
+
 
 long operator==(const GF2X& a, const GF2X& b)
@@ -213 +213 @@
 long operator==(const GF2X& a, long b)
 {
-   if (b & 1) 
+   if (b & 1)
       return IsOne(a);
    else
@@ -221 +221 @@
 long operator==(const GF2X& a, GF2 b)
 {
-   if (b == 1) 
+   if (b == 1)
       return IsOne(a);
    else
@@ -274 +274 @@
       x.xrep.QuickSetLength(i+1);
    }
-   
+
    else if (sa < sb) {
       x.xrep.SetLength(sb);
@@ -342 +342 @@
 
 
-static 
+static
 void mul1(_ntl_ulong *c, _ntl_ulong a, _ntl_ulong b)
 {
@@ -368 +368 @@
 }
 
-#define mul1_IL mul1_inline 
+#define mul1_IL mul1_inline
 #endif
 
 
-static 
+static
 void Mul1(_ntl_ulong *cp, const _ntl_ulong *bp, long sb, _ntl_ulong a)
 {
- 
+
 
 NTL_EFF_BB_MUL_CODE1
@@ -382 +382 @@
 }
 
-static 
+static
 void AddMul1(_ntl_ulong *cp, const _ntl_ulong* bp, long sb, _ntl_ulong a)
 {
@@ -393 +393 @@
 
 
-static 
+static
 void Mul1_short(_ntl_ulong *cp, const _ntl_ulong *bp, long sb, _ntl_ulong a)
 {
- 
+
 
 NTL_EFF_SHORT_BB_MUL_CODE1
@@ -407 +407 @@
 
 
-static 
+static
 void mul_half(_ntl_ulong *c, _ntl_ulong a, _ntl_ulong b)
 {
@@ -445 +445 @@
 
 /*
- * This version of mul3 I got from Weimerskirch, Stebila, 
+ * This version of mul3 I got from Weimerskirch, Stebila,
  * and Shantz, "Generic GF(2^m) arithmetic in software
  * an its application to ECC" (ACISP 2003).
@@ -462 +462 @@
    mul1_IL(d12, a[1]^a[2], b[1]^b[2]);
 
-   
+
    c[0] = d0[0];
    c[1] = d0[1] ^ d01[0] ^ d1[0] ^ d0[0];
@@ -484 +484 @@
 
    mul2(c, a, b);
-   mul2(c+4, a+2, b+2); 
+   mul2(c+4, a+2, b+2);
    mul2(hl2, hs0, hs1);
 
@@ -491 +491 @@
    hl2[2] = hl2[2] ^ c[2] ^ c[6];
    hl2[3] = hl2[3] ^ c[3] ^ c[7];
-   
+
    c[2] ^= hl2[0];
    c[3] ^= hl2[1];
@@ -504 +504 @@
    _ntl_ulong hl2[6];
 
-   hs0[0] = a[0] ^ a[3]; 
+   hs0[0] = a[0] ^ a[3];
    hs0[1] = a[1] ^ a[4];
    hs0[2] = a[2];
-   hs1[0] = b[0] ^ b[3]; 
+   hs1[0] = b[0] ^ b[3];
    hs1[1] = b[1] ^ b[4];
    hs1[2] = b[2];
 
-   mul3(c, a, b); 
+   mul3(c, a, b);
    mul3(hl2, hs0, hs1);
    mul2(c+6, a+3, b+3);
 
-   hl2[0] = hl2[0] ^ c[0] ^ c[6]; 
+   hl2[0] = hl2[0] ^ c[0] ^ c[6];
    hl2[1] = hl2[1] ^ c[1] ^ c[7];
    hl2[2] = hl2[2] ^ c[2] ^ c[8];
@@ -522 +522 @@
    hl2[5] = hl2[5] ^ c[5];
 
-  
+
    c[3] ^= hl2[0];
    c[4] ^= hl2[1];
@@ -537 +537 @@
    _ntl_ulong hl2[6];
 
-   hs0[0] = a[0] ^ a[3];   
+   hs0[0] = a[0] ^ a[3];
    hs0[1] = a[1] ^ a[4];
    hs0[2] = a[2] ^ a[5];
-   hs1[0] = b[0] ^ b[3];   
+   hs1[0] = b[0] ^ b[3];
    hs1[1] = b[1] ^ b[4];
    hs1[2] = b[2] ^ b[5];
 
-   mul3(c, a, b);   
-   mul3(c+6, a+3, b+3); 
-   mul3(hl2, hs0, hs1);  
+   mul3(c, a, b);
+   mul3(c+6, a+3, b+3);
+   mul3(hl2, hs0, hs1);
 
    hl2[0] = hl2[0] ^ c[0] ^ c[6];
@@ -554 +554 @@
    hl2[4] = hl2[4] ^ c[4] ^ c[10];
    hl2[5] = hl2[5] ^ c[5] ^ c[11];
-   
+
    c[3] ^= hl2[0];
    c[4] ^= hl2[1];
@@ -569 +569 @@
    _ntl_ulong hl2[8];
 
-   hs0[0] = a[0] ^ a[4]; 
+   hs0[0] = a[0] ^ a[4];
    hs0[1] = a[1] ^ a[5];
    hs0[2] = a[2] ^ a[6];
    hs0[3] = a[3];
-   hs1[0] = b[0] ^ b[4]; 
+   hs1[0] = b[0] ^ b[4];
    hs1[1] = b[1] ^ b[5];
    hs1[2] = b[2] ^ b[6];
    hs1[3] = b[3];
 
-   mul4(c, a, b); 
+   mul4(c, a, b);
    mul4(hl2, hs0, hs1);
-   mul3(c+8, a+4, b+4); 
+   mul3(c+8, a+4, b+4);
 
    hl2[0] = hl2[0] ^ c[0] ^ c[8];
@@ -590 +590 @@
    hl2[6] = hl2[6] ^ c[6];
    hl2[7] = hl2[7] ^ c[7];
-   
+
    c[4]  ^= hl2[0];
    c[5]  ^= hl2[1];
@@ -607 +607 @@
    _ntl_ulong hl2[8];
 
-   hs0[0] = a[0] ^ a[4]; 
+   hs0[0] = a[0] ^ a[4];
    hs0[1] = a[1] ^ a[5];
    hs0[2] = a[2] ^ a[6];
    hs0[3] = a[3] ^ a[7];
-   hs1[0] = b[0] ^ b[4]; 
+   hs1[0] = b[0] ^ b[4];
    hs1[1] = b[1] ^ b[5];
    hs1[2] = b[2] ^ b[6];
    hs1[3] = b[3] ^ b[7];
 
-   mul4(c, a, b); 
+   mul4(c, a, b);
    mul4(c+8, a+4, b+4);
-   mul4(hl2, hs0, hs1); 
+   mul4(hl2, hs0, hs1);
 
    hl2[0] = hl2[0] ^ c[0] ^ c[8];
@@ -628 +628 @@
    hl2[6] = hl2[6] ^ c[6] ^ c[14];
    hl2[7] = hl2[7] ^ c[7] ^ c[15];
-   
+
    c[4]  ^= hl2[0];
    c[5]  ^= hl2[1];
@@ -640 +640 @@
 
 static
-void KarMul(_ntl_ulong *c, const _ntl_ulong *a, const _ntl_ulong *b, 
+void KarMul(_ntl_ulong *c, const _ntl_ulong *a, const _ntl_ulong *b,
             long len, _ntl_ulong *stk)
 {
@@ -717 +717 @@
       return;
    }
- 
+
    _ntl_ulong a0 = a.xrep[0];
    _ntl_ulong b0 = b.xrep[0];
@@ -868 +868 @@
       return;
    }
- 
+
    _ntl_ulong a0 = a.xrep[0];
    _ntl_ulong b0 = b.xrep[0];
@@ -1057 +1057 @@
             }
          }
-         return; 
+         return;
 
          case 7: {
@@ -1098 +1098 @@
             }
          }
-         return; 
+         return;
 
          case 8: {
@@ -1143 +1143 @@
             }
          }
-         return; 
+         return;
 
       }
@@ -1183 +1183 @@
    // finally: the general case
 
-   
+
    static WordVector mem;
    static WordVector stk;
@@ -1244 +1244 @@
       if (sa == 1) {
          AddMul1(cp, bp, sb, ap[0]);
-         
+
          break;
       }
@@ -1253 +1253 @@
          KarMul(v, ap, bp + i, sa, stk_p);
          for (j = 0; j < 2*sa; j++)
-            cp[i+j] ^= v[j]; 
+            cp[i+j] ^= v[j];
       }
 
@@ -1314 +1314 @@
       }
    }
-   else if (n*NTL_BITS_PER_LONG <= m) 
+   else if (n*NTL_BITS_PER_LONG <= m)
       x = a;
    else {
@@ -1334 +1334 @@
    }
 }
-      
+
 
 /****** implementation of vec_GF2X ******/
@@ -1376 +1376 @@
 static _ntl_ulong sqrtab[256] = {
 
-0UL, 1UL, 4UL, 5UL, 16UL, 17UL, 20UL, 21UL, 64UL, 
-65UL, 68UL, 69UL, 80UL, 81UL, 84UL, 85UL, 256UL, 
-257UL, 260UL, 261UL, 272UL, 273UL, 276UL, 277UL, 320UL, 
-321UL, 324UL, 325UL, 336UL, 337UL, 340UL, 341UL, 1024UL, 
-1025UL, 1028UL, 1029UL, 1040UL, 1041UL, 1044UL, 1045UL, 1088UL, 
-1089UL, 1092UL, 1093UL, 1104UL, 1105UL, 1108UL, 1109UL, 1280UL, 
-1281UL, 1284UL, 1285UL, 1296UL, 1297UL, 1300UL, 1301UL, 1344UL, 
-1345UL, 1348UL, 1349UL, 1360UL, 1361UL, 1364UL, 1365UL, 4096UL, 
-4097UL, 4100UL, 4101UL, 4112UL, 4113UL, 4116UL, 4117UL, 4160UL, 
-4161UL, 4164UL, 4165UL, 4176UL, 4177UL, 4180UL, 4181UL, 4352UL, 
-4353UL, 4356UL, 4357UL, 4368UL, 4369UL, 4372UL, 4373UL, 4416UL, 
-4417UL, 4420UL, 4421UL, 4432UL, 4433UL, 4436UL, 4437UL, 5120UL, 
-5121UL, 5124UL, 5125UL, 5136UL, 5137UL, 5140UL, 5141UL, 5184UL, 
-5185UL, 5188UL, 5189UL, 5200UL, 5201UL, 5204UL, 5205UL, 5376UL, 
-5377UL, 5380UL, 5381UL, 5392UL, 5393UL, 5396UL, 5397UL, 5440UL, 
-5441UL, 5444UL, 5445UL, 5456UL, 5457UL, 5460UL, 5461UL, 16384UL, 
-16385UL, 16388UL, 16389UL, 16400UL, 16401UL, 16404UL, 16405UL, 16448UL, 
-16449UL, 16452UL, 16453UL, 16464UL, 16465UL, 16468UL, 16469UL, 16640UL, 
-16641UL, 16644UL, 16645UL, 16656UL, 16657UL, 16660UL, 16661UL, 16704UL, 
-16705UL, 16708UL, 16709UL, 16720UL, 16721UL, 16724UL, 16725UL, 17408UL, 
-17409UL, 17412UL, 17413UL, 17424UL, 17425UL, 17428UL, 17429UL, 17472UL, 
-17473UL, 17476UL, 17477UL, 17488UL, 17489UL, 17492UL, 17493UL, 17664UL, 
-17665UL, 17668UL, 17669UL, 17680UL, 17681UL, 17684UL, 17685UL, 17728UL, 
-17729UL, 17732UL, 17733UL, 17744UL, 17745UL, 17748UL, 17749UL, 20480UL, 
-20481UL, 20484UL, 20485UL, 20496UL, 20497UL, 20500UL, 20501UL, 20544UL, 
-20545UL, 20548UL, 20549UL, 20560UL, 20561UL, 20564UL, 20565UL, 20736UL, 
-20737UL, 20740UL, 20741UL, 20752UL, 20753UL, 20756UL, 20757UL, 20800UL, 
-20801UL, 20804UL, 20805UL, 20816UL, 20817UL, 20820UL, 20821UL, 21504UL, 
-21505UL, 21508UL, 21509UL, 21520UL, 21521UL, 21524UL, 21525UL, 21568UL, 
-21569UL, 21572UL, 21573UL, 21584UL, 21585UL, 21588UL, 21589UL, 21760UL, 
-21761UL, 21764UL, 21765UL, 21776UL, 21777UL, 21780UL, 21781UL, 21824UL, 
+0UL, 1UL, 4UL, 5UL, 16UL, 17UL, 20UL, 21UL, 64UL,
+65UL, 68UL, 69UL, 80UL, 81UL, 84UL, 85UL, 256UL,
+257UL, 260UL, 261UL, 272UL, 273UL, 276UL, 277UL, 320UL,
+321UL, 324UL, 325UL, 336UL, 337UL, 340UL, 341UL, 1024UL,
+1025UL, 1028UL, 1029UL, 1040UL, 1041UL, 1044UL, 1045UL, 1088UL,
+1089UL, 1092UL, 1093UL, 1104UL, 1105UL, 1108UL, 1109UL, 1280UL,
+1281UL, 1284UL, 1285UL, 1296UL, 1297UL, 1300UL, 1301UL, 1344UL,
+1345UL, 1348UL, 1349UL, 1360UL, 1361UL, 1364UL, 1365UL, 4096UL,
+4097UL, 4100UL, 4101UL, 4112UL, 4113UL, 4116UL, 4117UL, 4160UL,
+4161UL, 4164UL, 4165UL, 4176UL, 4177UL, 4180UL, 4181UL, 4352UL,
+4353UL, 4356UL, 4357UL, 4368UL, 4369UL, 4372UL, 4373UL, 4416UL,
+4417UL, 4420UL, 4421UL, 4432UL, 4433UL, 4436UL, 4437UL, 5120UL,
+5121UL, 5124UL, 5125UL, 5136UL, 5137UL, 5140UL, 5141UL, 5184UL,
+5185UL, 5188UL, 5189UL, 5200UL, 5201UL, 5204UL, 5205UL, 5376UL,
+5377UL, 5380UL, 5381UL, 5392UL, 5393UL, 5396UL, 5397UL, 5440UL,
+5441UL, 5444UL, 5445UL, 5456UL, 5457UL, 5460UL, 5461UL, 16384UL,
+16385UL, 16388UL, 16389UL, 16400UL, 16401UL, 16404UL, 16405UL, 16448UL,
+16449UL, 16452UL, 16453UL, 16464UL, 16465UL, 16468UL, 16469UL, 16640UL,
+16641UL, 16644UL, 16645UL, 16656UL, 16657UL, 16660UL, 16661UL, 16704UL,
+16705UL, 16708UL, 16709UL, 16720UL, 16721UL, 16724UL, 16725UL, 17408UL,
+17409UL, 17412UL, 17413UL, 17424UL, 17425UL, 17428UL, 17429UL, 17472UL,
+17473UL, 17476UL, 17477UL, 17488UL, 17489UL, 17492UL, 17493UL, 17664UL,
+17665UL, 17668UL, 17669UL, 17680UL, 17681UL, 17684UL, 17685UL, 17728UL,
+17729UL, 17732UL, 17733UL, 17744UL, 17745UL, 17748UL, 17749UL, 20480UL,
+20481UL, 20484UL, 20485UL, 20496UL, 20497UL, 20500UL, 20501UL, 20544UL,
+20545UL, 20548UL, 20549UL, 20560UL, 20561UL, 20564UL, 20565UL, 20736UL,
+20737UL, 20740UL, 20741UL, 20752UL, 20753UL, 20756UL, 20757UL, 20800UL,
+20801UL, 20804UL, 20805UL, 20816UL, 20817UL, 20820UL, 20821UL, 21504UL,
+21505UL, 21508UL, 21509UL, 21520UL, 21521UL, 21524UL, 21525UL, 21568UL,
+21569UL, 21572UL, 21573UL, 21584UL, 21585UL, 21588UL, 21589UL, 21760UL,
+21761UL, 21764UL, 21765UL, 21776UL, 21777UL, 21780UL, 21781UL, 21824UL,
 21825UL, 21828UL, 21829UL, 21840UL, 21841UL, 21844UL, 21845UL };
 
@@ -1412 +1412 @@
 
 
-static inline 
+static inline
 void sqr1(_ntl_ulong *c, _ntl_ulong a)
 {
@@ -1461 +1461 @@
 
    if (n < 0) {
-      if (n < -NTL_MAX_LONG) 
+      if (n < -NTL_MAX_LONG)
          clear(c);
       else
@@ -1535 +1535 @@
    if (bn) ss++;
 
-   if (ss > sc) 
+   if (ss > sc)
       c.xrep.SetLength(ss);
 
@@ -1614 +1614 @@
 static _ntl_ulong revtab[256] = {
 
-0UL, 128UL, 64UL, 192UL, 32UL, 160UL, 96UL, 224UL, 16UL, 144UL, 
-80UL, 208UL, 48UL, 176UL, 112UL, 240UL, 8UL, 136UL, 72UL, 200UL, 
-40UL, 168UL, 104UL, 232UL, 24UL, 152UL, 88UL, 216UL, 56UL, 184UL, 
-120UL, 248UL, 4UL, 132UL, 68UL, 196UL, 36UL, 164UL, 100UL, 228UL, 
-20UL, 148UL, 84UL, 212UL, 52UL, 180UL, 116UL, 244UL, 12UL, 140UL, 
-76UL, 204UL, 44UL, 172UL, 108UL, 236UL, 28UL, 156UL, 92UL, 220UL, 
-60UL, 188UL, 124UL, 252UL, 2UL, 130UL, 66UL, 194UL, 34UL, 162UL, 
-98UL, 226UL, 18UL, 146UL, 82UL, 210UL, 50UL, 178UL, 114UL, 242UL, 
-10UL, 138UL, 74UL, 202UL, 42UL, 170UL, 106UL, 234UL, 26UL, 154UL, 
-90UL, 218UL, 58UL, 186UL, 122UL, 250UL, 6UL, 134UL, 70UL, 198UL, 
-38UL, 166UL, 102UL, 230UL, 22UL, 150UL, 86UL, 214UL, 54UL, 182UL, 
-118UL, 246UL, 14UL, 142UL, 78UL, 206UL, 46UL, 174UL, 110UL, 238UL, 
-30UL, 158UL, 94UL, 222UL, 62UL, 190UL, 126UL, 254UL, 1UL, 129UL, 
-65UL, 193UL, 33UL, 161UL, 97UL, 225UL, 17UL, 145UL, 81UL, 209UL, 
-49UL, 177UL, 113UL, 241UL, 9UL, 137UL, 73UL, 201UL, 41UL, 169UL, 
-105UL, 233UL, 25UL, 153UL, 89UL, 217UL, 57UL, 185UL, 121UL, 249UL, 
-5UL, 133UL, 69UL, 197UL, 37UL, 165UL, 101UL, 229UL, 21UL, 149UL, 
-85UL, 213UL, 53UL, 181UL, 117UL, 245UL, 13UL, 141UL, 77UL, 205UL, 
-45UL, 173UL, 109UL, 237UL, 29UL, 157UL, 93UL, 221UL, 61UL, 189UL, 
-125UL, 253UL, 3UL, 131UL, 67UL, 195UL, 35UL, 163UL, 99UL, 227UL, 
-19UL, 147UL, 83UL, 211UL, 51UL, 179UL, 115UL, 243UL, 11UL, 139UL, 
-75UL, 203UL, 43UL, 171UL, 107UL, 235UL, 27UL, 155UL, 91UL, 219UL, 
-59UL, 187UL, 123UL, 251UL, 7UL, 135UL, 71UL, 199UL, 39UL, 167UL, 
-103UL, 231UL, 23UL, 151UL, 87UL, 215UL, 55UL, 183UL, 119UL, 247UL, 
-15UL, 143UL, 79UL, 207UL, 47UL, 175UL, 111UL, 239UL, 31UL, 159UL, 
-95UL, 223UL, 63UL, 191UL, 127UL, 255UL  }; 
-
-static inline 
+0UL, 128UL, 64UL, 192UL, 32UL, 160UL, 96UL, 224UL, 16UL, 144UL,
+80UL, 208UL, 48UL, 176UL, 112UL, 240UL, 8UL, 136UL, 72UL, 200UL,
+40UL, 168UL, 104UL, 232UL, 24UL, 152UL, 88UL, 216UL, 56UL, 184UL,
+120UL, 248UL, 4UL, 132UL, 68UL, 196UL, 36UL, 164UL, 100UL, 228UL,
+20UL, 148UL, 84UL, 212UL, 52UL, 180UL, 116UL, 244UL, 12UL, 140UL,
+76UL, 204UL, 44UL, 172UL, 108UL, 236UL, 28UL, 156UL, 92UL, 220UL,
+60UL, 188UL, 124UL, 252UL, 2UL, 130UL, 66UL, 194UL, 34UL, 162UL,
+98UL, 226UL, 18UL, 146UL, 82UL, 210UL, 50UL, 178UL, 114UL, 242UL,
+10UL, 138UL, 74UL, 202UL, 42UL, 170UL, 106UL, 234UL, 26UL, 154UL,
+90UL, 218UL, 58UL, 186UL, 122UL, 250UL, 6UL, 134UL, 70UL, 198UL,
+38UL, 166UL, 102UL, 230UL, 22UL, 150UL, 86UL, 214UL, 54UL, 182UL,
+118UL, 246UL, 14UL, 142UL, 78UL, 206UL, 46UL, 174UL, 110UL, 238UL,
+30UL, 158UL, 94UL, 222UL, 62UL, 190UL, 126UL, 254UL, 1UL, 129UL,
+65UL, 193UL, 33UL, 161UL, 97UL, 225UL, 17UL, 145UL, 81UL, 209UL,
+49UL, 177UL, 113UL, 241UL, 9UL, 137UL, 73UL, 201UL, 41UL, 169UL,
+105UL, 233UL, 25UL, 153UL, 89UL, 217UL, 57UL, 185UL, 121UL, 249UL,
+5UL, 133UL, 69UL, 197UL, 37UL, 165UL, 101UL, 229UL, 21UL, 149UL,
+85UL, 213UL, 53UL, 181UL, 117UL, 245UL, 13UL, 141UL, 77UL, 205UL,
+45UL, 173UL, 109UL, 237UL, 29UL, 157UL, 93UL, 221UL, 61UL, 189UL,
+125UL, 253UL, 3UL, 131UL, 67UL, 195UL, 35UL, 163UL, 99UL, 227UL,
+19UL, 147UL, 83UL, 211UL, 51UL, 179UL, 115UL, 243UL, 11UL, 139UL,
+75UL, 203UL, 43UL, 171UL, 107UL, 235UL, 27UL, 155UL, 91UL, 219UL,
+59UL, 187UL, 123UL, 251UL, 7UL, 135UL, 71UL, 199UL, 39UL, 167UL,
+103UL, 231UL, 23UL, 151UL, 87UL, 215UL, 55UL, 183UL, 119UL, 247UL,
+15UL, 143UL, 79UL, 207UL, 47UL, 175UL, 111UL, 239UL, 31UL, 159UL,
+95UL, 223UL, 63UL, 191UL, 127UL, 255UL  };
+
+static inline
 _ntl_ulong rev1(_ntl_ulong a)
 {
@@ -1675 +1675 @@
 
    c.xrep.SetLength(wn);
-  
+
    _ntl_ulong *cp = c.xrep.elts();
    const _ntl_ulong *ap = a.xrep.elts();
@@ -1737 +1737 @@
    r = n - lw*BytesPerLong;
 
-   if (r != 0) 
+   if (r != 0)
       lw++;
    else

ntl/src/GF2X1.c

@@ -16 +16 @@
 #ifdef NTL_GF2X_LIB
 
-#define NTL_GF2X_GCD_CROSSOVER (400L*NTL_BITS_PER_LONG) 
+#define NTL_GF2X_GCD_CROSSOVER (400L*NTL_BITS_PER_LONG)
 #define NTL_GF2X_HalfGCD_CROSSOVER (6L*NTL_BITS_PER_LONG)
 #define NTL_GF2X_BERMASS_CROSSOVER (200L*NTL_BITS_PER_LONG)
@@ -22 +22 @@
 #else
 
-#define NTL_GF2X_GCD_CROSSOVER (900L*NTL_BITS_PER_LONG) 
+#define NTL_GF2X_GCD_CROSSOVER (900L*NTL_BITS_PER_LONG)
 #define NTL_GF2X_HalfGCD_CROSSOVER (6L*NTL_BITS_PER_LONG)
 #define NTL_GF2X_BERMASS_CROSSOVER (450L*NTL_BITS_PER_LONG)
@@ -46 +46 @@
 
 ~GF2XRegisterType()
-{ xrep->xrep.release();  
+{ xrep->xrep.release();
   GF2XRegisterTop--; }
 
@@ -102 +102 @@
 
    stab[posb] = b;
-   for (i = 1; i <= min(dq, NTL_BITS_PER_LONG-1); i++) 
-      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
+   for (i = 1; i <= min(dq, NTL_BITS_PER_LONG-1); i++)
+      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
              stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
 
@@ -206 +206 @@
 
    stab[posb] = b;
-   for (i = 1; i <= min(da-db, NTL_BITS_PER_LONG-1); i++) 
-      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
+   for (i = 1; i <= min(da-db, NTL_BITS_PER_LONG-1); i++)
+      MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
              stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
 
@@ -349 +349 @@
 
 
-static 
+static
 long weight1(_ntl_ulong a)
 {
@@ -392 +392 @@
 
    trunc(g, g, n);
-   
+
    long t = deg(g);
 
@@ -440 +440 @@
    long posb = n - NTL_BITS_PER_LONG*(sb-1);
 
-   F.posn = posb; 
+   F.posn = posb;
 
    if (F.posn > 0) {
@@ -467 +467 @@
    long deg_f0 = deg(f0);
 
-   if (F.sn > 1 && deg_f0 < NTL_BITS_PER_LONG 
+   if (F.sn > 1 && deg_f0 < NTL_BITS_PER_LONG
        && deg_f0 >= NTL_BITS_PER_LONG/2) {
       if (F.size >= 6)
@@ -482 +482 @@
    else if (F.size >= 8)
       F.method = GF2X_MOD_MUL;
-   else 
+   else
       F.method = GF2X_MOD_PLAIN;
-      
+
 
    if (F.method == GF2X_MOD_SPECIAL) {
@@ -505 +505 @@
 
          stab1[kk1<<1] = stab1[kk0<<1] << 1;
-         stab1[(kk1<<1)+1] = (stab1[(kk0<<1)+1] << 1) 
+         stab1[(kk1<<1)+1] = (stab1[(kk0<<1)+1] << 1)
                           | (stab1[kk0<<1] >> (NTL_BITS_PER_LONG-1));
 
-         if (kk1 < posb) 
+         if (kk1 < posb)
             stab_cnt[kk1] = -sb;
          else
@@ -526 +526 @@
       long *stab_cnt = F.stab_cnt;
       if (!stab_cnt) Error("out of memory");
-      
-   
+
+
       stab[posb] = f;
-      for (i = 1; i < NTL_BITS_PER_LONG; i++) 
-         MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG], 
+      for (i = 1; i < NTL_BITS_PER_LONG; i++)
+         MulByX(stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG],
                 stab[((_ntl_ulong)(posb+i-1))%NTL_BITS_PER_LONG]);
-   
-   
+
+
       for (i = 0; i < NTL_BITS_PER_LONG; i++) {
          WordVector& st = stab[((_ntl_ulong)(posb+i))%NTL_BITS_PER_LONG].xrep;
@@ -568 +568 @@
 GF2XModulus::GF2XModulus(const GF2XModulus& F) :
    f(F.f), n(F.n), sn(F.sn), posn(F.posn), k3(F.k3), k2(F.k2), k1(F.k1),
-   size(F.size), 
+   size(F.size),
    msk(F.msk), method(F.method), stab(F.stab), h0(F.h0), f0(F.f0),
    stab_cnt(0), stab_ptr(0), stab1(0), tracevec(F.tracevec)
@@ -596 +596 @@
          stab_ptr = NTL_NEW_OP _ntl_ulong_ptr[NTL_BITS_PER_LONG];
          if (!stab_ptr) Error("GF2XModulus: out of memory");
-      
+
          for (i = 0; i < NTL_BITS_PER_LONG; i++) {
             WordVector& st = stab[((_ntl_ulong)(posn+i))%NTL_BITS_PER_LONG].xrep;
@@ -611 +611 @@
    if (this == &F) return *this;
 
-   f=F.f; n=F.n; sn=F.sn; posn=F.posn; 
+   f=F.f; n=F.n; sn=F.sn; posn=F.posn;
    k3=F.k3; k2=F.k2; k1=F.k1;
-   size=F.size; 
+   size=F.size;
    msk=F.msk; method=F.method; stab=F.stab; h0=F.h0; f0 = F.f0;
    tracevec=F.tracevec;
@@ -641 +641 @@
          if (!stab_ptr) stab_ptr = NTL_NEW_OP _ntl_ulong_ptr[NTL_BITS_PER_LONG];
          if (!stab_ptr) Error("GF2XModulus: out of memory");
-      
+
          for (i = 0; i < NTL_BITS_PER_LONG; i++) {
             WordVector& st = stab[((_ntl_ulong)(posn+i))%NTL_BITS_PER_LONG].xrep;
@@ -653 +653 @@
    return *this;
 }
-   
-
-
-GF2XModulus::~GF2XModulus() 
-{ 
-   delete [] stab_ptr; 
-   delete [] stab_cnt; 
-   delete [] stab1; 
+
+
+
+GF2XModulus::~GF2XModulus()
+{
+   delete [] stab_ptr;
+   delete [] stab_cnt;
+   delete [] stab1;
 }
 
@@ -751 +751 @@
    r = buf;
 }
-   
+
 
 void UseMulDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, const GF2XModulus& F)
@@ -795 +795 @@
    GF2XRegister(qq);
    GF2XRegister(qbuf);
-   
+
    clear(buf);
    a = aa;
@@ -890 +890 @@
          p[0] ^= (w >> bn);
 
-         p[m] &= ((1UL<<bn)-1UL); 
+         p[m] &= ((1UL<<bn)-1UL);
       }
       else {
@@ -911 +911 @@
          if (m-wdiff-1 >= 0) p[m-wdiff-1] ^= (w << (NTL_BITS_PER_LONG-bdiff));
          p[0] ^= (w >> bn);
-         p[m] &= ((1UL<<bn)-1UL); 
+         p[m] &= ((1UL<<bn)-1UL);
       }
    }
@@ -960 +960 @@
       w = p[m];
 
-      if (bn == 0) 
+      if (bn == 0)
          p[m-wn] ^= w;
       else {
@@ -968 +968 @@
       }
 
-      if (bdiff1 == 0) 
+      if (bdiff1 == 0)
          p[m-wdiff1] ^= w;
       else {
@@ -976 +976 @@
       }
 
-      if (bdiff2 == 0) 
+      if (bdiff2 == 0)
          p[m-wdiff2] ^= w;
       else {
@@ -984 +984 @@
       }
 
-      if (bdiff3 == 0) 
+      if (bdiff3 == 0)
          p[m-wdiff3] ^= w;
       else {
@@ -997 +997 @@
    w = (p[m] >> bn) << bn;
 
-   p[0] ^= (w >> bn); 
+   p[0] ^= (w >> bn);
 
    if (bdiff1 == 0)
@@ -1023 +1023 @@
       p[m] &= ((1UL<<bn)-1UL);
 
-   
+
    if (bn == 0)
       wn--;
@@ -1092 +1092 @@
 
    RightShift(P1, a, n);
-   if (k != 1) 
+   if (k != 1)
       RightShiftAdd(P1, P1, n-k);
 
@@ -1098 +1098 @@
 }
 
-static 
+static
 void TriDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n, long k)
 {
@@ -1120 +1120 @@
 
    RightShift(P1, a, n);
-   
+
    RightShift(P2, P1, n-k3);
    RightShiftAdd(P2, P1, n-k2);
@@ -1132 +1132 @@
 }
 
-static 
-void PentDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n, 
+static
+void PentDivRem21(GF2X& q, GF2X& r, const GF2X& a, long n,
                   long k3, long k2, long k1)
 {
@@ -1185 +1185 @@
    GF2XRegister(qq);
    GF2XRegister(qbuf);
-   
+
    clear(buf);
    a = aa;
@@ -1211 +1211 @@
 
 static
-void PentDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, long n, 
+void PentDivRemX1(GF2X& q, GF2X& r, const GF2X& aa, long n,
                   long k3, long k2, long k1)
 {
@@ -1254 +1254 @@
    GF2XRegister(qq);
    GF2XRegister(qbuf);
-   
+
    clear(buf);
    a = aa;
@@ -1304 +1304 @@
    }
    else if (F.method == GF2X_MOD_MUL) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          UseMulRem21(r, a, F);
       else
@@ -1312 +1312 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
+
       _ntl_ulong *ap;
       if (&r == &a)
@@ -1320 +1320 @@
          ap = GF2X_rembuf.elts();
       }
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
-   
+
       long i;
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1343 +1343 @@
          }
       }
-   
+
       long sn = F.size;
       r.xrep.SetLength(sn);
@@ -1357 +1357 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
-   
+
+
       _ntl_ulong *ap;
       if (&r == &a)
@@ -1366 +1366 @@
          ap = GF2X_rembuf.elts();
       }
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
-   
+
       long i;
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1378 +1378 @@
                atop[i] ^= stab_top[i];
          }
-   
+
          da--;
          if (da < n) break;
@@ -1388 +1388 @@
          }
       }
-   
+
       long sn = F.size;
       r.xrep.SetLength(sn);
@@ -1414 +1414 @@
    }
    else if (F.method == GF2X_MOD_TRI) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          TriDivRem21(q, r, a, F.n, F.k3);
       else
@@ -1420 +1420 @@
    }
    else if (F.method == GF2X_MOD_PENT) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          PentDivRem21(q, r, a, F.n, F.k3, F.k2, F.k1);
       else
@@ -1426 +1426 @@
    }
    else if (F.method == GF2X_MOD_MUL) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          UseMulDivRem21(q, r, a, F);
       else
@@ -1434 +1434 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
+
       long dq = da - n;
       long sq = dq/NTL_BITS_PER_LONG + 1;
       long posq = dq - NTL_BITS_PER_LONG*(sq-1);
-   
+
       _ntl_ulong *ap;
       if (&r == &a)
@@ -1446 +1446 @@
          ap = GF2X_rembuf.elts();
       }
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
@@ -1459 +1459 @@
       _ntl_ulong *qtop = &qp[sq-1];
 
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1468 +1468 @@
             atop[i+1] ^= stab_top[1];
          }
-   
+
          da--;
          if (da < n) break;
@@ -1484 +1484 @@
          }
       }
-   
+
       long sn = F.size;
       r.xrep.SetLength(sn);
@@ -1498 +1498 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
+
       long dq = da - n;
       long sq = dq/NTL_BITS_PER_LONG + 1;
       long posq = dq - NTL_BITS_PER_LONG*(sq-1);
-   
+
       _ntl_ulong *ap;
       if (&r == &a)
@@ -1510 +1510 @@
          ap = GF2X_rembuf.elts();
       }
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
-   
+
       long i;
 
@@ -1522 +1522 @@
 
       _ntl_ulong *qtop = &qp[sq-1];
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1530 +1530 @@
                atop[i] ^= stab_top[i];
          }
-   
+
          da--;
          if (da < n) break;
@@ -1546 +1546 @@
          }
       }
-   
+
       long sn = F.size;
       r.xrep.SetLength(sn);
@@ -1574 +1574 @@
    }
    else if (F.method == GF2X_MOD_TRI) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          TriDiv21(q, a, F.n, F.k3);
       else
@@ -1580 +1580 @@
    }
    else if (F.method == GF2X_MOD_PENT) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          PentDiv21(q, a, F.n, F.k3, F.k2, F.k1);
       else
@@ -1586 +1586 @@
    }
    else if (F.method == GF2X_MOD_MUL) {
-      if (da <= 2*(n-1)) 
+      if (da <= 2*(n-1))
          UseMulDiv21(q, a, F);
       else
@@ -1594 +1594 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
+
       long dq = da - n;
       long sq = dq/NTL_BITS_PER_LONG + 1;
       long posq = dq - NTL_BITS_PER_LONG*(sq-1);
-   
+
       _ntl_ulong *ap;
       GF2X_rembuf = a.xrep;
       ap = GF2X_rembuf.elts();
 
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
@@ -1615 +1615 @@
 
       _ntl_ulong *qtop = &qp[sq-1];
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1624 +1624 @@
             atop[i+1] ^= stab_top[1];
          }
-   
+
          da--;
          if (da < n) break;
@@ -1644 +1644 @@
       long sa = a.xrep.length();
       long posa = da - NTL_BITS_PER_LONG*(sa-1);
-   
+
       long dq = da - n;
       long sq = dq/NTL_BITS_PER_LONG + 1;
       long posq = dq - NTL_BITS_PER_LONG*(sq-1);
-   
+
       _ntl_ulong *ap;
       GF2X_rembuf = a.xrep;
       ap = GF2X_rembuf.elts();
-   
+
       _ntl_ulong *atop = &ap[sa-1];
       _ntl_ulong *stab_top;
-   
+
       long i;
 
@@ -1664 +1664 @@
 
       _ntl_ulong *qtop = &qp[sq-1];
-   
+
       while (1) {
          if (atop[0] & (1UL << posa)) {
@@ -1672 +1672 @@
                atop[i] ^= stab_top[i];
          }
-   
+
          da--;
          if (da < n) break;
@@ -1754 +1754 @@
    return k;
 }
-      
+
 
 
@@ -1821 +1821 @@
 
    v[0] = g;
- 
+
    if (k > 1) {
       GF2X t;
@@ -1837 +1837 @@
    val = 0;
    for (i = n-1; i >= 0; i--) {
-      val = (val << 1) | bit(e, i); 
+      val = (val << 1) | bit(e, i);
       if (val == 0)
          SqrMod(res, res, F);
@@ -1869 +1869 @@
 }
 
-   
+
 
 
@@ -1904 +1904 @@
 
 
-      
+
 
 
@@ -1924 +1924 @@
    mul(P1, P2, b);
    add(P1, P1, a);
-   
+
    r = P1;
 }
@@ -1945 +1945 @@
    mul(P1, P2, b);
    add(P1, P1, a);
-   
+
    r = P1;
    q = P2;
@@ -1965 +1965 @@
    mul(P2, P1, P2);
    RightShift(P2, P2, da-db);
-   
+
    q = P2;
 }
 
 
-const long GF2X_DIV_CROSS = 100; 
+const long GF2X_DIV_CROSS = 100;
 
 void DivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2X& b)
@@ -2021 +2021 @@
 
 
-static inline 
-void swap(_ntl_ulong_ptr& a, _ntl_ulong_ptr& b)  
+static inline
+void swap(_ntl_ulong_ptr& a, _ntl_ulong_ptr& b)
 {  _ntl_ulong_ptr t;  t = a; a = b; b = t; }
 
@@ -2033 +2033 @@
    GF2XRegister(a);
    GF2XRegister(b);
-   
+
    if (IsZero(a_in)) {
       d = b_in;
@@ -2043 +2043 @@
       return;
    }
-      
+
    a.xrep.SetMaxLength(a_in.xrep.length()+1);
    b.xrep.SetMaxLength(b_in.xrep.length()+1);
@@ -2240 +2240 @@
       return;
    }
-      
+
    a.xrep.SetMaxLength(a_in.xrep.length()+1);
    b.xrep.SetMaxLength(b_in.xrep.length()+1);
@@ -2348 +2348 @@
       BaseXGCD(d, s1, t1, b, r);
 
-      
+
       mul(r, t1, q);
       add(r, r, s1);  // r = s1 - t1*q, but sign doesn't matter
 
       s = t1;
-      t = r;   
+      t = r;
    }
    else if (sa >= 10 && 2*sb > 3*sa) {
@@ -2365 +2365 @@
       BaseXGCD(d, s1, t1, a, r);
 
-      
+
       mul(r, t1, q);
       add(r, r, s1);  // r = s1 - t1*q, but sign doesn't matter
 
       t = t1;
-      s = r;  
+      s = r;
    }
    else {
@@ -2389 +2389 @@
    long sf = f.xrep.length();
 
-   if ((sa >= 10 && 2*sf > 3*sa) || 
+   if ((sa >= 10 && 2*sf > 3*sa) ||
        sf > NTL_GF2X_GCD_CROSSOVER/NTL_BITS_PER_LONG) {
       GF2XRegister(t);
@@ -2404 +2404 @@
 
 void InvMod(GF2X& c, const GF2X& a, const GF2X& f)
-{ 
+{
    GF2XRegister(d);
    GF2XRegister(s);
@@ -2417 +2417 @@
 
 long InvModStatus(GF2X& c, const GF2X& a, const GF2X& f)
-{ 
+{
    GF2XRegister(d);
    GF2XRegister(s);
@@ -2433 +2433 @@
 
 
-   
+
 void diff(GF2X& c, const GF2X& a)
 {
    RightShift(c, a, 1);
-   
+
    // clear odd coeffs
 
@@ -2475 +2475 @@
 void VectorCopy(vec_GF2& x, const GF2X& a, long n)
 {
-   if (n < 0) Error("VectorCopy: negative length"); 
+   if (n < 0) Error("VectorCopy: negative length");
 
    if (NTL_OVERFLOW(n, 1, 0))
@@ -2511 +2511 @@
    if (b & 1) {
       long n = c.xrep.length();
-      if (n == 0) 
+      if (n == 0)
          set(c);
       else {
@@ -2577 +2577 @@
 
 
-void InnerProduct(GF2X& x, const GF2X& v, long dv, long low, long high, 
+void InnerProduct(GF2X& x, const GF2X& v, long dv, long low, long high,
                    const vec_GF2X& H, long n, WordVector& t)
 {
@@ -2591 +2591 @@
    long b_low = low - w_low*NTL_BITS_PER_LONG;
 
-   
+
    const _ntl_ulong *vp = &v.xrep[w_low];
    _ntl_ulong msk = 1UL << b_low;
@@ -2660 +2660 @@
    set(A.H[0]);
    A.H[1] = h;
-   for (i = 2; i <= m; i++) 
+   for (i = 2; i <= m; i++)
       MulMod(A.H[i], A.H[i-1], h, F);
 }
@@ -2710 +2710 @@
 }
 
-void Comp3Mod(GF2X& x1, GF2X& x2, GF2X& x3, 
+void Comp3Mod(GF2X& x1, GF2X& x2, GF2X& x3,
               const GF2X& g1, const GF2X& g2, const GF2X& g3,
               const GF2X& h, const GF2XModulus& F)
@@ -2760 +2760 @@
       B.shamt_fbi = 0;
    else
-      B.shamt_fbi = F.n-2 - d; 
+      B.shamt_fbi = F.n-2 - d;
 
    CopyReverse(B.fbi, t, d);
 
    if (F.method != GF2X_MOD_TRI && F.method != GF2X_MOD_PENT) {
-   
-      // The following code optimizes the case when 
+
+      // The following code optimizes the case when
       // f = X^n + low degree poly
-   
+
       trunc(t, F.f, F.n);
       d = deg(t);
@@ -2836 +2836 @@
    conv(x, xx);
 }
-   
+
 
 void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2XArgument& H,
@@ -2843 +2843 @@
    long n = F.n;
 
-   if (deg(a) >= n || k < 0 || NTL_OVERFLOW(k, 1, 0)) 
+   if (deg(a) >= n || k < 0 || NTL_OVERFLOW(k, 1, 0))
       Error("ProjectPowers: bad args");
 
@@ -2870 +2870 @@
 
 
-void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k, 
+void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k,
                    const GF2XArgument& H, const GF2XModulus& F)
 {
@@ -2879 +2879 @@
 
 
-void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2X& h, 
+void ProjectPowers(GF2X& x, const GF2X& a, long k, const GF2X& h,
                    const GF2XModulus& F)
 {
@@ -2920 +2920 @@
 
    CopyReverse(b_in, x, 2*m-1);
-      
+
    a.xrep.SetMaxLength(a_in.xrep.length()+1);
    b.xrep.SetMaxLength(b_in.xrep.length()+1);
@@ -2977 +2977 @@
       long t = ss + (da-db+NTL_BITS_PER_LONG-1)/NTL_BITS_PER_LONG;
       if (t > sr) {
-         while (t > 0 && rp[t-1] == 0) t--; 
+         while (t > 0 && rp[t-1] == 0) t--;
          sr = t;
       }
@@ -3012 +3012 @@
 
 
-void DoMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m, 
+void DoMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m,
                const GF2X& R)
 {
@@ -3066 +3066 @@
    GF2X R;
    GF2XTransMultiplier H1;
-   
+
 
    for (;;) {
@@ -3112 +3112 @@
    long da = deg(a);
    long df = deg(F);
-   if (da >= df) Error("MulByXMod: bad args"); 
+   if (da >= df) Error("MulByXMod: bad args");
 
    MulByX(c, a);
@@ -3125 +3125 @@
    long da = deg(a);
    long df = deg(f);
-   if (da >= df) Error("MulByXMod: bad args"); 
+   if (da >= df) Error("MulByXMod: bad args");
 
    MulByX(c, a);
@@ -3171 +3171 @@
    res.SetMaxLength(da*e + 1);
    res = 1;
-   
+
    long k = NumBits(e);
    long i;
@@ -3203 +3203 @@
    long n = deg(f);
 
-   if (n <= 0) 
+   if (n <= 0)
       Error("TraceVec: bad args");
 
@@ -3213 +3213 @@
    GF2X x = reverse(-LeftShift(reverse(diff(reverse(f)), n-1), n-1)/f, n-1);
 
-   VectorCopy(S, x, n); 
+   VectorCopy(S, x, n);
    S.put(0, to_GF2(n));
 }
@@ -3246 +3246 @@
       Error("trace: bad args");
 
-   if (F.tracevec.length() == 0) 
+   if (F.tracevec.length() == 0)
       ComputeTraceVec(F);
 
@@ -3499 +3499 @@
       return;
    }
-    
+
    GF2X u1, v1;
 
@@ -3665 +3665 @@
 
 void MinPolyInternal(GF2X& h, const GF2X& x, long m)
-{  
+{
    if (m < NTL_GF2X_BERMASS_CROSSOVER) {
       OldMinPolyInternal(h, x, m);
@@ -3673 +3673 @@
    GF2X a, b;
    _NTL_GF2XMatrix M;
-      
+
    SetCoeff(b, 2*m);
    CopyReverse(a, x, 2*m-1);

ntl/src/GF2XFactoring.c

@@ -17 +17 @@
 
    build(F, f);
-   
+
    GF2X h;
    SetX(h);
@@ -119 +119 @@
    } while (!finished);
 }
-         
+
 
 
@@ -130 +130 @@
 
 static
-void ProcessTable(GF2X& f, vec_pair_GF2X_long& factors, 
+void ProcessTable(GF2X& f, vec_pair_GF2X_long& factors,
                   const GF2XModulus& F, long limit, const vec_GF2X& tbl,
                   long d, long verbose)
@@ -167 +167 @@
 
    while (2*d <= deg(t1)) {
-      GCD(t2, tbl[i], t1); 
+      GCD(t2, tbl[i], t1);
       if (deg(t2) > 0) {
          AddFactor(factors, t2, d, verbose);
@@ -255 +255 @@
 
          if (deg(f) < old_n) {
-            // f has changed 
+            // f has changed
 
             build(F, f);
@@ -278 +278 @@
    GF2X a, g;
    GF2XModulus F;
-   
+
    build(F, f);
    long n = F.n;
@@ -305 +305 @@
    RecEDF(factors, f2, d);
 }
-         
+
 
 void EDF(vec_GF2X& factors, const GF2X& ff, long d, long verbose)
@@ -338 +338 @@
    }
 
-   
+
    double t;
 
@@ -369 +369 @@
    double t;
 
-   
+
    vec_pair_GF2X_long u;
    DDF(u, f, verbose);
@@ -394 +394 @@
    }
 }
-   
+
 void CanZass(vec_pair_GF2X_long& factors, const GF2X& f, long verbose)
 {
@@ -404 +404 @@
    vec_GF2X x;
 
-   
+
    SquareFreeDecomp(sfd, f);
 
@@ -497 +497 @@
 
 
-static int GF2X_irred_tab[][3] = 
+static int GF2X_irred_tab[][3] =
 
 {{0,0,0}, {0,0,0},
-{1,0,0}, {1,0,0}, {1,0,0}, {2,0,0}, {1,0,0}, {1,0,0}, 
-{4,3,1}, {1,0,0}, {3,0,0}, {2,0,0}, {3,0,0}, {4,3,1}, 
-{5,0,0}, {1,0,0}, {5,3,1}, {3,0,0}, {3,0,0}, {5,2,1}, 
-{3,0,0}, {2,0,0}, {1,0,0}, {5,0,0}, {4,3,1}, {3,0,0}, 
-{4,3,1}, {5,2,1}, {1,0,0}, {2,0,0}, {1,0,0}, {3,0,0}, 
-{7,3,2}, {10,0,0}, {7,0,0}, {2,0,0}, {9,0,0}, {6,4,1}, 
-{6,5,1}, {4,0,0}, {5,4,3}, {3,0,0}, {7,0,0}, {6,4,3}, 
-{5,0,0}, {4,3,1}, {1,0,0}, {5,0,0}, {5,3,2}, {9,0,0}, 
-{4,3,2}, {6,3,1}, {3,0,0}, {6,2,1}, {9,0,0}, {7,0,0}, 
-{7,4,2}, {4,0,0}, {19,0,0}, {7,4,2}, {1,0,0}, {5,2,1}, 
-{29,0,0}, {1,0,0}, {4,3,1}, {18,0,0}, {3,0,0}, {5,2,1}, 
-{9,0,0}, {6,5,2}, {5,3,1}, {6,0,0}, {10,9,3}, {25,0,0}, 
-{35,0,0}, {6,3,1}, {21,0,0}, {6,5,2}, {6,5,3}, {9,0,0}, 
-{9,4,2}, {4,0,0}, {8,3,1}, {7,4,2}, {5,0,0}, {8,2,1}, 
-{21,0,0}, {13,0,0}, {7,6,2}, {38,0,0}, {27,0,0}, {8,5,1}, 
-{21,0,0}, {2,0,0}, {21,0,0}, {11,0,0}, {10,9,6}, {6,0,0}, 
-{11,0,0}, {6,3,1}, {15,0,0}, {7,6,1}, {29,0,0}, {9,0,0}, 
-{4,3,1}, {4,0,0}, {15,0,0}, {9,7,4}, {17,0,0}, {5,4,2}, 
-{33,0,0}, {10,0,0}, {5,4,3}, {9,0,0}, {5,3,2}, {8,7,5}, 
-{4,2,1}, {5,2,1}, {33,0,0}, {8,0,0}, {4,3,1}, {18,0,0}, 
-{6,2,1}, {2,0,0}, {19,0,0}, {7,6,5}, {21,0,0}, {1,0,0}, 
-{7,2,1}, {5,0,0}, {3,0,0}, {8,3,2}, {17,0,0}, {9,8,2}, 
-{57,0,0}, {11,0,0}, {5,3,2}, {21,0,0}, {8,7,1}, {8,5,3}, 
-{15,0,0}, {10,4,1}, {21,0,0}, {5,3,2}, {7,4,2}, {52,0,0}, 
-{71,0,0}, {14,0,0}, {27,0,0}, {10,9,7}, {53,0,0}, {3,0,0}, 
-{6,3,2}, {1,0,0}, {15,0,0}, {62,0,0}, {9,0,0}, {6,5,2}, 
-{8,6,5}, {31,0,0}, {5,3,2}, {18,0,0}, {27,0,0}, {7,6,3}, 
-{10,8,7}, {9,8,3}, {37,0,0}, {6,0,0}, {15,3,2}, {34,0,0}, 
-{11,0,0}, {6,5,2}, {1,0,0}, {8,5,2}, {13,0,0}, {6,0,0}, 
-{11,3,2}, {8,0,0}, {31,0,0}, {4,2,1}, {3,0,0}, {7,6,1}, 
-{81,0,0}, {56,0,0}, {9,8,7}, {24,0,0}, {11,0,0}, {7,6,5}, 
-{6,5,2}, {6,5,2}, {8,7,6}, {9,0,0}, {7,2,1}, {15,0,0}, 
-{87,0,0}, {8,3,2}, {3,0,0}, {9,4,2}, {9,0,0}, {34,0,0}, 
-{5,3,2}, {14,0,0}, {55,0,0}, {8,7,1}, {27,0,0}, {9,5,2}, 
-{10,9,5}, {43,0,0}, {9,3,1}, {6,0,0}, {7,0,0}, {11,10,8}, 
-{105,0,0}, {6,5,2}, {73,0,0}, {23,0,0}, {7,3,1}, {45,0,0}, 
-{11,0,0}, {8,4,1}, {7,0,0}, {8,6,2}, {5,4,2}, {33,0,0}, 
-{9,8,3}, {32,0,0}, {10,7,3}, {10,9,4}, {113,0,0}, {10,4,1}, 
-{8,7,6}, {26,0,0}, {9,4,2}, {74,0,0}, {31,0,0}, {9,6,1}, 
-{5,0,0}, {7,4,1}, {73,0,0}, {36,0,0}, {8,5,3}, {70,0,0}, 
-{95,0,0}, {8,5,1}, {111,0,0}, {6,4,1}, {11,2,1}, {82,0,0}, 
-{15,14,10}, {35,0,0}, {103,0,0}, {7,4,2}, {15,0,0}, {46,0,0}, 
-{7,2,1}, {52,0,0}, {10,5,2}, {12,0,0}, {71,0,0}, {10,6,2}, 
-{15,0,0}, {7,6,4}, {9,8,4}, {93,0,0}, {9,6,2}, {42,0,0}, 
-{47,0,0}, {8,6,3}, {25,0,0}, {7,6,1}, {53,0,0}, {58,0,0}, 
-{9,3,2}, {23,0,0}, {67,0,0}, {11,10,9}, {63,0,0}, {12,6,3}, 
-{5,0,0}, {5,0,0}, {9,5,2}, {93,0,0}, {35,0,0}, {12,7,5}, 
-{53,0,0}, {10,7,5}, {69,0,0}, {71,0,0}, {11,10,1}, {21,0,0}, 
-{5,3,2}, {12,11,5}, {37,0,0}, {11,6,1}, {33,0,0}, {48,0,0}, 
-{7,3,2}, {5,0,0}, {11,8,4}, {11,6,4}, {5,0,0}, {9,5,2}, 
-{41,0,0}, {1,0,0}, {11,2,1}, {102,0,0}, {7,3,1}, {8,4,2}, 
-{15,0,0}, {10,6,4}, {93,0,0}, {7,5,3}, {9,7,4}, {79,0,0}, 
-{15,0,0}, {10,9,1}, {63,0,0}, {7,4,2}, {45,0,0}, {36,0,0}, 
-{4,3,1}, {31,0,0}, {67,0,0}, {10,3,1}, {51,0,0}, {10,5,2}, 
-{10,3,1}, {34,0,0}, {8,3,1}, {50,0,0}, {99,0,0}, {10,6,2}, 
-{89,0,0}, {2,0,0}, {5,2,1}, {10,7,2}, {7,4,1}, {55,0,0}, 
-{4,3,1}, {16,10,7}, {45,0,0}, {10,8,6}, {125,0,0}, {75,0,0}, 
-{7,2,1}, {22,0,0}, {63,0,0}, {11,10,3}, {103,0,0}, {6,5,2}, 
-{53,0,0}, {34,0,0}, {13,11,6}, {69,0,0}, {99,0,0}, {6,5,1}, 
-{10,9,7}, {11,10,2}, {57,0,0}, {68,0,0}, {5,3,2}, {7,4,1}, 
-{63,0,0}, {8,5,3}, {9,0,0}, {9,6,5}, {29,0,0}, {21,0,0}, 
-{7,3,2}, {91,0,0}, {139,0,0}, {8,3,2}, {111,0,0}, {8,7,2}, 
-{8,6,5}, {16,0,0}, {8,7,5}, {41,0,0}, {43,0,0}, {10,8,5}, 
-{47,0,0}, {5,2,1}, {81,0,0}, {90,0,0}, {12,3,2}, {6,0,0}, 
-{83,0,0}, {8,7,1}, {159,0,0}, {10,9,5}, {9,0,0}, {28,0,0}, 
-{13,10,6}, {7,0,0}, {135,0,0}, {11,6,5}, {25,0,0}, {12,7,6}, 
-{7,6,2}, {26,0,0}, {5,3,2}, {152,0,0}, {171,0,0}, {9,8,5}, 
-{65,0,0}, {13,8,2}, {141,0,0}, {71,0,0}, {5,3,2}, {87,0,0}, 
-{10,4,3}, {12,10,3}, {147,0,0}, {10,7,6}, {13,0,0}, {102,0,0}, 
-{9,5,2}, {107,0,0}, {199,0,0}, {15,5,4}, {7,0,0}, {5,4,2}, 
-{149,0,0}, {25,0,0}, {9,7,2}, {12,0,0}, {63,0,0}, {11,6,5}, 
-{105,0,0}, {10,8,7}, {14,6,1}, {120,0,0}, {13,4,3}, {33,0,0}, 
-{12,11,5}, {12,9,5}, {165,0,0}, {6,2,1}, {65,0,0}, {49,0,0}, 
-{4,3,1}, {7,0,0}, {7,5,2}, {10,6,1}, {81,0,0}, {7,6,4}, 
-{105,0,0}, {73,0,0}, {11,6,4}, {134,0,0}, {47,0,0}, {16,10,1}, 
-{6,5,4}, {15,6,4}, {8,6,1}, {38,0,0}, {18,9,6}, {16,0,0}, 
-{203,0,0}, {12,5,2}, {19,0,0}, {7,6,1}, {73,0,0}, {93,0,0}, 
-{19,18,13}, {31,0,0}, {14,11,6}, {11,6,1}, {27,0,0}, {9,5,2}, 
-{9,0,0}, {1,0,0}, {11,3,2}, {200,0,0}, {191,0,0}, {9,8,4}, 
-{9,0,0}, {16,15,7}, {121,0,0}, {104,0,0}, {15,9,6}, {138,0,0}, 
-{9,6,5}, {9,6,4}, {105,0,0}, {17,16,6}, {81,0,0}, {94,0,0}, 
-{4,3,1}, {83,0,0}, {219,0,0}, {11,6,3}, {7,0,0}, {10,5,3}, 
-{17,0,0}, {76,0,0}, {16,5,2}, {78,0,0}, {155,0,0}, {11,6,5}, 
-{27,0,0}, {5,4,2}, {8,5,4}, {3,0,0}, {15,14,6}, {156,0,0}, 
-{23,0,0}, {13,6,3}, {9,0,0}, {8,7,3}, {69,0,0}, {10,0,0}, 
-{8,5,2}, {26,0,0}, {67,0,0}, {14,7,4}, {21,0,0}, {12,10,2}, 
-{33,0,0}, {79,0,0}, {15,11,2}, {32,0,0}, {39,0,0}, {13,6,2}, 
-{167,0,0}, {6,4,1}, {97,0,0}, {47,0,0}, {11,6,2}, {42,0,0}, 
-{10,7,3}, {10,5,4}, {1,0,0}, {4,3,2}, {161,0,0}, {8,6,2}, 
-{7,5,3}, {94,0,0}, {195,0,0}, {10,5,4}, {9,0,0}, {13,10,4}, 
-{8,6,1}, {16,0,0}, {8,3,1}, {122,0,0}, {8,2,1}, {13,7,4}, 
-{10,5,3}, {16,4,3}, {193,0,0}, {135,0,0}, {19,16,9}, {39,0,0}, 
-{10,8,7}, {10,9,4}, {153,0,0}, {7,6,5}, {73,0,0}, {34,0,0}, 
-{11,9,6}, {71,0,0}, {11,4,2}, {14,7,3}, {163,0,0}, {11,6,1}, 
-{153,0,0}, {28,0,0}, {15,7,6}, {77,0,0}, {67,0,0}, {10,5,2}, 
-{12,8,1}, {10,6,4}, {13,0,0}, {146,0,0}, {13,4,3}, {25,0,0}, 
-{23,22,16}, {12,9,7}, {237,0,0}, {13,7,6}, {85,0,0}, {130,0,0}, 
-{14,13,3}, {88,0,0}, {7,5,2}, {11,6,1}, {35,0,0}, {10,4,3}, 
-{93,0,0}, {9,6,4}, {13,6,3}, {86,0,0}, {19,0,0}, {9,2,1}, 
-{273,0,0}, {14,12,9}, {7,6,1}, {30,0,0}, {9,5,2}, {201,0,0}, 
-{215,0,0}, {6,4,3}, {105,0,0}, {10,7,5}, {165,0,0}, {105,0,0}, 
-{19,13,6}, {31,0,0}, {127,0,0}, {10,4,2}, {81,0,0}, {19,10,4}, 
-{45,0,0}, {211,0,0}, {19,10,3}, {200,0,0}, {295,0,0}, {9,8,5}, 
-{9,0,0}, {12,6,5}, {297,0,0}, {68,0,0}, {11,6,5}, {133,0,0}, 
-{251,0,0}, {13,8,4}, {223,0,0}, {6,5,2}, {7,4,2}, {307,0,0}, 
-{9,2,1}, {101,0,0}, {39,0,0}, {14,10,4}, {217,0,0}, {14,9,1}, 
-{6,5,1}, {16,0,0}, {14,3,2}, {11,0,0}, {119,0,0}, {11,3,2}, 
-{11,6,5}, {11,8,4}, {249,0,0}, {5,0,0}, {13,3,1}, {37,0,0}, 
-{3,0,0}, {14,0,0}, {93,0,0}, {10,8,7}, {33,0,0}, {88,0,0}, 
-{7,5,4}, {38,0,0}, {55,0,0}, {15,4,2}, {11,0,0}, {12,11,4}, 
-{21,0,0}, {107,0,0}, {11,9,8}, {33,0,0}, {10,7,2}, {18,7,3}, 
-{147,0,0}, {5,4,2}, {153,0,0}, {15,0,0}, {11,6,5}, {28,0,0}, 
-{11,7,4}, {6,3,1}, {31,0,0}, {8,4,3}, {15,5,3}, {66,0,0}, 
-{23,16,9}, {11,9,3}, {171,0,0}, {11,6,1}, {209,0,0}, {4,3,1}, 
-{197,0,0}, {13,0,0}, {19,14,6}, {14,0,0}, {79,0,0}, {13,6,2}, 
-{299,0,0}, {15,8,2}, {169,0,0}, {177,0,0}, {23,10,2}, {267,0,0}, 
-{215,0,0}, {15,10,1}, {75,0,0}, {16,4,2}, {37,0,0}, {12,7,1}, 
-{8,3,2}, {17,0,0}, {12,11,8}, {15,8,5}, {15,0,0}, {4,3,1}, 
-{13,12,4}, {92,0,0}, {5,4,3}, {41,0,0}, {23,0,0}, {7,4,1}, 
-{183,0,0}, {16,7,1}, {165,0,0}, {150,0,0}, {9,6,4}, {9,0,0}, 
-{231,0,0}, {16,10,4}, {207,0,0}, {9,6,5}, {5,0,0}, {180,0,0}, 
-{4,3,2}, {58,0,0}, {147,0,0}, {8,6,2}, {343,0,0}, {8,7,2}, 
-{11,6,1}, {44,0,0}, {13,8,6}, {5,0,0}, {347,0,0}, {18,16,8}, 
-{135,0,0}, {9,8,3}, {85,0,0}, {90,0,0}, {13,11,1}, {258,0,0}, 
-{351,0,0}, {10,6,4}, {19,0,0}, {7,6,1}, {309,0,0}, {18,0,0}, 
-{13,10,3}, {158,0,0}, {19,0,0}, {12,10,1}, {45,0,0}, {7,6,1}, 
-{233,0,0}, {98,0,0}, {11,6,5}, {3,0,0}, {83,0,0}, {16,14,9}, 
-{6,5,3}, {9,7,4}, {22,19,9}, {168,0,0}, {19,17,4}, {120,0,0}, 
-{14,5,2}, {17,15,6}, {7,0,0}, {10,8,6}, {185,0,0}, {93,0,0}, 
-{15,14,7}, {29,0,0}, {375,0,0}, {10,8,3}, {13,0,0}, {17,16,2}, 
-{329,0,0}, {68,0,0}, {13,9,6}, {92,0,0}, {12,10,3}, {7,6,3}, 
-{17,10,3}, {5,2,1}, {9,6,1}, {30,0,0}, {9,7,3}, {253,0,0}, 
-{143,0,0}, {7,4,1}, {9,4,1}, {12,10,4}, {53,0,0}, {25,0,0}, 
-{9,7,1}, {217,0,0}, {15,13,9}, {14,9,2}, {75,0,0}, {8,7,2}, 
-{21,0,0}, {7,0,0}, {14,3,2}, {15,0,0}, {159,0,0}, {12,10,8}, 
-{29,0,0}, {10,3,1}, {21,0,0}, {333,0,0}, {11,8,2}, {52,0,0}, 
-{119,0,0}, {16,9,7}, {123,0,0}, {15,11,2}, {17,0,0}, {9,0,0}, 
-{11,6,4}, {38,0,0}, {255,0,0}, {12,10,7}, {189,0,0}, {4,3,1}, 
-{17,10,7}, {49,0,0}, {13,5,2}, {149,0,0}, {15,0,0}, {14,7,5}, 
-{10,9,2}, {8,6,5}, {61,0,0}, {54,0,0}, {11,5,1}, {144,0,0}, 
-{47,0,0}, {11,10,7}, {105,0,0}, {2,0,0}, {105,0,0}, {136,0,0}, 
-{11,4,1}, {253,0,0}, {111,0,0}, {13,10,5}, {159,0,0}, {10,7,1}, 
-{7,5,3}, {29,0,0}, {19,10,3}, {119,0,0}, {207,0,0}, {17,15,4}, 
-{35,0,0}, {14,0,0}, {349,0,0}, {6,3,2}, {21,10,6}, {1,0,0}, 
-{75,0,0}, {9,5,2}, {145,0,0}, {11,7,6}, {301,0,0}, {378,0,0}, 
-{13,3,1}, {352,0,0}, {12,7,4}, {12,8,1}, {149,0,0}, {6,5,4}, 
-{12,9,8}, {11,0,0}, {15,7,5}, {78,0,0}, {99,0,0}, {17,16,12}, 
-{173,0,0}, {8,7,1}, {13,9,8}, {147,0,0}, {19,18,10}, {127,0,0}, 
-{183,0,0}, {12,4,1}, {31,0,0}, {11,8,6}, {173,0,0}, {12,0,0}, 
-{7,5,3}, {113,0,0}, {207,0,0}, {18,15,5}, {1,0,0}, {13,7,6}, 
-{21,0,0}, {35,0,0}, {12,7,2}, {117,0,0}, {123,0,0}, {12,10,2}, 
-{143,0,0}, {14,4,1}, {15,9,7}, {204,0,0}, {7,5,1}, {91,0,0}, 
-{4,2,1}, {8,6,3}, {183,0,0}, {12,10,7}, {77,0,0}, {36,0,0}, 
-{14,9,6}, {221,0,0}, {7,6,5}, {16,14,13}, {31,0,0}, {16,15,7}, 
-{365,0,0}, {403,0,0}, {10,3,2}, {11,4,3}, {31,0,0}, {10,9,4}, 
-{177,0,0}, {16,6,1}, {22,6,5}, {417,0,0}, {15,13,12}, {217,0,0}, 
-{207,0,0}, {7,5,4}, {10,7,1}, {11,6,1}, {45,0,0}, {24,0,0}, 
-{12,11,9}, {77,0,0}, {21,20,13}, {9,6,5}, {189,0,0}, {8,3,2}, 
-{13,12,10}, {260,0,0}, {16,9,7}, {168,0,0}, {131,0,0}, {7,6,3}, 
-{305,0,0}, {10,9,6}, {13,9,4}, {143,0,0}, {12,9,3}, {18,0,0}, 
-{15,8,5}, {20,9,6}, {103,0,0}, {15,4,2}, {201,0,0}, {36,0,0}, 
-{9,5,2}, {31,0,0}, {11,7,2}, {6,2,1}, {7,0,0}, {13,6,4}, 
-{9,8,7}, {19,0,0}, {17,10,6}, {15,0,0}, {9,3,1}, {178,0,0}, 
-{8,7,6}, {12,6,5}, {177,0,0}, {230,0,0}, {24,9,3}, {222,0,0}, 
-{3,0,0}, {16,13,12}, {121,0,0}, {10,4,2}, {161,0,0}, {39,0,0}, 
-{17,15,13}, {62,0,0}, {223,0,0}, {15,12,2}, {65,0,0}, {12,6,3}, 
-{101,0,0}, {59,0,0}, {5,4,3}, {17,0,0}, {5,3,2}, {13,8,3}, 
-{10,9,7}, {12,8,2}, {5,4,3}, {75,0,0}, {19,17,8}, {55,0,0}, 
-{99,0,0}, {10,7,4}, {115,0,0}, {9,8,6}, {385,0,0}, {186,0,0}, 
-{15,6,3}, {9,4,1}, {12,10,5}, {10,8,1}, {135,0,0}, {5,2,1}, 
-{317,0,0}, {7,0,0}, {19,6,1}, {294,0,0}, {35,0,0}, {13,12,6}, 
-{119,0,0}, {98,0,0}, {93,0,0}, {68,0,0}, {21,15,3}, {108,0,0}, 
-{75,0,0}, {12,6,5}, {411,0,0}, {12,7,2}, {13,7,2}, {21,0,0}, 
-{15,10,8}, {412,0,0}, {439,0,0}, {10,7,6}, {41,0,0}, {13,9,6}, 
-{8,5,2}, {10,0,0}, {15,7,2}, {141,0,0}, {159,0,0}, {13,12,10}, 
-{291,0,0}, {10,9,1}, {105,0,0}, {24,0,0}, {11,2,1}, {198,0,0}, 
-{27,0,0}, {6,3,1}, {439,0,0}, {10,3,1}, {49,0,0}, {168,0,0}, 
-{13,11,9}, {463,0,0}, {10,9,3}, {13,9,8}, {15,8,3}, {18,16,8}, 
-{15,14,11}, {7,0,0}, {19,9,8}, {12,6,3}, {7,4,3}, {15,14,5}, 
-{8,6,3}, {10,9,7}, {361,0,0}, {230,0,0}, {15,9,6}, {24,0,0}, 
-{407,0,0}, {16,7,2}, {189,0,0}, {62,0,0}, {189,0,0}, {112,0,0}, 
-{22,21,10}, {91,0,0}, {79,0,0}, {12,10,5}, {23,0,0}, {7,6,1}, 
-{57,0,0}, {139,0,0}, {24,15,6}, {14,0,0}, {83,0,0}, {16,9,1}, 
-{35,0,0}, {9,7,4}, {117,0,0}, {65,0,0}, {21,9,6}, {21,0,0}, 
-{195,0,0}, {23,11,10}, {327,0,0}, {17,14,3}, {417,0,0}, {13,0,0}, 
-{15,8,6}, {107,0,0}, {19,10,6}, {18,15,3}, {59,0,0}, {12,10,4}, 
-{9,7,5}, {283,0,0}, {13,9,6}, {62,0,0}, {427,0,0}, {14,7,3}, 
-{8,7,4}, {15,8,3}, {105,0,0}, {27,0,0}, {7,3,1}, {103,0,0}, 
-{551,0,0}, {10,6,1}, {6,4,1}, {11,6,4}, {129,0,0}, {9,0,0}, 
-{9,4,2}, {277,0,0}, {31,0,0}, {13,12,5}, {141,0,0}, {12,7,3}, 
-{357,0,0}, {7,2,1}, {11,9,7}, {227,0,0}, {131,0,0}, {7,6,3}, 
-{23,0,0}, {20,17,3}, {13,4,1}, {90,0,0}, {15,3,2}, {241,0,0}, 
-{75,0,0}, {13,6,1}, {307,0,0}, {8,7,3}, {245,0,0}, {66,0,0}, 
-{15,11,2}, {365,0,0}, {18,16,11}, {11,10,1}, {19,0,0}, {8,6,1}, 
-{189,0,0}, {133,0,0}, {12,7,2}, {114,0,0}, {27,0,0}, {6,5,1}, 
-{15,5,2}, {17,14,5}, {133,0,0}, {476,0,0}, {11,9,3}, {16,0,0}, 
-{375,0,0}, {15,8,6}, {25,0,0}, {17,11,6}, {77,0,0}, {87,0,0}, 
-{5,3,2}, {134,0,0}, {171,0,0}, {13,8,4}, {75,0,0}, {8,3,1}, 
-{233,0,0}, {196,0,0}, {9,8,7}, {173,0,0}, {15,14,12}, {13,6,5}, 
-{281,0,0}, {9,8,2}, {405,0,0}, {114,0,0}, {15,9,6}, {171,0,0}, 
-{287,0,0}, {8,4,2}, {43,0,0}, {4,2,1}, {513,0,0}, {273,0,0}, 
-{11,10,6}, {118,0,0}, {243,0,0}, {14,7,1}, {203,0,0}, {9,5,2}, 
-{257,0,0}, {302,0,0}, {27,25,9}, {393,0,0}, {91,0,0}, {12,10,6}, 
-{413,0,0}, {15,14,9}, {18,16,1}, {255,0,0}, {12,9,7}, {234,0,0}, 
-{167,0,0}, {16,13,10}, {27,0,0}, {15,6,2}, {433,0,0}, {105,0,0}, 
-{25,10,2}, {151,0,0}, {427,0,0}, {13,9,8}, {49,0,0}, {10,6,4}, 
-{153,0,0}, {4,0,0}, {17,7,5}, {54,0,0}, {203,0,0}, {16,15,1}, 
-{16,14,7}, {13,6,1}, {25,0,0}, {14,0,0}, {15,5,3}, {187,0,0}, 
-{15,13,10}, {13,10,5}, {97,0,0}, {11,10,9}, {19,10,4}, {589,0,0}, 
-{31,30,2}, {289,0,0}, {9,6,4}, {11,8,6}, {21,0,0}, {7,4,1}, 
-{7,4,2}, {77,0,0}, {5,3,2}, {119,0,0}, {7,0,0}, {9,5,2}, 
-{345,0,0}, {17,10,8}, {333,0,0}, {17,0,0}, {16,9,7}, {168,0,0}, 
-{15,13,4}, {11,10,1}, {217,0,0}, {18,11,10}, {189,0,0}, {216,0,0}, 
-{12,7,5}, {229,0,0}, {231,0,0}, {12,9,3}, {223,0,0}, {10,9,1}, 
-{153,0,0}, {470,0,0}, {23,16,6}, {99,0,0}, {10,4,3}, {9,8,4}, 
-{12,10,1}, {14,9,6}, {201,0,0}, {38,0,0}, {15,14,2}, {198,0,0}, 
-{399,0,0}, {14,11,5}, {75,0,0}, {11,10,1}, {77,0,0}, {16,12,8}, 
-{20,17,15}, {326,0,0}, {39,0,0}, {14,12,9}, {495,0,0}, {8,3,2}, 
-{333,0,0}, {476,0,0}, {15,14,2}, {164,0,0}, {19,0,0}, {12,4,2}, 
-{8,6,3}, {13,12,3}, {12,11,5}, {129,0,0}, {12,9,3}, {52,0,0}, 
-{10,8,3}, {17,16,2}, {337,0,0}, {12,9,3}, {397,0,0}, {277,0,0}, 
-{21,11,3}, {73,0,0}, {11,6,1}, {7,5,4}, {95,0,0}, {11,3,2}, 
-{617,0,0}, {392,0,0}, {8,3,2}, {75,0,0}, {315,0,0}, {15,6,4}, 
-{125,0,0}, {6,5,2}, {15,9,7}, {348,0,0}, {15,6,1}, {553,0,0}, 
-{6,3,2}, {10,9,7}, {553,0,0}, {14,10,4}, {237,0,0}, {39,0,0}, 
-{17,14,6}, {371,0,0}, {255,0,0}, {8,4,1}, {131,0,0}, {14,6,1}, 
-{117,0,0}, {98,0,0}, {5,3,2}, {56,0,0}, {655,0,0}, {9,5,2}, 
-{239,0,0}, {11,8,4}, {1,0,0}, {134,0,0}, {15,9,5}, {88,0,0}, 
-{10,5,3}, {10,9,4}, {181,0,0}, {15,11,2}, {609,0,0}, {52,0,0}, 
-{19,18,10}, {100,0,0}, {7,6,3}, {15,8,2}, {183,0,0}, {18,7,6}, 
-{10,9,2}, {130,0,0}, {11,5,1}, {12,0,0}, {219,0,0}, {13,10,7}, 
-{11,0,0}, {19,9,4}, {129,0,0}, {3,0,0}, {17,15,5}, {300,0,0}, 
-{17,13,9}, {14,6,5}, {97,0,0}, {13,8,3}, {601,0,0}, {55,0,0}, 
-{8,3,1}, {92,0,0}, {127,0,0}, {12,11,2}, {81,0,0}, {15,10,8}, 
-{13,2,1}, {47,0,0}, {14,13,6}, {194,0,0}, {383,0,0}, {25,14,11}, 
-{125,0,0}, {20,19,16}, {429,0,0}, {282,0,0}, {10,9,6}, {342,0,0}, 
-{5,3,2}, {15,9,4}, {33,0,0}, {9,4,2}, {49,0,0}, {15,0,0}, 
-{11,6,2}, {28,0,0}, {103,0,0}, {18,17,8}, {27,0,0}, {11,6,5}, 
-{33,0,0}, {17,0,0}, {11,10,6}, {387,0,0}, {363,0,0}, {15,10,9}, 
-{83,0,0}, {7,6,4}, {357,0,0}, {13,12,4}, {14,13,7}, {322,0,0}, 
-{395,0,0}, {16,5,1}, {595,0,0}, {13,10,3}, {421,0,0}, {195,0,0}, 
-{11,3,2}, {13,0,0}, {16,12,3}, {14,3,1}, {315,0,0}, {26,10,5}, 
-{297,0,0}, {52,0,0}, {9,4,2}, {314,0,0}, {243,0,0}, {16,14,9}, 
-{185,0,0}, {12,5,3}, {13,5,2}, {575,0,0}, {12,9,3}, {39,0,0}, 
-{311,0,0}, {13,5,2}, {181,0,0}, {20,18,14}, {49,0,0}, {25,0,0}, 
-{11,4,1}, {77,0,0}, {17,11,10}, {15,14,8}, {21,0,0}, {17,10,5}, 
-{69,0,0}, {49,0,0}, {11,10,2}, {32,0,0}, {411,0,0}, {21,16,3}, 
-{11,7,4}, {22,10,3}, {85,0,0}, {140,0,0}, {9,8,6}, {252,0,0}, 
-{279,0,0}, {9,5,2}, {307,0,0}, {17,10,4}, {13,12,9}, {94,0,0}, 
-{13,11,4}, {49,0,0}, {17,11,10}, {16,12,5}, {25,0,0}, {6,5,2}, 
-{12,5,1}, {80,0,0}, {8,3,2}, {246,0,0}, {11,5,2}, {11,10,2}, 
-{599,0,0}, {18,12,10}, {189,0,0}, {278,0,0}, {10,9,3}, {399,0,0}, 
-{299,0,0}, {13,10,6}, {277,0,0}, {13,10,6}, {69,0,0}, {220,0,0}, 
-{13,10,3}, {229,0,0}, {18,11,10}, {16,15,1}, {27,0,0}, {18,9,3}, 
-{473,0,0}, {373,0,0}, {18,17,7}, {60,0,0}, {207,0,0}, {13,9,8}, 
-{22,20,13}, {25,18,7}, {225,0,0}, {404,0,0}, {21,6,2}, {46,0,0}, 
-{6,2,1}, {17,12,6}, {75,0,0}, {4,2,1}, {365,0,0}, {445,0,0}, 
-{11,7,1}, {44,0,0}, {10,8,5}, {12,5,2}, {63,0,0}, {17,4,2}, 
-{189,0,0}, {557,0,0}, {19,12,2}, {252,0,0}, {99,0,0}, {10,8,5}, 
-{65,0,0}, {14,9,3}, {9,0,0}, {119,0,0}, {8,5,2}, {339,0,0}, 
-{95,0,0}, {12,9,7}, {7,0,0}, {13,10,2}, {77,0,0}, {127,0,0}, 
-{21,10,7}, {319,0,0}, {667,0,0}, {17,10,3}, {501,0,0}, {18,12,9}, 
-{9,8,5}, {17,0,0}, {20,9,2}, {341,0,0}, {731,0,0}, {7,6,5}, 
-{647,0,0}, {10,4,2}, {121,0,0}, {20,0,0}, {21,19,13}, {574,0,0}, 
-{399,0,0}, {15,10,7}, {85,0,0}, {16,8,3}, {169,0,0}, {15,0,0}, 
-{12,7,5}, {568,0,0}, {10,7,1}, {18,2,1}, {3,0,0}, {14,3,2}, 
-{13,7,3}, {643,0,0}, {14,11,1}, {548,0,0}, {783,0,0}, {14,11,1}, 
-{317,0,0}, {7,6,4}, {153,0,0}, {87,0,0}, {15,13,1}, {231,0,0}, 
-{11,5,3}, {18,13,7}, {771,0,0}, {30,20,11}, {15,6,3}, {103,0,0}, 
-{13,4,3}, {182,0,0}, {211,0,0}, {17,6,1}, {27,0,0}, {13,12,10}, 
-{15,14,10}, {17,0,0}, {13,11,5}, {69,0,0}, {11,5,1}, {18,6,1}, 
-{603,0,0}, {10,4,2}, {741,0,0}, {668,0,0}, {17,15,3}, {147,0,0}, 
-{227,0,0}, {15,10,9}, {37,0,0}, {16,6,1}, {173,0,0}, {427,0,0}, 
-{7,5,1}, {287,0,0}, {231,0,0}, {20,15,10}, {18,9,1}, {14,12,5}, 
-{16,5,1}, {310,0,0}, {18,13,1}, {434,0,0}, {579,0,0}, {18,13,8}, 
-{45,0,0}, {12,8,3}, {16,9,5}, {53,0,0}, {19,15,10}, {16,0,0}, 
-{17,6,5}, {17,10,1}, {37,0,0}, {17,10,9}, {21,13,7}, {99,0,0}, 
-{17,9,6}, {176,0,0}, {271,0,0}, {18,17,13}, {459,0,0}, {21,17,10}, 
-{6,5,2}, {202,0,0}, {5,4,3}, {90,0,0}, {755,0,0}, {15,7,2}, 
-{363,0,0}, {8,4,2}, {129,0,0}, {20,0,0}, {11,6,2}, {135,0,0}, 
-{15,8,7}, {14,13,2}, {10,4,3}, {24,13,10}, {19,14,11}, {31,0,0}, 
-{15,8,6}, {758,0,0}, {16,11,5}, {16,5,1}, {359,0,0}, {23,18,17}, 
-{501,0,0}, {29,0,0}, {15,6,3}, {201,0,0}, {459,0,0}, {12,10,7}, 
-{225,0,0}, {22,17,13}, {24,22,5}, {161,0,0}, {14,11,3}, {52,0,0}, 
-{19,17,6}, {21,14,12}, {93,0,0}, {13,10,3}, {201,0,0}, {178,0,0}, 
-{15,12,5}, {250,0,0}, {7,6,4}, {17,13,6}, {221,0,0}, {13,11,8}, 
-{17,14,9}, {113,0,0}, {17,14,10}, {300,0,0}, {39,0,0}, {18,13,3}, 
-{261,0,0}, {15,14,8}, {753,0,0}, {8,4,3}, {11,10,5}, {94,0,0}, 
-{15,13,1}, {10,4,2}, {14,11,10}, {8,6,2}, {461,0,0}, {418,0,0}, 
-{19,14,6}, {403,0,0}, {267,0,0}, {10,9,2}, {259,0,0}, {20,4,3}, 
-{869,0,0}, {173,0,0}, {19,18,2}, {369,0,0}, {255,0,0}, {22,12,9}, 
-{567,0,0}, {20,11,7}, {457,0,0}, {482,0,0}, {6,3,2}, {775,0,0}, 
-{19,17,6}, {6,4,3}, {99,0,0}, {15,14,8}, {6,5,2}, {165,0,0}, 
-{8,3,2}, {13,12,10}, {25,21,17}, {17,14,9}, {105,0,0}, {17,15,14}, 
-{10,3,2}, {250,0,0}, {25,6,5}, {327,0,0}, {279,0,0}, {13,6,5}, 
-{371,0,0}, {15,9,4}, {117,0,0}, {486,0,0}, {10,9,3}, {217,0,0}, 
-{635,0,0}, {30,27,17}, {457,0,0}, {16,6,2}, {57,0,0}, {439,0,0}, 
-{23,21,6}, {214,0,0}, {20,13,6}, {20,16,1}, {819,0,0}, {15,11,8}, 
-{593,0,0}, {190,0,0}, {17,14,3}, {114,0,0}, {21,18,3}, {10,5,2}, 
-{12,9,5}, {8,6,3}, {69,0,0}, {312,0,0}, {22,5,2}, {502,0,0}, 
-{843,0,0}, {15,10,3}, {747,0,0}, {6,5,2}, {101,0,0}, {123,0,0}, 
-{19,16,9}, {521,0,0}, {171,0,0}, {16,7,2}, {12,6,5}, {22,21,20}, 
-{545,0,0}, {163,0,0}, {23,18,1}, {479,0,0}, {495,0,0}, {13,6,5}, 
-{11,0,0}, {17,5,2}, {18,8,1}, {684,0,0}, {7,5,1}, {9,0,0}, 
-{18,11,3}, {22,20,13}, {273,0,0}, {4,3,2}, {381,0,0}, {51,0,0}, 
-{18,13,7}, {518,0,0}, {9,5,1}, {14,12,3}, {243,0,0}, {21,17,2}, 
-{53,0,0}, {836,0,0}, {21,10,2}, {66,0,0}, {12,10,7}, {13,9,8}, 
-{339,0,0}, {16,11,5}, {901,0,0}, {180,0,0}, {16,13,3}, {49,0,0}, 
-{6,3,2}, {15,4,1}, {16,13,6}, {18,15,12}, {885,0,0}, {39,0,0}, 
-{11,9,4}, {688,0,0}, {16,15,7}, {13,10,6}, {13,0,0}, {25,23,12}, 
-{149,0,0}, {260,0,0}, {11,9,1}, {53,0,0}, {11,0,0}, {12,4,2}, 
-{9,7,5}, {11,8,1}, {121,0,0}, {261,0,0}, {10,5,2}, {199,0,0}, 
-{20,4,3}, {17,9,2}, {13,9,4}, {12,8,7}, {253,0,0}, {174,0,0}, 
-{15,4,2}, {370,0,0}, {9,6,1}, {16,10,9}, {669,0,0}, {20,10,9}, 
-{833,0,0}, {353,0,0}, {17,13,2}, {29,0,0}, {371,0,0}, {9,8,5}, 
-{8,7,1}, {19,8,7}, {12,11,10}, {873,0,0}, {26,11,2}, {12,9,1}, 
-{10,7,2}, {13,6,1}, {235,0,0}, {26,24,19}, {733,0,0}, {778,0,0}, 
-{12,11,1}, {344,0,0}, {931,0,0}, {16,6,4}, {945,0,0}, {21,19,14}, 
-{18,13,11}, {67,0,0}, {20,15,10}, {462,0,0}, {14,5,1}, {10,9,6}, 
-{18,11,10}, {16,9,7}, {477,0,0}, {105,0,0}, {11,3,2}, {468,0,0}, 
-{23,16,15}, {16,15,6}, {327,0,0}, {23,10,4}, {357,0,0}, {25,0,0}, 
-{17,16,7}, {31,0,0}, {7,5,2}, {16,7,6}, {277,0,0}, {14,13,6}, 
-{413,0,0}, {103,0,0}, {15,10,1}, {231,0,0}, {747,0,0}, {5,2,1}, 
-{113,0,0}, {20,10,7}, {15,9,6}, {11,0,0}, {27,22,18}, {91,0,0}, 
-{51,0,0}, {18,13,12}, {603,0,0}, {10,7,3}, {9,0,0}, {121,0,0}, 
-{15,14,6}, {17,0,0}, {16,11,2}, {23,15,6}, {279,0,0}, {16,12,6}, 
-{89,0,0}, {371,0,0}, {17,15,2}, {771,0,0}, {99,0,0}, {7,6,3}, 
-{21,0,0}, {10,7,5}, {801,0,0}, {26,0,0}, {25,19,14}, {175,0,0}, 
-{10,7,2}, {20,5,4}, {12,11,1}, {22,5,1}, {165,0,0}, {841,0,0}, 
-{25,19,17}, {238,0,0}, {11,8,6}, {22,21,4}, {33,0,0}, {8,7,6}, 
-{14,9,2}, {113,0,0}, {13,11,5}, {311,0,0}, {891,0,0}, {20,16,14}, 
-{555,0,0}, {23,14,8}, {133,0,0}, {546,0,0}, {6,3,2}, {103,0,0}, 
-{15,0,0}, {10,7,3}, {307,0,0}, {14,10,1}, {15,12,2}, {367,0,0}, 
-{13,10,6}, {169,0,0}, {22,21,11}, {12,10,8}, {441,0,0}, {17,12,7}, 
-{917,0,0}, {205,0,0}, {26,23,13}, {54,0,0}, {459,0,0}, {17,15,4}, 
-{19,15,4}, {5,4,2}, {9,7,6}, {42,0,0}, {21,15,7}, {330,0,0}, 
-{20,7,3}, {20,7,2}, {81,0,0}, {19,14,1}, {349,0,0}, {165,0,0}, 
-{40,35,9}, {274,0,0}, {475,0,0}, {11,10,3}, {93,0,0}, {12,7,4}, 
-{13,12,2}, {386,0,0}, {7,6,2}, {881,0,0}, {143,0,0}, {9,8,4}, 
-{71,0,0}, {19,18,3}, {16,11,6}, {155,0,0}, {7,2,1}, {735,0,0}, 
-{16,8,7}, {9,7,4}, {45,0,0}, {7,6,4}, {12,11,3}, {3,0,0}, 
+{1,0,0}, {1,0,0}, {1,0,0}, {2,0,0}, {1,0,0}, {1,0,0},
+{4,3,1}, {1,0,0}, {3,0,0}, {2,0,0}, {3,0,0}, {4,3,1},
+{5,0,0}, {1,0,0}, {5,3,1}, {3,0,0}, {3,0,0}, {5,2,1},
+{3,0,0}, {2,0,0}, {1,0,0}, {5,0,0}, {4,3,1}, {3,0,0},
+{4,3,1}, {5,2,1}, {1,0,0}, {2,0,0}, {1,0,0}, {3,0,0},
+{7,3,2}, {10,0,0}, {7,0,0}, {2,0,0}, {9,0,0}, {6,4,1},
+{6,5,1}, {4,0,0}, {5,4,3}, {3,0,0}, {7,0,0}, {6,4,3},
+{5,0,0}, {4,3,1}, {1,0,0}, {5,0,0}, {5,3,2}, {9,0,0},
+{4,3,2}, {6,3,1}, {3,0,0}, {6,2,1}, {9,0,0}, {7,0,0},
+{7,4,2}, {4,0,0}, {19,0,0}, {7,4,2}, {1,0,0}, {5,2,1},
+{29,0,0}, {1,0,0}, {4,3,1}, {18,0,0}, {3,0,0}, {5,2,1},
+{9,0,0}, {6,5,2}, {5,3,1}, {6,0,0}, {10,9,3}, {25,0,0},
+{35,0,0}, {6,3,1}, {21,0,0}, {6,5,2}, {6,5,3}, {9,0,0},
+{9,4,2}, {4,0,0}, {8,3,1}, {7,4,2}, {5,0,0}, {8,2,1},
+{21,0,0}, {13,0,0}, {7,6,2}, {38,0,0}, {27,0,0}, {8,5,1},
+{21,0,0}, {2,0,0}, {21,0,0}, {11,0,0}, {10,9,6}, {6,0,0},
+{11,0,0}, {6,3,1}, {15,0,0}, {7,6,1}, {29,0,0}, {9,0,0},
+{4,3,1}, {4,0,0}, {15,0,0}, {9,7,4}, {17,0,0}, {5,4,2},
+{33,0,0}, {10,0,0}, {5,4,3}, {9,0,0}, {5,3,2}, {8,7,5},
+{4,2,1}, {5,2,1}, {33,0,0}, {8,0,0}, {4,3,1}, {18,0,0},
+{6,2,1}, {2,0,0}, {19,0,0}, {7,6,5}, {21,0,0}, {1,0,0},
+{7,2,1}, {5,0,0}, {3,0,0}, {8,3,2}, {17,0,0}, {9,8,2},
+{57,0,0}, {11,0,0}, {5,3,2}, {21,0,0}, {8,7,1}, {8,5,3},
+{15,0,0}, {10,4,1}, {21,0,0}, {5,3,2}, {7,4,2}, {52,0,0},
+{71,0,0}, {14,0,0}, {27,0,0}, {10,9,7}, {53,0,0}, {3,0,0},
+{6,3,2}, {1,0,0}, {15,0,0}, {62,0,0}, {9,0,0}, {6,5,2},
+{8,6,5}, {31,0,0}, {5,3,2}, {18,0,0}, {27,0,0}, {7,6,3},
+{10,8,7}, {9,8,3}, {37,0,0}, {6,0,0}, {15,3,2}, {34,0,0},
+{11,0,0}, {6,5,2}, {1,0,0}, {8,5,2}, {13,0,0}, {6,0,0},
+{11,3,2}, {8,0,0}, {31,0,0}, {4,2,1}, {3,0,0}, {7,6,1},
+{81,0,0}, {56,0,0}, {9,8,7}, {24,0,0}, {11,0,0}, {7,6,5},
+{6,5,2}, {6,5,2}, {8,7,6}, {9,0,0}, {7,2,1}, {15,0,0},
+{87,0,0}, {8,3,2}, {3,0,0}, {9,4,2}, {9,0,0}, {34,0,0},
+{5,3,2}, {14,0,0}, {55,0,0}, {8,7,1}, {27,0,0}, {9,5,2},
+{10,9,5}, {43,0,0}, {9,3,1}, {6,0,0}, {7,0,0}, {11,10,8},
+{105,0,0}, {6,5,2}, {73,0,0}, {23,0,0}, {7,3,1}, {45,0,0},
+{11,0,0}, {8,4,1}, {7,0,0}, {8,6,2}, {5,4,2}, {33,0,0},
+{9,8,3}, {32,0,0}, {10,7,3}, {10,9,4}, {113,0,0}, {10,4,1},
+{8,7,6}, {26,0,0}, {9,4,2}, {74,0,0}, {31,0,0}, {9,6,1},
+{5,0,0}, {7,4,1}, {73,0,0}, {36,0,0}, {8,5,3}, {70,0,0},
+{95,0,0}, {8,5,1}, {111,0,0}, {6,4,1}, {11,2,1}, {82,0,0},
+{15,14,10}, {35,0,0}, {103,0,0}, {7,4,2}, {15,0,0}, {46,0,0},
+{7,2,1}, {52,0,0}, {10,5,2}, {12,0,0}, {71,0,0}, {10,6,2},
+{15,0,0}, {7,6,4}, {9,8,4}, {93,0,0}, {9,6,2}, {42,0,0},
+{47,0,0}, {8,6,3}, {25,0,0}, {7,6,1}, {53,0,0}, {58,0,0},
+{9,3,2}, {23,0,0}, {67,0,0}, {11,10,9}, {63,0,0}, {12,6,3},
+{5,0,0}, {5,0,0}, {9,5,2}, {93,0,0}, {35,0,0}, {12,7,5},
+{53,0,0}, {10,7,5}, {69,0,0}, {71,0,0}, {11,10,1}, {21,0,0},
+{5,3,2}, {12,11,5}, {37,0,0}, {11,6,1}, {33,0,0}, {48,0,0},
+{7,3,2}, {5,0,0}, {11,8,4}, {11,6,4}, {5,0,0}, {9,5,2},
+{41,0,0}, {1,0,0}, {11,2,1}, {102,0,0}, {7,3,1}, {8,4,2},
+{15,0,0}, {10,6,4}, {93,0,0}, {7,5,3}, {9,7,4}, {79,0,0},
+{15,0,0}, {10,9,1}, {63,0,0}, {7,4,2}, {45,0,0}, {36,0,0},
+{4,3,1}, {31,0,0}, {67,0,0}, {10,3,1}, {51,0,0}, {10,5,2},
+{10,3,1}, {34,0,0}, {8,3,1}, {50,0,0}, {99,0,0}, {10,6,2},
+{89,0,0}, {2,0,0}, {5,2,1}, {10,7,2}, {7,4,1}, {55,0,0},
+{4,3,1}, {16,10,7}, {45,0,0}, {10,8,6}, {125,0,0}, {75,0,0},
+{7,2,1}, {22,0,0}, {63,0,0}, {11,10,3}, {103,0,0}, {6,5,2},
+{53,0,0}, {34,0,0}, {13,11,6}, {69,0,0}, {99,0,0}, {6,5,1},
+{10,9,7}, {11,10,2}, {57,0,0}, {68,0,0}, {5,3,2}, {7,4,1},
+{63,0,0}, {8,5,3}, {9,0,0}, {9,6,5}, {29,0,0}, {21,0,0},
+{7,3,2}, {91,0,0}, {139,0,0}, {8,3,2}, {111,0,0}, {8,7,2},
+{8,6,5}, {16,0,0}, {8,7,5}, {41,0,0}, {43,0,0}, {10,8,5},
+{47,0,0}, {5,2,1}, {81,0,0}, {90,0,0}, {12,3,2}, {6,0,0},
+{83,0,0}, {8,7,1}, {159,0,0}, {10,9,5}, {9,0,0}, {28,0,0},
+{13,10,6}, {7,0,0}, {135,0,0}, {11,6,5}, {25,0,0}, {12,7,6},
+{7,6,2}, {26,0,0}, {5,3,2}, {152,0,0}, {171,0,0}, {9,8,5},
+{65,0,0}, {13,8,2}, {141,0,0}, {71,0,0}, {5,3,2}, {87,0,0},
+{10,4,3}, {12,10,3}, {147,0,0}, {10,7,6}, {13,0,0}, {102,0,0},
+{9,5,2}, {107,0,0}, {199,0,0}, {15,5,4}, {7,0,0}, {5,4,2},
+{149,0,0}, {25,0,0}, {9,7,2}, {12,0,0}, {63,0,0}, {11,6,5},
+{105,0,0}, {10,8,7}, {14,6,1}, {120,0,0}, {13,4,3}, {33,0,0},
+{12,11,5}, {12,9,5}, {165,0,0}, {6,2,1}, {65,0,0}, {49,0,0},
+{4,3,1}, {7,0,0}, {7,5,2}, {10,6,1}, {81,0,0}, {7,6,4},
+{105,0,0}, {73,0,0}, {11,6,4}, {134,0,0}, {47,0,0}, {16,10,1},
+{6,5,4}, {15,6,4}, {8,6,1}, {38,0,0}, {18,9,6}, {16,0,0},
+{203,0,0}, {12,5,2}, {19,0,0}, {7,6,1}, {73,0,0}, {93,0,0},
+{19,18,13}, {31,0,0}, {14,11,6}, {11,6,1}, {27,0,0}, {9,5,2},
+{9,0,0}, {1,0,0}, {11,3,2}, {200,0,0}, {191,0,0}, {9,8,4},
+{9,0,0}, {16,15,7}, {121,0,0}, {104,0,0}, {15,9,6}, {138,0,0},
+{9,6,5}, {9,6,4}, {105,0,0}, {17,16,6}, {81,0,0}, {94,0,0},
+{4,3,1}, {83,0,0}, {219,0,0}, {11,6,3}, {7,0,0}, {10,5,3},
+{17,0,0}, {76,0,0}, {16,5,2}, {78,0,0}, {155,0,0}, {11,6,5},
+{27,0,0}, {5,4,2}, {8,5,4}, {3,0,0}, {15,14,6}, {156,0,0},
+{23,0,0}, {13,6,3}, {9,0,0}, {8,7,3}, {69,0,0}, {10,0,0},
+{8,5,2}, {26,0,0}, {67,0,0}, {14,7,4}, {21,0,0}, {12,10,2},
+{33,0,0}, {79,0,0}, {15,11,2}, {32,0,0}, {39,0,0}, {13,6,2},
+{167,0,0}, {6,4,1}, {97,0,0}, {47,0,0}, {11,6,2}, {42,0,0},
+{10,7,3}, {10,5,4}, {1,0,0}, {4,3,2}, {161,0,0}, {8,6,2},
+{7,5,3}, {94,0,0}, {195,0,0}, {10,5,4}, {9,0,0}, {13,10,4},
+{8,6,1}, {16,0,0}, {8,3,1}, {122,0,0}, {8,2,1}, {13,7,4},
+{10,5,3}, {16,4,3}, {193,0,0}, {135,0,0}, {19,16,9}, {39,0,0},
+{10,8,7}, {10,9,4}, {153,0,0}, {7,6,5}, {73,0,0}, {34,0,0},
+{11,9,6}, {71,0,0}, {11,4,2}, {14,7,3}, {163,0,0}, {11,6,1},
+{153,0,0}, {28,0,0}, {15,7,6}, {77,0,0}, {67,0,0}, {10,5,2},
+{12,8,1}, {10,6,4}, {13,0,0}, {146,0,0}, {13,4,3}, {25,0,0},
+{23,22,16}, {12,9,7}, {237,0,0}, {13,7,6}, {85,0,0}, {130,0,0},
+{14,13,3}, {88,0,0}, {7,5,2}, {11,6,1}, {35,0,0}, {10,4,3},
+{93,0,0}, {9,6,4}, {13,6,3}, {86,0,0}, {19,0,0}, {9,2,1},
+{273,0,0}, {14,12,9}, {7,6,1}, {30,0,0}, {9,5,2}, {201,0,0},
+{215,0,0}, {6,4,3}, {105,0,0}, {10,7,5}, {165,0,0}, {105,0,0},
+{19,13,6}, {31,0,0}, {127,0,0}, {10,4,2}, {81,0,0}, {19,10,4},
+{45,0,0}, {211,0,0}, {19,10,3}, {200,0,0}, {295,0,0}, {9,8,5},
+{9,0,0}, {12,6,5}, {297,0,0}, {68,0,0}, {11,6,5}, {133,0,0},
+{251,0,0}, {13,8,4}, {223,0,0}, {6,5,2}, {7,4,2}, {307,0,0},
+{9,2,1}, {101,0,0}, {39,0,0}, {14,10,4}, {217,0,0}, {14,9,1},
+{6,5,1}, {16,0,0}, {14,3,2}, {11,0,0}, {119,0,0}, {11,3,2},
+{11,6,5}, {11,8,4}, {249,0,0}, {5,0,0}, {13,3,1}, {37,0,0},
+{3,0,0}, {14,0,0}, {93,0,0}, {10,8,7}, {33,0,0}, {88,0,0},
+{7,5,4}, {38,0,0}, {55,0,0}, {15,4,2}, {11,0,0}, {12,11,4},
+{21,0,0}, {107,0,0}, {11,9,8}, {33,0,0}, {10,7,2}, {18,7,3},
+{147,0,0}, {5,4,2}, {153,0,0}, {15,0,0}, {11,6,5}, {28,0,0},
+{11,7,4}, {6,3,1}, {31,0,0}, {8,4,3}, {15,5,3}, {66,0,0},
+{23,16,9}, {11,9,3}, {171,0,0}, {11,6,1}, {209,0,0}, {4,3,1},
+{197,0,0}, {13,0,0}, {19,14,6}, {14,0,0}, {79,0,0}, {13,6,2},
+{299,0,0}, {15,8,2}, {169,0,0}, {177,0,0}, {23,10,2}, {267,0,0},
+{215,0,0}, {15,10,1}, {75,0,0}, {16,4,2}, {37,0,0}, {12,7,1},
+{8,3,2}, {17,0,0}, {12,11,8}, {15,8,5}, {15,0,0}, {4,3,1},
+{13,12,4}, {92,0,0}, {5,4,3}, {41,0,0}, {23,0,0}, {7,4,1},
+{183,0,0}, {16,7,1}, {165,0,0}, {150,0,0}, {9,6,4}, {9,0,0},
+{231,0,0}, {16,10,4}, {207,0,0}, {9,6,5}, {5,0,0}, {180,0,0},
+{4,3,2}, {58,0,0}, {147,0,0}, {8,6,2}, {343,0,0}, {8,7,2},
+{11,6,1}, {44,0,0}, {13,8,6}, {5,0,0}, {347,0,0}, {18,16,8},
+{135,0,0}, {9,8,3}, {85,0,0}, {90,0,0}, {13,11,1}, {258,0,0},
+{351,0,0}, {10,6,4}, {19,0,0}, {7,6,1}, {309,0,0}, {18,0,0},
+{13,10,3}, {158,0,0}, {19,0,0}, {12,10,1}, {45,0,0}, {7,6,1},
+{233,0,0}, {98,0,0}, {11,6,5}, {3,0,0}, {83,0,0}, {16,14,9},
+{6,5,3}, {9,7,4}, {22,19,9}, {168,0,0}, {19,17,4}, {120,0,0},
+{14,5,2}, {17,15,6}, {7,0,0}, {10,8,6}, {185,0,0}, {93,0,0},
+{15,14,7}, {29,0,0}, {375,0,0}, {10,8,3}, {13,0,0}, {17,16,2},
+{329,0,0}, {68,0,0}, {13,9,6}, {92,0,0}, {12,10,3}, {7,6,3},
+{17,10,3}, {5,2,1}, {9,6,1}, {30,0,0}, {9,7,3}, {253,0,0},
+{143,0,0}, {7,4,1}, {9,4,1}, {12,10,4}, {53,0,0}, {25,0,0},
+{9,7,1}, {217,0,0}, {15,13,9}, {14,9,2}, {75,0,0}, {8,7,2},
+{21,0,0}, {7,0,0}, {14,3,2}, {15,0,0}, {159,0,0}, {12,10,8},
+{29,0,0}, {10,3,1}, {21,0,0}, {333,0,0}, {11,8,2}, {52,0,0},
+{119,0,0}, {16,9,7}, {123,0,0}, {15,11,2}, {17,0,0}, {9,0,0},
+{11,6,4}, {38,0,0}, {255,0,0}, {12,10,7}, {189,0,0}, {4,3,1},
+{17,10,7}, {49,0,0}, {13,5,2}, {149,0,0}, {15,0,0}, {14,7,5},
+{10,9,2}, {8,6,5}, {61,0,0}, {54,0,0}, {11,5,1}, {144,0,0},
+{47,0,0}, {11,10,7}, {105,0,0}, {2,0,0}, {105,0,0}, {136,0,0},
+{11,4,1}, {253,0,0}, {111,0,0}, {13,10,5}, {159,0,0}, {10,7,1},
+{7,5,3}, {29,0,0}, {19,10,3}, {119,0,0}, {207,0,0}, {17,15,4},
+{35,0,0}, {14,0,0}, {349,0,0}, {6,3,2}, {21,10,6}, {1,0,0},
+{75,0,0}, {9,5,2}, {145,0,0}, {11,7,6}, {301,0,0}, {378,0,0},
+{13,3,1}, {352,0,0}, {12,7,4}, {12,8,1}, {149,0,0}, {6,5,4},
+{12,9,8}, {11,0,0}, {15,7,5}, {78,0,0}, {99,0,0}, {17,16,12},
+{173,0,0}, {8,7,1}, {13,9,8}, {147,0,0}, {19,18,10}, {127,0,0},
+{183,0,0}, {12,4,1}, {31,0,0}, {11,8,6}, {173,0,0}, {12,0,0},
+{7,5,3}, {113,0,0}, {207,0,0}, {18,15,5}, {1,0,0}, {13,7,6},
+{21,0,0}, {35,0,0}, {12,7,2}, {117,0,0}, {123,0,0}, {12,10,2},
+{143,0,0}, {14,4,1}, {15,9,7}, {204,0,0}, {7,5,1}, {91,0,0},
+{4,2,1}, {8,6,3}, {183,0,0}, {12,10,7}, {77,0,0}, {36,0,0},
+{14,9,6}, {221,0,0}, {7,6,5}, {16,14,13}, {31,0,0}, {16,15,7},
+{365,0,0}, {403,0,0}, {10,3,2}, {11,4,3}, {31,0,0}, {10,9,4},
+{177,0,0}, {16,6,1}, {22,6,5}, {417,0,0}, {15,13,12}, {217,0,0},
+{207,0,0}, {7,5,4}, {10,7,1}, {11,6,1}, {45,0,0}, {24,0,0},
+{12,11,9}, {77,0,0}, {21,20,13}, {9,6,5}, {189,0,0}, {8,3,2},
+{13,12,10}, {260,0,0}, {16,9,7}, {168,0,0}, {131,0,0}, {7,6,3},
+{305,0,0}, {10,9,6}, {13,9,4}, {143,0,0}, {12,9,3}, {18,0,0},
+{15,8,5}, {20,9,6}, {103,0,0}, {15,4,2}, {201,0,0}, {36,0,0},
+{9,5,2}, {31,0,0}, {11,7,2}, {6,2,1}, {7,0,0}, {13,6,4},
+{9,8,7}, {19,0,0}, {17,10,6}, {15,0,0}, {9,3,1}, {178,0,0},
+{8,7,6}, {12,6,5}, {177,0,0}, {230,0,0}, {24,9,3}, {222,0,0},
+{3,0,0}, {16,13,12}, {121,0,0}, {10,4,2}, {161,0,0}, {39,0,0},
+{17,15,13}, {62,0,0}, {223,0,0}, {15,12,2}, {65,0,0}, {12,6,3},
+{101,0,0}, {59,0,0}, {5,4,3}, {17,0,0}, {5,3,2}, {13,8,3},
+{10,9,7}, {12,8,2}, {5,4,3}, {75,0,0}, {19,17,8}, {55,0,0},
+{99,0,0}, {10,7,4}, {115,0,0}, {9,8,6}, {385,0,0}, {186,0,0},
+{15,6,3}, {9,4,1}, {12,10,5}, {10,8,1}, {135,0,0}, {5,2,1},
+{317,0,0}, {7,0,0}, {19,6,1}, {294,0,0}, {35,0,0}, {13,12,6},
+{119,0,0}, {98,0,0}, {93,0,0}, {68,0,0}, {21,15,3}, {108,0,0},
+{75,0,0}, {12,6,5}, {411,0,0}, {12,7,2}, {13,7,2}, {21,0,0},
+{15,10,8}, {412,0,0}, {439,0,0}, {10,7,6}, {41,0,0}, {13,9,6},
+{8,5,2}, {10,0,0}, {15,7,2}, {141,0,0}, {159,0,0}, {13,12,10},
+{291,0,0}, {10,9,1}, {105,0,0}, {24,0,0}, {11,2,1}, {198,0,0},
+{27,0,0}, {6,3,1}, {439,0,0}, {10,3,1}, {49,0,0}, {168,0,0},
+{13,11,9}, {463,0,0}, {10,9,3}, {13,9,8}, {15,8,3}, {18,16,8},
+{15,14,11}, {7,0,0}, {19,9,8}, {12,6,3}, {7,4,3}, {15,14,5},
+{8,6,3}, {10,9,7}, {361,0,0}, {230,0,0}, {15,9,6}, {24,0,0},
+{407,0,0}, {16,7,2}, {189,0,0}, {62,0,0}, {189,0,0}, {112,0,0},
+{22,21,10}, {91,0,0}, {79,0,0}, {12,10,5}, {23,0,0}, {7,6,1},
+{57,0,0}, {139,0,0}, {24,15,6}, {14,0,0}, {83,0,0}, {16,9,1},
+{35,0,0}, {9,7,4}, {117,0,0}, {65,0,0}, {21,9,6}, {21,0,0},
+{195,0,0}, {23,11,10}, {327,0,0}, {17,14,3}, {417,0,0}, {13,0,0},
+{15,8,6}, {107,0,0}, {19,10,6}, {18,15,3}, {59,0,0}, {12,10,4},
+{9,7,5}, {283,0,0}, {13,9,6}, {62,0,0}, {427,0,0}, {14,7,3},
+{8,7,4}, {15,8,3}, {105,0,0}, {27,0,0}, {7,3,1}, {103,0,0},
+{551,0,0}, {10,6,1}, {6,4,1}, {11,6,4}, {129,0,0}, {9,0,0},
+{9,4,2}, {277,0,0}, {31,0,0}, {13,12,5}, {141,0,0}, {12,7,3},
+{357,0,0}, {7,2,1}, {11,9,7}, {227,0,0}, {131,0,0}, {7,6,3},
+{23,0,0}, {20,17,3}, {13,4,1}, {90,0,0}, {15,3,2}, {241,0,0},
+{75,0,0}, {13,6,1}, {307,0,0}, {8,7,3}, {245,0,0}, {66,0,0},
+{15,11,2}, {365,0,0}, {18,16,11}, {11,10,1}, {19,0,0}, {8,6,1},
+{189,0,0}, {133,0,0}, {12,7,2}, {114,0,0}, {27,0,0}, {6,5,1},
+{15,5,2}, {17,14,5}, {133,0,0}, {476,0,0}, {11,9,3}, {16,0,0},
+{375,0,0}, {15,8,6}, {25,0,0}, {17,11,6}, {77,0,0}, {87,0,0},
+{5,3,2}, {134,0,0}, {171,0,0}, {13,8,4}, {75,0,0}, {8,3,1},
+{233,0,0}, {196,0,0}, {9,8,7}, {173,0,0}, {15,14,12}, {13,6,5},
+{281,0,0}, {9,8,2}, {405,0,0}, {114,0,0}, {15,9,6}, {171,0,0},
+{287,0,0}, {8,4,2}, {43,0,0}, {4,2,1}, {513,0,0}, {273,0,0},
+{11,10,6}, {118,0,0}, {243,0,0}, {14,7,1}, {203,0,0}, {9,5,2},
+{257,0,0}, {302,0,0}, {27,25,9}, {393,0,0}, {91,0,0}, {12,10,6},
+{413,0,0}, {15,14,9}, {18,16,1}, {255,0,0}, {12,9,7}, {234,0,0},
+{167,0,0}, {16,13,10}, {27,0,0}, {15,6,2}, {433,0,0}, {105,0,0},
+{25,10,2}, {151,0,0}, {427,0,0}, {13,9,8}, {49,0,0}, {10,6,4},
+{153,0,0}, {4,0,0}, {17,7,5}, {54,0,0}, {203,0,0}, {16,15,1},
+{16,14,7}, {13,6,1}, {25,0,0}, {14,0,0}, {15,5,3}, {187,0,0},
+{15,13,10}, {13,10,5}, {97,0,0}, {11,10,9}, {19,10,4}, {589,0,0},
+{31,30,2}, {289,0,0}, {9,6,4}, {11,8,6}, {21,0,0}, {7,4,1},
+{7,4,2}, {77,0,0}, {5,3,2}, {119,0,0}, {7,0,0}, {9,5,2},
+{345,0,0}, {17,10,8}, {333,0,0}, {17,0,0}, {16,9,7}, {168,0,0},
+{15,13,4}, {11,10,1}, {217,0,0}, {18,11,10}, {189,0,0}, {216,0,0},
+{12,7,5}, {229,0,0}, {231,0,0}, {12,9,3}, {223,0,0}, {10,9,1},
+{153,0,0}, {470,0,0}, {23,16,6}, {99,0,0}, {10,4,3}, {9,8,4},
+{12,10,1}, {14,9,6}, {201,0,0}, {38,0,0}, {15,14,2}, {198,0,0},
+{399,0,0}, {14,11,5}, {75,0,0}, {11,10,1}, {77,0,0}, {16,12,8},
+{20,17,15}, {326,0,0}, {39,0,0}, {14,12,9}, {495,0,0}, {8,3,2},
+{333,0,0}, {476,0,0}, {15,14,2}, {164,0,0}, {19,0,0}, {12,4,2},
+{8,6,3}, {13,12,3}, {12,11,5}, {129,0,0}, {12,9,3}, {52,0,0},
+{10,8,3}, {17,16,2}, {337,0,0}, {12,9,3}, {397,0,0}, {277,0,0},
+{21,11,3}, {73,0,0}, {11,6,1}, {7,5,4}, {95,0,0}, {11,3,2},
+{617,0,0}, {392,0,0}, {8,3,2}, {75,0,0}, {315,0,0}, {15,6,4},
+{125,0,0}, {6,5,2}, {15,9,7}, {348,0,0}, {15,6,1}, {553,0,0},
+{6,3,2}, {10,9,7}, {553,0,0}, {14,10,4}, {237,0,0}, {39,0,0},
+{17,14,6}, {371,0,0}, {255,0,0}, {8,4,1}, {131,0,0}, {14,6,1},
+{117,0,0}, {98,0,0}, {5,3,2}, {56,0,0}, {655,0,0}, {9,5,2},
+{239,0,0}, {11,8,4}, {1,0,0}, {134,0,0}, {15,9,5}, {88,0,0},
+{10,5,3}, {10,9,4}, {181,0,0}, {15,11,2}, {609,0,0}, {52,0,0},
+{19,18,10}, {100,0,0}, {7,6,3}, {15,8,2}, {183,0,0}, {18,7,6},
+{10,9,2}, {130,0,0}, {11,5,1}, {12,0,0}, {219,0,0}, {13,10,7},
+{11,0,0}, {19,9,4}, {129,0,0}, {3,0,0}, {17,15,5}, {300,0,0},
+{17,13,9}, {14,6,5}, {97,0,0}, {13,8,3}, {601,0,0}, {55,0,0},
+{8,3,1}, {92,0,0}, {127,0,0}, {12,11,2}, {81,0,0}, {15,10,8},
+{13,2,1}, {47,0,0}, {14,13,6}, {194,0,0}, {383,0,0}, {25,14,11},
+{125,0,0}, {20,19,16}, {429,0,0}, {282,0,0}, {10,9,6}, {342,0,0},
+{5,3,2}, {15,9,4}, {33,0,0}, {9,4,2}, {49,0,0}, {15,0,0},
+{11,6,2}, {28,0,0}, {103,0,0}, {18,17,8}, {27,0,0}, {11,6,5},
+{33,0,0}, {17,0,0}, {11,10,6}, {387,0,0}, {363,0,0}, {15,10,9},
+{83,0,0}, {7,6,4}, {357,0,0}, {13,12,4}, {14,13,7}, {322,0,0},
+{395,0,0}, {16,5,1}, {595,0,0}, {13,10,3}, {421,0,0}, {195,0,0},
+{11,3,2}, {13,0,0}, {16,12,3}, {14,3,1}, {315,0,0}, {26,10,5},
+{297,0,0}, {52,0,0}, {9,4,2}, {314,0,0}, {243,0,0}, {16,14,9},
+{185,0,0}, {12,5,3}, {13,5,2}, {575,0,0}, {12,9,3}, {39,0,0},
+{311,0,0}, {13,5,2}, {181,0,0}, {20,18,14}, {49,0,0}, {25,0,0},
+{11,4,1}, {77,0,0}, {17,11,10}, {15,14,8}, {21,0,0}, {17,10,5},
+{69,0,0}, {49,0,0}, {11,10,2}, {32,0,0}, {411,0,0}, {21,16,3},
+{11,7,4}, {22,10,3}, {85,0,0}, {140,0,0}, {9,8,6}, {252,0,0},
+{279,0,0}, {9,5,2}, {307,0,0}, {17,10,4}, {13,12,9}, {94,0,0},
+{13,11,4}, {49,0,0}, {17,11,10}, {16,12,5}, {25,0,0}, {6,5,2},
+{12,5,1}, {80,0,0}, {8,3,2}, {246,0,0}, {11,5,2}, {11,10,2},
+{599,0,0}, {18,12,10}, {189,0,0}, {278,0,0}, {10,9,3}, {399,0,0},
+{299,0,0}, {13,10,6}, {277,0,0}, {13,10,6}, {69,0,0}, {220,0,0},
+{13,10,3}, {229,0,0}, {18,11,10}, {16,15,1}, {27,0,0}, {18,9,3},
+{473,0,0}, {373,0,0}, {18,17,7}, {60,0,0}, {207,0,0}, {13,9,8},
+{22,20,13}, {25,18,7}, {225,0,0}, {404,0,0}, {21,6,2}, {46,0,0},
+{6,2,1}, {17,12,6}, {75,0,0}, {4,2,1}, {365,0,0}, {445,0,0},
+{11,7,1}, {44,0,0}, {10,8,5}, {12,5,2}, {63,0,0}, {17,4,2},
+{189,0,0}, {557,0,0}, {19,12,2}, {252,0,0}, {99,0,0}, {10,8,5},
+{65,0,0}, {14,9,3}, {9,0,0}, {119,0,0}, {8,5,2}, {339,0,0},
+{95,0,0}, {12,9,7}, {7,0,0}, {13,10,2}, {77,0,0}, {127,0,0},
+{21,10,7}, {319,0,0}, {667,0,0}, {17,10,3}, {501,0,0}, {18,12,9},
+{9,8,5}, {17,0,0}, {20,9,2}, {341,0,0}, {731,0,0}, {7,6,5},
+{647,0,0}, {10,4,2}, {121,0,0}, {20,0,0}, {21,19,13}, {574,0,0},
+{399,0,0}, {15,10,7}, {85,0,0}, {16,8,3}, {169,0,0}, {15,0,0},
+{12,7,5}, {568,0,0}, {10,7,1}, {18,2,1}, {3,0,0}, {14,3,2},
+{13,7,3}, {643,0,0}, {14,11,1}, {548,0,0}, {783,0,0}, {14,11,1},
+{317,0,0}, {7,6,4}, {153,0,0}, {87,0,0}, {15,13,1}, {231,0,0},
+{11,5,3}, {18,13,7}, {771,0,0}, {30,20,11}, {15,6,3}, {103,0,0},
+{13,4,3}, {182,0,0}, {211,0,0}, {17,6,1}, {27,0,0}, {13,12,10},
+{15,14,10}, {17,0,0}, {13,11,5}, {69,0,0}, {11,5,1}, {18,6,1},
+{603,0,0}, {10,4,2}, {741,0,0}, {668,0,0}, {17,15,3}, {147,0,0},
+{227,0,0}, {15,10,9}, {37,0,0}, {16,6,1}, {173,0,0}, {427,0,0},
+{7,5,1}, {287,0,0}, {231,0,0}, {20,15,10}, {18,9,1}, {14,12,5},
+{16,5,1}, {310,0,0}, {18,13,1}, {434,0,0}, {579,0,0}, {18,13,8},
+{45,0,0}, {12,8,3}, {16,9,5}, {53,0,0}, {19,15,10}, {16,0,0},
+{17,6,5}, {17,10,1}, {37,0,0}, {17,10,9}, {21,13,7}, {99,0,0},
+{17,9,6}, {176,0,0}, {271,0,0}, {18,17,13}, {459,0,0}, {21,17,10},
+{6,5,2}, {202,0,0}, {5,4,3}, {90,0,0}, {755,0,0}, {15,7,2},
+{363,0,0}, {8,4,2}, {129,0,0}, {20,0,0}, {11,6,2}, {135,0,0},
+{15,8,7}, {14,13,2}, {10,4,3}, {24,13,10}, {19,14,11}, {31,0,0},
+{15,8,6}, {758,0,0}, {16,11,5}, {16,5,1}, {359,0,0}, {23,18,17},
+{501,0,0}, {29,0,0}, {15,6,3}, {201,0,0}, {459,0,0}, {12,10,7},
+{225,0,0}, {22,17,13}, {24,22,5}, {161,0,0}, {14,11,3}, {52,0,0},
+{19,17,6}, {21,14,12}, {93,0,0}, {13,10,3}, {201,0,0}, {178,0,0},
+{15,12,5}, {250,0,0}, {7,6,4}, {17,13,6}, {221,0,0}, {13,11,8},
+{17,14,9}, {113,0,0}, {17,14,10}, {300,0,0}, {39,0,0}, {18,13,3},
+{261,0,0}, {15,14,8}, {753,0,0}, {8,4,3}, {11,10,5}, {94,0,0},
+{15,13,1}, {10,4,2}, {14,11,10}, {8,6,2}, {461,0,0}, {418,0,0},
+{19,14,6}, {403,0,0}, {267,0,0}, {10,9,2}, {259,0,0}, {20,4,3},
+{869,0,0}, {173,0,0}, {19,18,2}, {369,0,0}, {255,0,0}, {22,12,9},
+{567,0,0}, {20,11,7}, {457,0,0}, {482,0,0}, {6,3,2}, {775,0,0},
+{19,17,6}, {6,4,3}, {99,0,0}, {15,14,8}, {6,5,2}, {165,0,0},
+{8,3,2}, {13,12,10}, {25,21,17}, {17,14,9}, {105,0,0}, {17,15,14},
+{10,3,2}, {250,0,0}, {25,6,5}, {327,0,0}, {279,0,0}, {13,6,5},
+{371,0,0}, {15,9,4}, {117,0,0}, {486,0,0}, {10,9,3}, {217,0,0},
+{635,0,0}, {30,27,17}, {457,0,0}, {16,6,2}, {57,0,0}, {439,0,0},
+{23,21,6}, {214,0,0}, {20,13,6}, {20,16,1}, {819,0,0}, {15,11,8},
+{593,0,0}, {190,0,0}, {17,14,3}, {114,0,0}, {21,18,3}, {10,5,2},
+{12,9,5}, {8,6,3}, {69,0,0}, {312,0,0}, {22,5,2}, {502,0,0},
+{843,0,0}, {15,10,3}, {747,0,0}, {6,5,2}, {101,0,0}, {123,0,0},
+{19,16,9}, {521,0,0}, {171,0,0}, {16,7,2}, {12,6,5}, {22,21,20},
+{545,0,0}, {163,0,0}, {23,18,1}, {479,0,0}, {495,0,0}, {13,6,5},
+{11,0,0}, {17,5,2}, {18,8,1}, {684,0,0}, {7,5,1}, {9,0,0},
+{18,11,3}, {22,20,13}, {273,0,0}, {4,3,2}, {381,0,0}, {51,0,0},
+{18,13,7}, {518,0,0}, {9,5,1}, {14,12,3}, {243,0,0}, {21,17,2},
+{53,0,0}, {836,0,0}, {21,10,2}, {66,0,0}, {12,10,7}, {13,9,8},
+{339,0,0}, {16,11,5}, {901,0,0}, {180,0,0}, {16,13,3}, {49,0,0},
+{6,3,2}, {15,4,1}, {16,13,6}, {18,15,12}, {885,0,0}, {39,0,0},
+{11,9,4}, {688,0,0}, {16,15,7}, {13,10,6}, {13,0,0}, {25,23,12},
+{149,0,0}, {260,0,0}, {11,9,1}, {53,0,0}, {11,0,0}, {12,4,2},
+{9,7,5}, {11,8,1}, {121,0,0}, {261,0,0}, {10,5,2}, {199,0,0},
+{20,4,3}, {17,9,2}, {13,9,4}, {12,8,7}, {253,0,0}, {174,0,0},
+{15,4,2}, {370,0,0}, {9,6,1}, {16,10,9}, {669,0,0}, {20,10,9},
+{833,0,0}, {353,0,0}, {17,13,2}, {29,0,0}, {371,0,0}, {9,8,5},
+{8,7,1}, {19,8,7}, {12,11,10}, {873,0,0}, {26,11,2}, {12,9,1},
+{10,7,2}, {13,6,1}, {235,0,0}, {26,24,19}, {733,0,0}, {778,0,0},
+{12,11,1}, {344,0,0}, {931,0,0}, {16,6,4}, {945,0,0}, {21,19,14},
+{18,13,11}, {67,0,0}, {20,15,10}, {462,0,0}, {14,5,1}, {10,9,6},
+{18,11,10}, {16,9,7}, {477,0,0}, {105,0,0}, {11,3,2}, {468,0,0},
+{23,16,15}, {16,15,6}, {327,0,0}, {23,10,4}, {357,0,0}, {25,0,0},
+{17,16,7}, {31,0,0}, {7,5,2}, {16,7,6}, {277,0,0}, {14,13,6},
+{413,0,0}, {103,0,0}, {15,10,1}, {231,0,0}, {747,0,0}, {5,2,1},
+{113,0,0}, {20,10,7}, {15,9,6}, {11,0,0}, {27,22,18}, {91,0,0},
+{51,0,0}, {18,13,12}, {603,0,0}, {10,7,3}, {9,0,0}, {121,0,0},
+{15,14,6}, {17,0,0}, {16,11,2}, {23,15,6}, {279,0,0}, {16,12,6},
+{89,0,0}, {371,0,0}, {17,15,2}, {771,0,0}, {99,0,0}, {7,6,3},
+{21,0,0}, {10,7,5}, {801,0,0}, {26,0,0}, {25,19,14}, {175,0,0},
+{10,7,2}, {20,5,4}, {12,11,1}, {22,5,1}, {165,0,0}, {841,0,0},
+{25,19,17}, {238,0,0}, {11,8,6}, {22,21,4}, {33,0,0}, {8,7,6},
+{14,9,2}, {113,0,0}, {13,11,5}, {311,0,0}, {891,0,0}, {20,16,14},
+{555,0,0}, {23,14,8}, {133,0,0}, {546,0,0}, {6,3,2}, {103,0,0},
+{15,0,0}, {10,7,3}, {307,0,0}, {14,10,1}, {15,12,2}, {367,0,0},
+{13,10,6}, {169,0,0}, {22,21,11}, {12,10,8}, {441,0,0}, {17,12,7},
+{917,0,0}, {205,0,0}, {26,23,13}, {54,0,0}, {459,0,0}, {17,15,4},
+{19,15,4}, {5,4,2}, {9,7,6}, {42,0,0}, {21,15,7}, {330,0,0},
+{20,7,3}, {20,7,2}, {81,0,0}, {19,14,1}, {349,0,0}, {165,0,0},
+{40,35,9}, {274,0,0}, {475,0,0}, {11,10,3}, {93,0,0}, {12,7,4},
+{13,12,2}, {386,0,0}, {7,6,2}, {881,0,0}, {143,0,0}, {9,8,4},
+{71,0,0}, {19,18,3}, {16,11,6}, {155,0,0}, {7,2,1}, {735,0,0},
+{16,8,7}, {9,7,4}, {45,0,0}, {7,6,4}, {12,11,3}, {3,0,0},
 {19,14,13}
 };
@@ -870 +870 @@
 
    for (k3 = 3; k3 < n; k3++)
-      for (k2 = 2; k2 < k3; k2++) 
+      for (k2 = 2; k2 < k3; k2++)
          for (k1 = 1; k1 < k2; k1++)
             if (IterIrredTest(1+GF2X(k1,1)+GF2X(k2,1)+GF2X(k3,1)+GF2X(n,1))) {
@@ -885 +885 @@
    if (n <= 0) Error("SparseIrred: n <= 0");
 
-   if (NTL_OVERFLOW(n, 1, 0)) 
+   if (NTL_OVERFLOW(n, 1, 0))
       Error("overflow in BuildSparseIrred");
 

ntl/src/GF2XTest.c

@@ -7 +7 @@
    int amt;
 
-   wd(int x) { amt = x; } 
+   wd(int x) { amt = x; }
 };
 
@@ -44 +44 @@
       }
 
-      cout << WD(12,n); 
+      cout << WD(12,n);
 
       iter = 0;

ntl/src/GF2XTimeTest.c

@@ -31 +31 @@
    }
 
-   z = z/n;  
+   z = z/n;
 
    return z;
@@ -79 +79 @@
       }
    }
-   
+
 
    n = 16;
@@ -140 +140 @@
    return 0;
 }
-   
 
+

ntl/src/GF2XVec.c

@@ -52 +52 @@
 
    free(v);
-   v = 0; 
+   v = 0;
 }
 
 
-GF2XVec& GF2XVec::operator=(const GF2XVec& a) 
+GF2XVec& GF2XVec::operator=(const GF2XVec& a)
 {
    if (this == &a)
@@ -70 +70 @@
    return *this;
 }
-   
+
 GF2XVec::GF2XVec(const GF2XVec& a)
 {

ntl/src/G_LLL_FP.c

@@ -17 +17 @@
 
 
+
 static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1)
 // x = x - y*MU
@@ -44 +45 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -54 +55 @@
       conv(mu1, MU);
 
-      for (i = 1; i <= n; i++) {
-         mul(T, B(i), mu1);
-         if (k > 0) LeftShift(T, T, k);
-         sub(A(i), A(i), T);
+      if (k > 0) {
+
+         for (i = 1; i <= n; i++) {
+            mul(T, B(i), mu1);
+            LeftShift(T, T, k);
+            sub(A(i), A(i), T);
+         }
+
+      }
+      else {
+
+         for (i = 1; i <= n; i++) {
+            MulSubFrom(A(i), B(i), mu1);
+         }
+
       }
    }
@@ -70 +82 @@
 
 
+
 #define TR_BND (NTL_FDOUBLE_PRECISION/2.0)
 // Just to be safe!!
@@ -120 +133 @@
 
 
-static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1, 
+static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1,
                          double *a, double *b, long *in_a,
                          double& max_a, double max_b, long& in_float)
@@ -186 +199 @@
                in_a[i] = 0;
             }
-         
+
             sub(A(i), A(i), B(i));
          }
@@ -205 +218 @@
                in_a[i] = 0;
             }
-         
+
             add(A(i), A(i), B(i));
          }
@@ -215 +228 @@
 
    double b_bnd = fabs(TR_BND/mu) - 1;
-   if (b_bnd < 0) b_bnd = 0; 
-
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (b_bnd < 0) b_bnd = 0;
+
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -243 +256 @@
             if (in_a[i] && a[i] < TR_BND && a[i] > -TR_BND &&
                 b[i] < b_bnd && b[i] > -b_bnd) {
-   
+
                a[i] -= b[i]*mu;
             }
@@ -251 +264 @@
                   in_a[i] = 0;
                }
-               mul(T, B(i), mu1);
-               sub(A(i), A(i), T);
+               MulSubFrom(A(i), B(i), mu1);
             }
          }
@@ -298 +310 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -348 +360 @@
 {
    sz = min(m, n)/10;
-   if (sz < 2) 
+   if (sz < 2)
       sz = 2;
    else if (sz > 20)
@@ -356 +368 @@
 
    long i;
-   buf = NTL_NEW_OP doubleptr[sz]; 
+   buf = NTL_NEW_OP doubleptr[sz];
    if (!buf) Error("out of memory");
    for (i = 0; i < sz; i++)
@@ -443 +455 @@
    }
 
-   i = 0; 
+   i = 0;
    while (i < sz && bl[i] != 0)
       i++;
@@ -488 +500 @@
          backoff = 2;
       else if (backoff > cache.sz + 2)
-         backoff = cache.sz + 2; 
+         backoff = cache.sz + 2;
 
       long ub = k-(backoff-1);
@@ -495 +507 @@
          double *cptr = mu[i];
          double *sptr = aux[i];
-   
+
          for (j = n; j > i; j--) {
             c = cptr[j];
             s = sptr[j];
-   
+
             a = c*pp[j-1] - s*pp[j];
             b = s*pp[j-1] + c*pp[j];
-   
+
             pp[j-1] = a;
             pp[j] = b;
          }
-   
-         pp[i] = pp[i]/mu[i][i]; 
+
+         pp[i] = pp[i]/mu[i][i];
       }
 
@@ -520 +532 @@
       double *cptr = mu[i];
       double *sptr = aux[i];
-  
+
       for (j = n; j > i; j--) {
          c = cptr[j];
          s = sptr[j];
-  
+
          a = c*p[j-1] - s*p[j];
          b = s*p[j-1] + c*p[j];
-  
+
          p[j-1] = a;
          p[j] = b;
       }
-  
+
       p[i] = p[i]/mu[i][i];
    }
@@ -553 +565 @@
          s = c*t;
       }
-   
+
       p[j-1] = c*a - s*b;
       p[j] = c;
@@ -594 +606 @@
    log_red--;
 
-   
+
    //cerr << "G_LLL_FP: warning--relaxing reduction (" << log_red << ")\n";
 
@@ -618 +630 @@
 
 static
-long ll_G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep, 
-           LLLCheckFct check, double **B1, double **mu, 
+long ll_G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep,
+           LLLCheckFct check, double **B1, double **mu,
            double **aux,
            long m, long init_k, long &quit, GivensCache_FP& cache)
@@ -701 +713 @@
             }
             else {
-               Error( "G_LLL_FP: warning--infinite loop?\n");
+               Error("G_LLL_FP: warning--infinite loop?\n");
             }
          }
 
          Fc1 = 0;
-   
+
          for (j = k-1; j >= 1; j--) {
             t1 = fabs(mu[k][j]);
-            if (t1 > half_plus_fudge) { 
+            if (t1 > half_plus_fudge) {
 
 
                if (!Fc1) {
-                  if (j > trigger_index || 
+                  if (j > trigger_index ||
                       (j == trigger_index && small_trigger)) {
 
@@ -731 +743 @@
                   RowTransformStart(B1[k], in_vec, in_float, n);
                }
-                  
+
 
                mu1 = mu[k][j];
@@ -738 +750 @@
                else
                   mu1 = floor(mu1+0.5);
-   
+
                double *mu_k = mu[k];
                double *mu_j = mu[j];
-   
+
                if (mu1 == 1) {
                   for (i = 1; i <= j-1; i++)
@@ -754 +766 @@
                      mu_k[i] -= mu1*mu_j[i];
                }
-   
+
                mu_k[j] -= mu1;
-   
+
                conv(MU, mu1);
 
@@ -774 +786 @@
       } while (Fc1);
 
-      if (check && (*check)(B(k))) 
+      if (check && (*check)(B(k)))
          quit = 1;
 
@@ -803 +815 @@
       // test G_LLL reduction condition
 
-      if (k > 1 && 
-         sqrt(delta - mu[k][k-1]*mu[k][k-1])*fabs(mu[k-1][k-1]) > 
+      if (k > 1 &&
+         sqrt(delta - mu[k][k-1]*mu[k][k-1])*fabs(mu[k-1][k-1]) >
          fabs(mu[k][k])) {
          // swap rows k, k-1
@@ -840 +852 @@
 
 static
-long G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep, 
+long G_LLL_FP(mat_ZZ& B, mat_ZZ* U, double delta, long deep,
            LLLCheckFct check)
 {
@@ -892 +904 @@
       }
 
-         
+
    GivensCache_FP cache(m, n);
 
@@ -932 +944 @@
 }
 
-         
-
-long G_LLL_FP(mat_ZZ& B, double delta, long deep, LLLCheckFct check, 
+
+
+long G_LLL_FP(mat_ZZ& B, double delta, long deep, LLLCheckFct check,
            long verb)
 {
@@ -945 +957 @@
 }
 
-long G_LLL_FP(mat_ZZ& B, mat_ZZ& U, double delta, long deep, 
+long G_LLL_FP(mat_ZZ& B, mat_ZZ& U, double delta, long deep,
            LLLCheckFct check, long verb)
 {
@@ -987 +999 @@
          for (j = 1; j <= k; j++)
             x = x + Log(j);
-          
+
          x = x * (1/double(k));
 
@@ -1015 +1027 @@
 static vec_double G_BKZThresh;
 
-static 
+static
 void ComputeG_BKZThresh(double *c, long beta)
 {
@@ -1033 +1045 @@
 
 static
-long G_BKZ_FP(mat_ZZ& BB, mat_ZZ* UU, double delta, 
+long G_BKZ_FP(mat_ZZ& BB, mat_ZZ* UU, double delta,
          long beta, long prune, LLLCheckFct check)
 {
 
-   
+
 
    long m = BB.NumRows();
    long n = BB.NumCols();
    long m_orig = m;
-   
+
    long i, j;
    ZZ MU;
@@ -1151 +1163 @@
       }
 
-         
+
    GivensCache_FP cache(m, n);
 
@@ -1182 +1194 @@
       if (beta > m) beta = m;
 
-      if (prune > 0) 
+      if (prune > 0)
          ComputeG_BKZConstant(beta, prune);
 
       z = 0;
       jj = 0;
-   
+
       while (z < m-1) {
          jj++;
          kk = min(jj+beta-1, m);
-   
+
          if (jj == m) {
             jj = 1;
@@ -1209 +1221 @@
          if (prune > 0)
             ComputeG_BKZThresh(&c[jj], kk-jj+1);
-   
+
          cbar = c[jj];
          utildavec[jj] = uvec[jj] = 1;
-   
+
          yvec[jj] = vvec[jj] = 0;
          Deltavec[jj] = 0;
-   
-   
+
+
          s = t = jj;
          deltavec[jj] = 1;
-   
+
          for (i = jj+1; i <= kk+1; i++) {
             ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
@@ -1228 +1240 @@
 
          long enum_cnt = 0;
-   
+
          while (t <= kk) {
-
-            ctilda[t] = ctilda[t+1] + 
+            ctilda[t] = ctilda[t+1] +
                (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*c[t];
 
             ForceToMem(&ctilda[t]); // prevents an infinite loop
-   
+
             if (prune > 0 && t > jj) {
                eta = G_BKZThresh(t-jj);
@@ -1241 +1252 @@
             else
                eta = 0;
-   
+
             if (ctilda[t] < cbar - eta) {
                if (t > jj) {
@@ -1256 +1267 @@
                   utildavec[t] = vvec[t] = t1;
                   Deltavec[t] = 0;
-                  if (utildavec[t] > -yvec[t]) 
+                  if (utildavec[t] > -yvec[t])
                      deltavec[t] = -1;
                   else
@@ -1278 +1289 @@
 
          NumIterations++;
-   
+
          h = min(kk+1, m);
-   
+
          if ((delta - 8*red_fudge)*c[jj] > cbar) {
 
@@ -1287 +1298 @@
             // we treat the case that the new vector is b_s (jj < s <= kk)
             // as a special case that appears to occur most of the time.
-   
+
             s = 0;
             for (i = jj+1; i <= kk; i++) {
@@ -1297 +1308 @@
                }
             }
-   
+
             if (s == 0) Error("G_BKZ_FP: internal error");
-   
+
             if (s > 0) {
                // special case
 
                NumTrivial++;
-   
+
                for (i = s; i > jj; i--) {
                   // swap i, i-1
@@ -1311 +1322 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-   
+
                // cerr << "special case\n";
-               new_m = ll_G_LLL_FP(B, U, delta, 0, check, 
+               new_m = ll_G_LLL_FP(B, U, delta, 0, check,
                                 B1, mu, aux, h, jj, quit, cache);
                if (new_m != h) Error("G_BKZ_FP: internal error");
@@ -1322 +1333 @@
 
                NumNonTrivial++;
-   
+
                for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
 
@@ -1336 +1347 @@
                   if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
                }
-      
+
                for (i = m+1; i >= jj+1; i--) {
                   // swap i, i-1
@@ -1343 +1354 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                for (i = 1; i <= n; i++) {
                   conv(B1[jj][i], B(jj, i));
@@ -1350 +1361 @@
 
                if (IsZero(B(jj))) Error("G_BKZ_FP: internal error");
-      
+
                // remove linear dependencies
-   
+
                // cerr << "general case\n";
-               new_m = ll_G_LLL_FP(B, U, delta, 0, 0, B1, mu, aux, 
+               new_m = ll_G_LLL_FP(B, U, delta, 0, 0, B1, mu, aux,
                                   kk+1, jj, quit, cache);
-              
-               if (new_m != kk) Error("G_BKZ_FP: internal error"); 
+
+               if (new_m != kk) Error("G_BKZ_FP: internal error");
 
                // remove zero vector
-      
+
                for (i = kk+2; i <= m+1; i++) {
                   // swap i, i-1
@@ -1367 +1378 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                quit = 0;
                if (check) {
@@ -1378 +1389 @@
 
                if (quit) break;
-   
+
                if (h > kk) {
                   // extend reduced basis
-   
-                  new_m = ll_G_LLL_FP(B, U, delta, 0, check, 
+
+                  new_m = ll_G_LLL_FP(B, U, delta, 0, check,
                                    B1, mu, aux, h, h, quit, cache);
-   
+
                   if (new_m != h) Error("G_BKZ_FP: internal error");
                   if (quit) break;
                }
             }
-   
+
             z = 0;
          }
@@ -1399 +1410 @@
 
             if (!clean) {
-               new_m = ll_G_LLL_FP(B, U, delta, 0, check, B1, mu, aux, 
+               new_m = ll_G_LLL_FP(B, U, delta, 0, check, B1, mu, aux,
                                    h, h, quit, cache);
                if (new_m != h) Error("G_BKZ_FP: internal error");
                if (quit) break;
             }
-   
+
             z++;
          }
@@ -1466 +1477 @@
 }
 
-long G_BKZ_FP(mat_ZZ& BB, mat_ZZ& UU, double delta, 
+long G_BKZ_FP(mat_ZZ& BB, mat_ZZ& UU, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {
@@ -1478 +1489 @@
 }
 
-long G_BKZ_FP(mat_ZZ& BB, double delta, 
+long G_BKZ_FP(mat_ZZ& BB, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {

ntl/src/G_LLL_QP.c

@@ -24 +24 @@
 
 
-
 static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1)
 // x = x - y*MU
@@ -52 +51 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -62 +61 @@
       conv(mu1, MU);
 
-      for (i = 1; i <= n; i++) {
-         mul(T, B(i), mu1);
-         if (k > 0) LeftShift(T, T, k);
-         sub(A(i), A(i), T);
+      if (k > 0) {
+
+         for (i = 1; i <= n; i++) {
+            mul(T, B(i), mu1);
+            LeftShift(T, T, k);
+            sub(A(i), A(i), T);
+         }
+
+      }
+      else {
+
+         for (i = 1; i <= n; i++) {
+            MulSubFrom(A(i), B(i), mu1);
+         }
+
       }
    }
@@ -77 +87 @@
 }
 
+
+
+
 #define TR_BND (NTL_FDOUBLE_PRECISION/2.0)
 // Just to be safe!!
@@ -128 +141 @@
 
 
-   
-
-
-
-static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1, 
-                         quad_float *a, quad_float *b, long *in_a, 
+
+
+
+
+static void RowTransform(vec_ZZ& A, vec_ZZ& B, const ZZ& MU1,
+                         quad_float *a, quad_float *b, long *in_a,
                          double& max_a, double max_b, long& in_float)
 // x = x - y*MU
@@ -232 +245 @@
 
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -258 +271 @@
             if (in_a[i] && a[i].hi < TR_BND && a[i].hi > -TR_BND &&
                 b[i].hi < b_bnd && b[i].hi > -b_bnd) {
-  
+
                a[i].hi -= b[i].hi*mu;
             }
@@ -266 +279 @@
                   in_a[i] = 0;
                }
-               mul(T, B(i), mu1);
-               sub(A(i), A(i), T);
+               MulSubFrom(A(i), B(i), mu1);
            }
          }
@@ -312 +324 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -359 +371 @@
 {
    sz = min(m, n)/10;
-   if (sz < 2) 
+   if (sz < 2)
       sz = 2;
    else if (sz > 20)
@@ -367 +379 @@
 
    long i;
-   buf = NTL_NEW_OP quad_floatptr[sz]; 
+   buf = NTL_NEW_OP quad_floatptr[sz];
    if (!buf) Error("out of memory");
    for (i = 0; i < sz; i++)
@@ -454 +466 @@
    }
 
-   i = 0; 
+   i = 0;
    while (i < sz && bl[i] != 0)
       i++;
@@ -499 +511 @@
          backoff = 2;
       else if (backoff > cache.sz + 2)
-         backoff = cache.sz + 2; 
+         backoff = cache.sz + 2;
 
       long ub = k-(backoff-1);
@@ -506 +518 @@
          quad_float *cptr = mu[i];
          quad_float *sptr = aux[i];
-   
+
          for (j = n; j > i; j--) {
             c = cptr[j];
             s = sptr[j];
-   
+
             a = c*pp[j-1] - s*pp[j];
             b = s*pp[j-1] + c*pp[j];
-   
+
             pp[j-1] = a;
             pp[j] = b;
          }
-   
-         pp[i] = pp[i]/mu[i][i]; 
+
+         pp[i] = pp[i]/mu[i][i];
       }
 
@@ -531 +543 @@
       quad_float *cptr = mu[i];
       quad_float *sptr = aux[i];
-  
+
       for (j = n; j > i; j--) {
          c = cptr[j];
          s = sptr[j];
-  
+
          a = c*p[j-1] - s*p[j];
          b = s*p[j-1] + c*p[j];
-  
+
          p[j-1] = a;
          p[j] = b;
       }
-  
+
       p[i] = p[i]/mu[i][i];
    }
@@ -564 +576 @@
          s = c*t;
       }
-   
+
       p[j-1] = c*a - s*b;
       p[j] = c;
@@ -595 +607 @@
    // to help ensure stability in G_BKZ_QP1
 
-   log_red = NTL_DOUBLE_PRECISION-2; 
+   log_red = NTL_DOUBLE_PRECISION-2;
 
    red_fudge = 1;
@@ -617 +629 @@
 
 static
-long ll_G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep, 
-           LLLCheckFct check, quad_float **B1, quad_float **mu, 
+long ll_G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep,
+           LLLCheckFct check, quad_float **B1, quad_float **mu,
            quad_float **aux,
            long m, long init_k, long &quit, GivensCache_QP& cache)
@@ -689 +701 @@
 
          Fc1 = 0;
-   
+
          for (j = k-1; j >= 1; j--) {
             t1 = fabs(mu[k][j]);
@@ -715 +727 @@
 
 
-   
+
                mu1 = mu[k][j];
                if (mu1 >= 0)
@@ -721 +733 @@
                else
                   mu1 = floor(mu1+half);
-   
-   
+
+
                quad_float *mu_k = mu[k];
                quad_float *mu_j = mu[j];
-  
+
                if (mu1 == 1) {
                   for (i = 1; i <= j-1; i++)
@@ -740 +752 @@
 
                // cout << j << " " << mu[k][j] << " " << mu1 << "\n";
-  
+
                mu_k[j] -= mu1;
 
                conv(MU, mu1);
 
-   
+
                RowTransform(B(k), B(j), MU, B1[k], B1[j], in_vec,
                             max_b[k], max_b[j], in_float);
@@ -761 +773 @@
       } while (Fc1);
 
-      if (check && (*check)(B(k))) 
+      if (check && (*check)(B(k)))
          quit = 1;
 
@@ -784 +796 @@
       if (deep > 0) {
          // deep insertions
-   
+
          Error("sorry...deep insertions not implemented");
       } // end deep insertions
@@ -819 +831 @@
 
 static
-long G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep, 
+long G_LLL_QP(mat_ZZ& B, mat_ZZ* U, quad_float delta, long deep,
            LLLCheckFct check)
 {
@@ -877 +889 @@
    GivensCache_QP cache(m, n);
 
-   new_m = 
+   new_m =
       ll_G_LLL_QP(B, U, delta, deep, check, B1, mu, aux, m, 1, quit, cache);
 
@@ -918 +930 @@
 }
 
-         
+
 
 long G_LLL_QP(mat_ZZ& B, double delta, long deep, LLLCheckFct check,
@@ -931 +943 @@
 }
 
-long G_LLL_QP(mat_ZZ& B, mat_ZZ& U, double delta, long deep, 
+long G_LLL_QP(mat_ZZ& B, mat_ZZ& U, double delta, long deep,
            LLLCheckFct check, long verb)
 {
@@ -949 +961 @@
 void ComputeG_BKZConstant(long beta, long p)
 {
-   const quad_float c_PI = 
+   const quad_float c_PI =
       to_quad_float("3.141592653589793238462643383279502884197");
-   const quad_float LogPI = 
+   const quad_float LogPI =
       to_quad_float("1.144729885849400174143427351353058711647");
 
@@ -975 +987 @@
          for (j = 1; j <= k; j++)
             x = x + Log(j);
-          
+
          x = x * (1/to_quad_float(k));
 
@@ -1003 +1015 @@
 static vec_quad_float G_BKZThresh;
 
-static 
+static
 void ComputeG_BKZThresh(quad_float *c, long beta)
 {
@@ -1022 +1034 @@
 
 static
-long G_BKZ_QP(mat_ZZ& BB, mat_ZZ* UU, quad_float delta, 
+long G_BKZ_QP(mat_ZZ& BB, mat_ZZ* UU, quad_float delta,
          long beta, long prune, LLLCheckFct check)
 {
@@ -1029 +1041 @@
    long n = BB.NumCols();
    long m_orig = m;
-   
+
    long i, j;
    ZZ MU;
@@ -1136 +1148 @@
          CheckFinite(&B1[i][j]);
       }
-         
+
 
    GivensCache_QP cache(m, n);
@@ -1174 +1186 @@
       z = 0;
       jj = 0;
-   
+
       while (z < m-1) {
          jj++;
          kk = min(jj+beta-1, m);
-   
+
          if (jj == m) {
             jj = 1;
@@ -1197 +1209 @@
             ComputeG_BKZThresh(&c[jj], kk-jj+1);
 
-   
+
          cbar = c[jj];
          utildavec[jj] = uvec[jj] = 1;
-   
+
          yvec[jj] = vvec[jj] = 0;
          Deltavec[jj] = 0;
-   
-   
+
+
          s = t = jj;
          deltavec[jj] = 1;
-   
+
          for (i = jj+1; i <= kk+1; i++) {
             ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
@@ -1216 +1228 @@
 
          long enum_cnt = 0;
-   
+
          while (t <= kk) {
 
-            ctilda[t] = ctilda[t+1] + 
+            ctilda[t] = ctilda[t+1] +
                (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*c[t];
-   
+
             if (prune > 0 && t > jj) {
                eta = G_BKZThresh(t-jj);
@@ -1246 +1258 @@
                   utildavec[t] = vvec[t] = t1;
                   Deltavec[t] = 0;
-                  if (utildavec[t] > -yvec[t]) 
+                  if (utildavec[t] > -yvec[t])
                      deltavec[t] = -1;
                   else
@@ -1270 +1282 @@
 
          h = min(kk+1, m);
-   
+
          if ((delta-8*red_fudge)*c[jj] > cbar) {
 
@@ -1277 +1289 @@
             // we treat the case that the new vector is b_s (jj < s <= kk)
             // as a special case that appears to occur most of the time.
-   
+
             s = 0;
             for (i = jj+1; i <= kk; i++) {
@@ -1287 +1299 @@
                }
             }
-   
+
             if (s == 0) Error("G_BKZ_QP: internal error");
-   
+
             if (s > 0) {
                // special case
 
                NumTrivial++;
-   
+
                for (i = s; i > jj; i--) {
                   // swap i, i-1
@@ -1301 +1313 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-   
+
                // cerr << "special case\n";
                new_m = ll_G_LLL_QP(B, U, delta, 0, check,
@@ -1313 +1325 @@
                NumNonTrivial++;
 
-   
+
                for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
 
@@ -1327 +1339 @@
                   if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
                }
-      
+
                for (i = m+1; i >= jj+1; i--) {
                   // swap i, i-1
@@ -1334 +1346 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                for (i = 1; i <= n; i++) {
                   conv(B1[jj][i], B(jj, i));
                   CheckFinite(&B1[jj][i]);
                }
-      
-               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error"); 
-      
+
+               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error");
+
                // remove linear dependencies
-   
+
                // cerr << "general case\n";
                new_m = ll_G_LLL_QP(B, U, delta, 0, 0, B1, mu, aux,
                                   kk+1, jj, quit, cache);
-              
-               if (new_m != kk) Error("G_BKZ_QP: internal error"); 
+
+               if (new_m != kk) Error("G_BKZ_QP: internal error");
 
                // remove zero vector
-      
+
                for (i = kk+2; i <= m+1; i++) {
                   // swap i, i-1
@@ -1358 +1370 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                quit = 0;
                if (check) {
@@ -1369 +1381 @@
 
                if (quit) break;
-   
+
                if (h > kk) {
                   // extend reduced basis
-   
+
                   new_m = ll_G_LLL_QP(B, U, delta, 0, check,
                                    B1, mu, aux, h, h, quit, cache);
-   
+
                   if (new_m != h) Error("G_BKZ_QP: internal error");
                   if (quit) break;
                }
             }
-   
+
             z = 0;
          }
@@ -1392 +1404 @@
             if (!clean) {
                new_m =
-                  ll_G_LLL_QP(B, U, delta, 0, check, B1, mu, aux, 
+                  ll_G_LLL_QP(B, U, delta, 0, check, B1, mu, aux,
                               h, h, quit, cache);
                if (new_m != h) Error("G_BKZ_QP: internal error");
                if (quit) break;
             }
-   
+
             z++;
          }
@@ -1460 +1472 @@
 }
 
-long G_BKZ_QP(mat_ZZ& BB, mat_ZZ& UU, double delta, 
+long G_BKZ_QP(mat_ZZ& BB, mat_ZZ& UU, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {
@@ -1466 +1478 @@
    NumSwaps = 0;
 
-
    if (delta < 0.50 || delta >= 1) Error("G_BKZ_QP: bad delta");
    if (beta < 2) Error("G_BKZ_QP: bad block size");
@@ -1473 +1484 @@
 }
 
-long G_BKZ_QP(mat_ZZ& BB, double delta, 
+long G_BKZ_QP(mat_ZZ& BB, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {
@@ -1488 +1499 @@
 
 static
-long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ* UU, quad_float delta, 
+long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ* UU, quad_float delta,
          long beta, long prune, LLLCheckFct check)
 {
@@ -1495 +1506 @@
    long n = BB.NumCols();
    long m_orig = m;
-   
+
    long i, j;
    ZZ MU;
@@ -1641 +1652 @@
       z = 0;
       jj = 0;
-   
+
       while (z < m-1) {
          jj++;
          kk = min(jj+beta-1, m);
-   
+
          if (jj == m) {
             jj = 1;
@@ -1664 +1675 @@
             ComputeG_BKZThresh(&c[jj], kk-jj+1);
 
-   
+
          cbar = to_double(c[jj]);
          utildavec[jj] = uvec[jj] = 1;
-   
+
          yvec[jj] = vvec[jj] = 0;
          Deltavec[jj] = 0;
-   
-   
+
+
          s = t = jj;
          deltavec[jj] = 1;
-   
+
          for (i = jj+1; i <= kk+1; i++) {
             ctilda[i] = uvec[i] = utildavec[i] = yvec[i] = 0;
@@ -1683 +1694 @@
 
          long enum_cnt = 0;
-   
+
          while (t <= kk) {
-
-            ctilda[t] = ctilda[t+1] + 
+            ctilda[t] = ctilda[t+1] +
                (yvec[t]+utildavec[t])*(yvec[t]+utildavec[t])*to_double(c[t]);
 
             ForceToMem(&ctilda[t]); // prevents an infinite loop
-   
+
             if (prune > 0 && t > jj) {
                eta = to_double(G_BKZThresh(t-jj));
@@ -1717 +1727 @@
                   utildavec[t] = vvec[t] = t1;
                   Deltavec[t] = 0;
-                  if (utildavec[t] > -yvec[t]) 
+                  if (utildavec[t] > -yvec[t])
                      deltavec[t] = -1;
                   else
@@ -1743 +1753 @@
 
          quad_float t1;
-   
+
          if ((delta-8*red_fudge)*c[jj] > cbar*(1+64/NTL_FDOUBLE_PRECISION)) {
 
@@ -1750 +1760 @@
             // we treat the case that the new vector is b_s (jj < s <= kk)
             // as a special case that appears to occur most of the time.
-   
+
             s = 0;
             for (i = jj+1; i <= kk; i++) {
@@ -1760 +1770 @@
                }
             }
-   
+
             if (s == 0) Error("G_BKZ_QP: internal error");
-   
+
             if (s > 0) {
                // special case
 
                NumTrivial++;
-   
+
                for (i = s; i > jj; i--) {
                   // swap i, i-1
@@ -1774 +1784 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-   
+
                // cerr << "special case\n";
                new_m = ll_G_LLL_QP(B, U, delta, 0, check,
@@ -1786 +1796 @@
                NumNonTrivial++;
 
-   
+
                for (i = 1; i <= n; i++) conv(B(m+1, i), 0);
 
@@ -1800 +1810 @@
                   if (U) RowTransform2((*U)(m+1), (*U)(i), MU);
                }
-      
+
                for (i = m+1; i >= jj+1; i--) {
                   // swap i, i-1
@@ -1807 +1817 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                for (i = 1; i <= n; i++) {
                   conv(B1[jj][i], B(jj, i));
                   CheckFinite(&B1[jj][i]);
                }
-      
-               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error"); 
-      
+
+               if (IsZero(B(jj))) Error("G_BKZ_QP: internal error");
+
                // remove linear dependencies
-   
+
                // cerr << "general case\n";
                new_m = ll_G_LLL_QP(B, U, delta, 0, 0, B1, mu, aux,
                                   kk+1, jj, quit, cache);
-              
-               if (new_m != kk) Error("G_BKZ_QP: internal error"); 
+
+               if (new_m != kk) Error("G_BKZ_QP: internal error");
 
                // remove zero vector
-      
+
                for (i = kk+2; i <= m+1; i++) {
                   // swap i, i-1
@@ -1831 +1841 @@
                   tp = B1[i-1]; B1[i-1] = B1[i]; B1[i] = tp;
                }
-      
+
                quit = 0;
                if (check) {
@@ -1842 +1852 @@
 
                if (quit) break;
-   
+
                if (h > kk) {
                   // extend reduced basis
-   
+
                   new_m = ll_G_LLL_QP(B, U, delta, 0, check,
                                    B1, mu, aux, h, h, quit, cache);
-   
+
                   if (new_m != h) Error("G_BKZ_QP: internal error");
                   if (quit) break;
                }
             }
-   
+
             z = 0;
          }
@@ -1870 +1880 @@
                if (quit) break;
             }
-   
+
             z++;
          }
@@ -1933 +1943 @@
 }
 
-long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ& UU, double delta, 
+long G_BKZ_QP1(mat_ZZ& BB, mat_ZZ& UU, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {
@@ -1945 +1955 @@
 }
 
-long G_BKZ_QP1(mat_ZZ& BB, double delta, 
+long G_BKZ_QP1(mat_ZZ& BB, double delta,
          long beta, long prune, LLLCheckFct check, long verb)
 {

ntl/src/G_LLL_RR.c

@@ -37 +37 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -89 +89 @@
    if (MU == 0) return;
 
-   if (NumTwos(MU) >= NTL_ZZ_NBITS) 
+   if (NumTwos(MU) >= NTL_ZZ_NBITS)
       k = MakeOdd(MU);
    else
@@ -138 +138 @@
 {
    sz = min(m, n)/10;
-   if (sz < 2) 
+   if (sz < 2)
       sz = 2;
    else if (sz > 20)
@@ -227 +227 @@
    }
 
-   i = 0; 
+   i = 0;
    while (i < sz && bl[i] != 0)
       i++;
@@ -273 +273 @@
          backoff = 2;
       else if (backoff > cache.sz + 2)
-         backoff = cache.sz + 2; 
+         backoff = cache.sz + 2;
 
       long ub = k-(backoff-1);
@@ -280 +280 @@
          vec_RR& cptr = mu(i);
          vec_RR& sptr = aux(i);
-   
+
          for (j = n; j > i; j--) {
             c = cptr(j);
             s = sptr(j);
-   
+
             // a = c*pp(j-1) - s*pp(j);
             mul(T1, c, pp(j-1));
@@ -294 +294 @@
             mul(T2, c, pp(j));
             add(b, T1, T2);
-   
+
             pp(j-1) = a;
             pp(j) = b;
          }
-   
+
          div(pp(i), pp(i), mu(i,i));
       }
@@ -312 +312 @@
       vec_RR& cptr = mu(i);
       vec_RR& sptr = aux(i);
-  
+
       for (j = n; j > i; j--) {
          c = cptr(j);
          s = sptr(j);
-  
+
          // a = c*p(j-1) - s*p(j);
          mul(T1, c, p(j-1));
@@ -326 +326 @@
          mul(T2, c, p(j));
          add(b, T1, T2);
-  
+
          p(j-1) = a;
          p(j) = b;
       }
-  
+
       div(p(i), p(i), mu(i,i));
    }
@@ -350 +350 @@
             div(T1, a, b);
             negate(t, T1);
-   
+
             // s = 1/sqrt(1 + t*t);
             sqr(T1, t);
@@ -356 +356 @@
             SqrRoot(T1, T1);
             inv(s, T1);
-            
+
             // c = s*t;
             mul(c, s, t);
@@ -364 +364 @@
             div(T1, b, a);
             negate(t, T1);
-   
+
             // c = 1/sqrt(1 + t*t);
             sqr(T1, t);