beyond_the_mountain.md

Writeup "beyond the mountain" (crypto) from backdoorctf 2021

[This challenges had a mountainous flavor text, now lost to history.]

In short, the task is to provide vectors flipping specific bits in an encryption scheme resembling ring learning with errors.

1 solve / 500 points

Given

chall.sage

import random

q = 3329
R = Zmod(q)
N = 32
l = 2
d = 11
Rx.<x> = PolynomialRing(R)
Rq.<u> = Rx.quotient(x^N + 1)

# My not so secret keys
# Static keys so you can precompute part of the solution to spare our poor VPS some load
t = vector(Rq, [3299*u^31 + 3045*u^30 + 2395*u^29 + 742*u^28 + 2092*u^27 + 22*u^26 + 2323*u^25 + 506*u^24 + 2532*u^23 + 5*u^22 + 1565*u^21 + 704*u^20 + 355*u^19 + 1766*u^18 + 1307*u^17 + 1148*u^16 + 1194*u^15 + 2260*u^14 + 1999*u^13 + 1188*u^12 + 731*u^11 + 68*u^10 + 847*u^9 + 2090*u^8 + 2514*u^7 + 3252*u^6 + 997*u^5 + 2271*u^4 + 731*u^3 + 1937*u^2 + 7*u + 2574, 2383*u^31 + 3121*u^30 + 963*u^29 + 1495*u^28 + 2776*u^27 + 2541*u^26 + 2516*u^25 + 2667*u^24 + 2772*u^23 + 114*u^22 + 1762*u^21 + 366*u^20 + 1343*u^19 + 2521*u^18 + 1678*u^17 + 3224*u^16 + 510*u^15 + 1594*u^14 + 3020*u^13 + 3145*u^12 + 1114*u^11 + 1823*u^10 + 1081*u^9 + 1737*u^8 + 2821*u^7 + 2202*u^6 + 2355*u^5 + 2238*u^4 + 745*u^3 + 266*u^2 + 887*u + 2731])
rh = 3428567257
s = vector(Rq, [4*u^31 + u^30 + 2*u^29 + u^28 + 4*u^27 + u^26 + 3*u^25 + 4*u^24 + 3*u^23 + u^22 + 2*u^21 + 4*u^20 + 3*u^19 + u^18 + u^17 + 3*u^16 + 2*u^15 + 2*u^14 + 4*u^13 + 4*u^12 + 2*u^11 + u^10 + u^9 + u^8 + u^7 + 2*u^6 + 4*u^5 + 2*u^4 + 3*u^3 + 4*u^2 + 3*u + 2, 4*u^31 + u^30 + 2*u^29 + 4*u^28 + u^27 + 3*u^26 + 2*u^25 + u^24 + u^23 + 3*u^22 + 4*u^21 + u^20 + u^19 + 4*u^18 + 3*u^17 + u^16 + u^15 + 3*u^14 + 3*u^13 + 3*u^12 + 3*u^11 + 3*u^10 + u^9 + 4*u^8 + 3*u^7 + 4*u^6 + 2*u^5 + 2*u^4 + u^3 + u^2 + 4*u + 4])
e = vector(Rq, [3325*u^31 + 5*u^30 + 3325*u^29 + 3325*u^28 + 3324*u^27 + 4*u^26 + 5*u^25 + 3324*u^24 + 3324*u^23 + 3324*u^22 + 5*u^21 + 3325*u^20 + 5*u^19 + 3325*u^18 + 5*u^17 + 3325*u^16 + 3326*u^15 + 3325*u^14 + 3328*u^13 + 3327*u^12 + 3325*u^11 + 3326*u^10 + 3327*u^9 + 3328*u^8 + 3327*u^7 + 3325*u^6 + 3325*u^5 + 3327*u^4 + 3326*u^3 + 3328*u^2 + 3328*u + 3325, 3325*u^31 + 5*u^30 + 5*u^29 + 3325*u^28 + 3325*u^27 + 4*u^26 + 3324*u^25 + 3325*u^24 + 3325*u^23 + 3324*u^22 + 3325*u^21 + 4*u^20 + 4*u^19 + 3325*u^18 + 3324*u^17 + 4*u^16 + 3325*u^15 + 4*u^14 + 5*u^13 + 4*u^12 + 3324*u^11 + 5*u^10 + 5*u^9 + 3324*u^8 + 5*u^7 + 4*u^6 + 5*u^5 + 3324*u^4 + 4*u^3 + 3324*u^2 + 5*u + 3325])

pk = (t, rh)
sk = (s, e)

def genA(base_ring, r, l):
    random.seed(r)
    A = Matrix(base_ring, [[base_ring([Integer(random.randint(0, q-1)) for _ in range(N)]) for _ in range(l)] for _ in range(l)])
    return A

def decode(base_ring, v):
    v = list(v).copy()
    for i, p in enumerate(v):
        coefs = p.list()
        for j, a in enumerate(coefs):
            coefs[j] = round((2/q)*Integer(a))%2
        v[i] = base_ring(coefs)
    return v

def small_secret():
    return Rq([randint(1, 4) for _ in range(N)])

def small_error():
    return Rq([randint(-4, -1) for _ in range(N)])

# In case you plebs think testing it locally will make it any easier
def keygen():
    global l
    r = Integer(random.getrandbits(N))
    A = genA(Rq, r, l)
    s = vector(Rq, [small_secret() for _ in range(l)])
    e = vector(Rq, [small_error() for _ in range(l)])
    t = A*s + e

    return (t, r), (s, e)

def encrypt(pk, m, r, e1):
    t, rh = pk
    t = vector(Rq, t)
    A = genA(Rq, rh, l)
    m = list(map(int, bin(m)[2:][::-1]))
    m = Rq(m)
    e2 = small_error()
    u = A.transpose()*r + e1
    v = t*r + e2 + (q//2)*m
    return (u, v)

def decrypt(sk, ct):
    u, v = ct
    m = decode(Rq, [v - sk*u])[0]
    m = m.list()[::-1]
    return int(''.join(map(str, m)), 2)

def verify_small_vector(v):
    return all([-6 <= i <= 6 for i in v[:-1]])

def flatten(u):
    b = []
    for i in u:
        j = i.list()
        j = j + [0]*(N-len(j))
        b += j
    return vector(R, b)

def unflatten(base_ring, v):
    v = list(v)
    return vector(base_ring, [base_ring(v[i*N: (i+1)*N]) for i in range(len(v)//N)])

def receive_vector():
    """
    What you want to input here is a vector of dimension l over Rq.
    The way to do that is to create your vector, call the function "flatten" on it,
    and then send the resulting list as comma separated integers
    e.g: if your vector is v, you need to send str(flatten(v)).replace("[", "").replace("]", "")
    """
    a = input("Enter vector: ")
    a = list(map(Integer, a.split(",")))
    
    if len(a) != N*l:
        print ("It's just a simple math challenge, no pwn trickery please")
        exit()

    if not verify_small_vector(a):
        print ("Is an error even an error if it's not small")
        exit()
    
    return unflatten(Rq, a)

for _ in range(5):
    pt = randint(0, 2^11)
    print ("plaintext: ", pt)
    challenge = 2^randint(0, 11)
    print ("challenge: ", challenge)
    r = receive_vector()
    e1 = receive_vector()
    dif = decrypt(sk[0], encrypt(pk, pt, r, e1))^^pt
    if dif != challenge:
        print ("So much for perfect correctness")
        exit()

print ("OK, you win. Here's your flag")

Explanation

Computations are in the ring $R_q := \mathbb Z_q[x]/(x^N+1)$ with $N=32$. Somewhat unusually, the modulus is not irreducible, though we do not make use of that property.

We are given constants $t,rh,s,e$. $rh$ determines a matrix $A\in R_q^{2\times 2}$ (genA) with $t=A\cdot s+e$.

encrypt takes vectors $r,e_1$ and a message as input. The program ensures that $r,e_1$ are small (verify_small_vector), i.e., the coefficients of entries are in the range $[-6,6]$ (recall we have vectors of polynomials). The message is encoded as a polynomial $m\in R_q$ whose coefficients are the message's bits. encrypt returns $u = A^Tr + e_1$ and $v = t^Tr + e_2 + \lfloor\frac q2 \rfloor m$, where $e_2$ is a small_error with coefficients in $[-4,-1]$.

decrypt then computes $y := v - s^T u$ and extracts the message bits from the coefficients $c$ of $y$ as $\lfloor\frac2q c\rceil \bmod 2$. In other words, a coefficient is interpreted as 1 iff it is closer to $q/2$ than $0 \mod q$.

Why does this work? Substituting, we get $y = (As + e)^Tr + e_2+\lfloor\frac q2\rfloor m - s^T(A^Tr+e_1)$. Simplifying to $y = \lfloor\frac q2\rfloor m +e_2 + e^Tr - s^Te_1$. Ideally, we have $y \approx \lfloor\frac q2\rfloor m$, because $e,e_1,e_2,s,r$ are all small, but is that really the case?

Challenge

Our challenge is now to provide $e_1,r$ such that a precisely one given bit $n$ of a random $pt\in [0,2^{11}]$ flips. We need to solve this challenge five times consecutively to get the flag.

Though $pt, A$ are known, our solution does not depend on them. In fact it would also work with $pt\in [0,2^N]$.

Solution

Note that the only thing we can control is the term $z:= (e^Tr-s^Te_1)$. To flip bit $n$ (and solve the challenge), we need $c_n \approx q/2$ and $c_i \approx 0$ for $i\ne n$, where $c_0,\dots,c_{N-1}$ are the coefficients of $z$. Note that the $\approx$ is very lose here, it suffices to be within $\pm q/4$ (in reality a little less because of the $e_2$ error term).

Recall that the coefficients of $s,e_1$ are restricted to $[-6,6]$, so there does not appear to be an easy solution. We first tried to solve this using the closest vector problem (CVP), but my 64G machine ran out of RAM. The second idea was to use the solver Z3, but it did not seem like the program would terminate before the heat death of the universe.

Baring any mathematical insight, we used brute force, which miraculously did work quite well.

It is straightforward to implement the computation of $y$ in C++. To implement the $x^N+1$ modulus we observe that $x^{i+N} = -x^{i}\mod (x^N+1)$ (easily verified with sage).

typedef int V[2][N];

void multiply(const int *a, const int *b, int *c) {
  std::fill(c, c + N, 0);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) {
      int d = i + j;
      int sig = d >= N ? -1 : 1;
      c[d % N] += a[i] * b[j] * sig;
    }
}

void comp(V &r, V &e1, int *out) { // e*r - s*e1
  int a[N]{};
  int b[N]{};
  int c[N]{};
  int d[N]{};
  multiply(e[0], r[0], a);
  multiply(e[1], r[1], b);
  multiply(s[0], e1[0], c);
  multiply(s[1], e1[1], d);
  for (int i = 0; i < N; ++i) {
    out[i] = ((a[i] + b[i] - c[i] - d[i]) % q + q) % q;
  }
}

We choose all coefficients $r,e_1$ uniformly at random from $[-6,6]$. Interestingly, the comp output appears to have at most one big (q/4 + 4 < c < q*3/4 - 4) coefficient (with high probability?), which is exactly what we need!

Searching with 32 threads, we find $e_1,r$ values to flip each of the $N$ bits in about 1.35 minutes.

Full code

Bruteforce in C++, output to all.txt.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <thread>
#include <mutex>
#include <random>

constexpr int N = 32;
constexpr int q = 3329;

typedef int V[2][N];

constexpr V s = {{2, 3, 4, 3, 2, 4, 2, 1, 1, 1, 1, 2, 4, 4, 2, 2, 3, 1, 1, 3, 4, 2, 1, 3, 4, 3, 1, 4, 1, 2, 1, 4},
                 {4, 4, 1, 1, 2, 2, 4, 3, 4, 1, 3, 3, 3, 3, 3, 1, 1, 3, 4, 1, 1, 4, 3, 1, 1, 2, 3, 1, 4, 2, 1, 4}};

constexpr V e = {{3325, 3328, 3328, 3326, 3327, 3325, 3325, 3327, 3328, 3327, 3326, 3325, 3327, 3328, 3325, 3326, 3325, 5, 3325, 5, 3325, 5, 3324, 3324, 3324, 5, 4, 3324, 3325, 3325, 5, 3325},
                 {3325, 5, 3324, 4, 3324, 5, 4, 5, 3324, 5, 5, 3324, 4, 5, 4, 3325, 4, 3324, 3325, 4, 4, 3325, 3324, 3325, 3325, 3324, 4, 3325, 3325, 5, 5, 3325}};

void multiply(const int *a, const int *b, int *c) {
  std::fill(c, c + N, 0);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) {
      int d = i + j;
      int sig = d >= N ? -1 : 1;
      c[d % N] += a[i] * b[j] * sig;
    }
}

void comp(V &r, V &e1, int *out) { // e*r - s*e1
  int a[N]{};
  int b[N]{};
  int c[N]{};
  int d[N]{};
  multiply(e[0], r[0], a);
  multiply(e[1], r[1], b);
  multiply(s[0], e1[0], c);
  multiply(s[1], e1[1], d);
  for (int i = 0; i < N; ++i) {
    out[i] = ((a[i] + b[i] - c[i] - d[i]) % q + q) % q;
  }
}

void printV(const V &v) {
  printf("tovec([");
  for (int j = 0; j < 2; ++j) {
    printf("[");
    for (int k = 0; k < N; ++k) {
      printf("%d, ", v[j][k]);
    }
    printf("], ");
  }
  printf("])");
}

void print_arr(const int *a) {
  for (int i = 0; i < N; ++i) {
    auto c = a[i];
    printf("%d, ", c > q / 2 ? c - q : c);
  }
  puts("");
}

bool found[N];
int found_count = 0;
std::mutex found_mutex;


void search() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> distrib(-6, 6);
  V r;
  V e1;
  int x[N];
  for (size_t i = 0; i < (1ull << 40); ++i) {
    //if ((i & 0xfffff) == 0) {
    //  printf("%lx\n", i);
    //}
    for (int j = 0; j < N; ++j) {
      r[0][j] = distrib(gen);
      r[1][j] = distrib(gen);
      e1[0][j] = distrib(gen);
      e1[1][j] = distrib(gen);
    }
    comp(r, e1, x);
    int big_count{};
    int big_j{};
    constexpr int LO = q / 4 + 4, HI = q * 3 / 4 - 4;
    for (int j = 0; j < N; ++j) {
      int c = x[j];
      if (LO < c && c < HI) {
        big_j = j;
        big_count++;
      }
    }
    if (big_count == 1) {
      std::lock_guard g(found_mutex);
      if (!found[big_j]) {
        found[big_j] = true;
        found_count++;
        printf("%d: (", big_j);
        printV(r);
        printf(", ");
        printV(e1);
        printf("),\n# ");
        print_arr(x);
        puts("");
      }
    }
    if (found_count == N) return;
  }
}

void test() {
  V r{{3325, 3327, 4, 6, 3, 4,    2, 3327, 3324, 2,    3326, 6,    1, 1, 3325, 0, 1, 2, 3328, 1, 3327, 3328, 2, 1, 3327, 3,    0, 6,    3,    1, 4, 3328},
      {3323, 5,    0, 3, 3, 3324, 1, 6,    3327, 3327, 5,    3323, 4, 2, 3326, 6, 2, 3, 3324, 4, 2,    3328, 4, 0, 3327, 3328, 3, 3328, 3325, 6, 1, 2}};
  V e1{{3325, 3324, 3323, 6,    0, 3325, 0, 6, 3323, 3327, 6,    1, 3327, 3327, 3328, 6, 4,    3, 2, 1, 3326, 2, 3326, 3325, 1,    3,    2,    3328, 3, 2, 3323, 5},
       {6,    6,    6,    3327, 3, 3328, 0, 0, 3328, 3327, 3328, 6, 3324, 3328, 3323, 2, 3328, 2, 0, 1, 0,    4, 3328, 0,    3327, 3328, 3325, 2,    3, 0, 3,    3324}};
  int c[]{3250, 86, 267, 3309, 3144, 175, 62, 3269, 220, 3320, 3249, 20, 3286, 90, 3326, 59, 39, 3218, 3317, 3217, 103,
          3257, 229, 3275, 134, 3326, 61, 3169, 3297, 3278, 3187, 3152};
  int out[N]{};
  comp(r, e1, out);
  for (int i = 0; i < N; ++i) {
    assert(c[i] == out[i]);
  }
}

int main() {
  //test();
  constexpr int TC = 32;
  std::vector<std::thread> threads;
  for (int i = 0; i < TC; ++i) {
    threads.emplace_back(search);
  }

  for (auto &t: threads) {
    t.join();
  }

  search();
  return 0;
}

Convert all.txt to python array (add code to chall.sage):

def tovec(v):
    return vector([Rq(v[0]), Rq(v[1])])
D = eval("{" + open('all.txt').read() + "}")
print([(flatten(D[i][0]), flatten(D[i][1])) for i in range(N)])

Final solution script:

from pwn import *

context(log_level='debug')

q = 3329
N = 32
l = 2
# p = process(['sage', 'chall.sage'])
p = remote('52.172.254.231', 7905)

D = [((2, 6, 3326, 3328, 3, 5, 1, 3323, 6, 2, 2, 3326, 4, 3323, 3, 3324, 5, 3, 3, 0, 3324, 5, 0, 0, 4, 5, 4, 4, 5, 4, 3326, 0, 3327, 3, 4, 3328, 6, 5, 1, 6, 6, 2, 3, 3326, 3327, 3324, 0, 2, 1, 3328, 3324, 3327, 3, 3, 3323, 3326, 2, 3324, 3328, 4, 6, 3327, 3326, 3323),
      (3323, 3323, 3328, 3326, 3328, 2, 3325, 3, 6, 4, 3325, 3323, 6, 6, 3324, 1, 5, 0, 6, 3325, 3, 4, 6, 3323, 2, 3, 3328, 3, 5, 3328, 6, 1, 1, 2, 2, 3328, 6, 3326, 3328, 6, 3326, 4, 3327, 1, 2, 1, 6, 2, 3326, 5, 1, 4, 4, 3328, 3, 0, 4, 3323, 4, 6, 3323, 3324, 6, 6)),
     ((0, 1, 3, 3323, 3325, 3327, 3326, 6, 5, 0, 3325, 3323, 0, 3328, 4, 3325, 4, 3326, 3326, 4, 3324, 3324, 5, 4, 2, 3323, 3325, 3327, 3323, 1, 3, 0, 3323, 6, 3326, 4, 5, 3324, 3328, 4, 3327, 1, 3327, 3326, 3326, 2, 5, 0, 3328, 4, 6, 4, 3328, 3326, 3323, 3324, 3327, 3324, 5, 6, 5, 3323, 6, 3328),
      (3, 0, 3326, 0, 3, 5, 3325, 5, 3323, 3326, 4, 0, 3324, 3323, 2, 3, 2, 3325, 3, 6, 0, 3323, 3, 3, 4, 3324, 3323, 3, 1, 2, 3323, 3323, 1, 3, 3324, 5, 0, 3323, 3327, 3323, 3327, 0, 3323, 3327, 3325, 3327, 3326, 0, 3328, 6, 3324, 3323, 3323, 1, 3323, 3324, 1, 4, 3326, 3324, 3324, 3327, 3324, 6)),
     ((3324, 4, 6, 3327, 3325, 3324, 3326, 0, 6, 1, 3323, 0, 3327, 4, 3323, 6, 3325, 3325, 3328, 5, 3, 6, 2, 5, 3326, 3326, 5, 5, 3327, 3328, 4, 5, 3, 3, 4, 3323, 6, 6, 3323, 3327, 6, 3327, 0, 3328, 3, 3323, 6, 1, 3323, 3324, 4, 3327, 6, 6, 3, 4, 5, 6, 6, 3328, 3, 4, 3324, 4),
      (6, 2, 1, 1, 3325, 3324, 3328, 4, 3, 3323, 3328, 3327, 2, 3325, 3323, 3328, 3326, 3323, 3326, 3324, 3325, 3323, 3324, 5, 3323, 1, 3326, 3323, 3323, 3324, 1, 1, 3326, 5, 2, 3323, 3325, 3323, 3328, 3326, 3324, 3326, 3328, 3328, 0, 3328, 3325, 5, 3327, 3323, 3325, 4, 1, 6, 6, 3323, 3323, 4, 0, 3326, 3323, 3323, 3327, 3324)),
     ((1, 3327, 3327, 3325, 3324, 2, 3, 3328, 3326, 2, 0, 3328, 3326, 3325, 4, 6, 0, 2, 5, 3326, 0, 3323, 3325, 3325, 3324, 5, 3323, 0, 3325, 1, 1, 3325, 3323, 6, 3327, 6, 3326, 3328, 3323, 3328, 3324, 6, 3324, 3326, 3323, 3323, 1, 3324, 3, 3325, 3327, 4, 1, 5, 6, 5, 3327, 0, 5, 3323, 5, 2, 0, 3324),
      (1, 0, 3325, 4, 3325, 1, 3324, 4, 3328, 1, 4, 3324, 3324, 3323, 3, 3324, 4, 5, 0, 3328, 3323, 3324, 3326, 5, 3326, 3326, 6, 3326, 3327, 3327, 3327, 2, 3326, 3325, 0, 2, 3323, 0, 3327, 3325, 3, 3323, 3327, 0, 3327, 3323, 6, 6, 3325, 3325, 3323, 3327, 1, 3323, 3324, 3328, 3324, 3323, 5, 3327, 3326, 3, 3323, 3325)),
     ((2, 6, 4, 1, 6, 3328, 4, 3324, 3328, 3324, 3323, 4, 3324, 3325, 3, 4, 3328, 4, 4, 1, 3327, 3323, 3328, 3327, 3323, 0, 1, 3326, 3328, 3328, 3323, 3328, 3328, 3325, 1, 3323, 4, 3325, 3327, 5, 1, 3324, 4, 3324, 3323, 1, 3323, 3323, 1, 4, 3324, 3326, 6, 3326, 3324, 4, 3, 3327, 6, 3, 5, 3, 3, 4),
      (1, 4, 3328, 3328, 1, 1, 3324, 0, 3325, 3324, 3, 3, 3324, 4, 3323, 1, 3327, 1, 3324, 4, 3323, 2, 2, 3323, 3323, 0, 3327, 3324, 3327, 3327, 4, 3324, 3323, 0, 3325, 5, 3326, 3328, 0, 3326, 3323, 3325, 3, 1, 0, 3325, 3327, 4, 3327, 3324, 3326, 3325, 3325, 3323, 3323, 3323, 3323, 5, 3327, 5, 1, 3327, 3324, 3)),
     ((6, 4, 6, 3324, 3327, 3, 3325, 6, 3324, 2, 6, 6, 5, 3, 3323, 3323, 1, 1, 5, 3323, 1, 3327, 3, 1, 3324, 3325, 3, 3325, 3328, 3323, 4, 3328, 3324, 4, 3324, 5, 3326, 4, 3325, 3, 6, 6, 3324, 3325, 3324, 0, 3323, 3325, 0, 4, 0, 2, 3328, 1, 3325, 1, 6, 6, 3326, 5, 3, 3328, 5, 3326),
      (5, 3, 0, 2, 4, 4, 3323, 3328, 1, 2, 2, 3328, 3325, 3327, 3327, 3, 2, 3326, 1, 3327, 3326, 1, 3326, 3325, 3326, 3328, 3324, 1, 3324, 3326, 5, 2, 3323, 6, 6, 3328, 5, 3328, 3324, 3326, 3324, 3326, 3323, 3324, 3327, 4, 5, 3324, 3, 2, 3326, 3326, 3, 3324, 3325, 5, 3, 3328, 3327, 3326, 3325, 6, 3328, 0)),
     ((0, 6, 3, 3326, 3, 2, 2, 3327, 4, 3328, 2, 3, 3, 4, 3325, 3327, 3326, 5, 3323, 3327, 3325, 2, 2, 3326, 3, 3326, 3327, 3326, 0, 3326, 3323, 1, 0, 3324, 6, 3325, 0, 0, 2, 2, 6, 6, 3324, 3326, 3326, 5, 3328, 2, 3323, 3326, 5, 4, 3325, 0, 5, 3324, 0, 5, 0, 3327, 1, 2, 3324, 6),
      (6, 3327, 4, 1, 5, 1, 4, 3326, 3324, 3326, 4, 3326, 2, 3326, 3325, 3326, 3327, 3323, 3326, 3327, 0, 3327, 3324, 3326, 3326, 3325, 3324, 3326, 3323, 2, 3323, 6, 2, 4, 3328, 3327, 3323, 0, 5, 3323, 3326, 3324, 4, 3324, 3328, 3328, 3328, 3325, 3328, 2, 3327, 5, 3323, 5, 5, 0, 3324, 3328, 5, 5, 6, 3327, 3324, 3325)),
     ((3324, 3325, 3323, 3, 3327, 4, 3328, 3325, 2, 3323, 3, 3328, 3325, 3, 3328, 2, 6, 2, 1, 3323, 3324, 6, 1, 3323, 0, 4, 3325, 3, 4, 5, 6, 3326, 5, 4, 5, 3323, 2, 3326, 5, 3323, 5, 3323, 3324, 6, 3324, 6, 6, 3, 5, 2, 6, 3328, 3327, 6, 5, 3324, 3324, 0, 3324, 3325, 0, 3323, 4, 3),
      (2, 1, 3325, 2, 3327, 3323, 3326, 5, 3, 3326, 3326, 1, 3326, 6, 1, 6, 1, 3327, 4, 5, 1, 1, 3327, 1, 3324, 5, 2, 5, 3325, 3, 2, 3328, 3325, 3323, 0, 3325, 3326, 3327, 3327, 3323, 3, 3327, 3323, 4, 3327, 5, 3327, 0, 0, 2, 3, 3327, 3, 0, 6, 3, 5, 3, 3323, 5, 3, 1, 5, 3323)),
     ((3325, 3325, 3323, 3328, 3328, 5, 4, 3326, 3327, 6, 3323, 0, 6, 4, 3326, 3324, 3, 2, 6, 3323, 2, 3328, 1, 6, 6, 3327, 3, 6, 3, 3, 6, 4, 3324, 3, 4, 5, 1, 2, 3323, 3326, 3325, 0, 3326, 3324, 1, 3, 3324, 1, 0, 3327, 2, 4, 3323, 1, 3, 6, 2, 6, 3325, 3324, 3325, 5, 3325, 3325),
      (6, 5, 2, 3327, 3326, 3323, 3327, 3323, 6, 3, 3328, 3328, 3327, 6, 3323, 0, 6, 2, 3327, 3324, 6, 5, 5, 3325, 6, 4, 3323, 4, 3327, 3325, 3323, 3323, 3326, 3328, 3323, 3328, 0, 3327, 2, 3323, 2, 3326, 0, 3328, 3328, 5, 2, 5, 3324, 3325, 3328, 0, 3, 5, 3326, 3326, 3328, 1, 3, 3327, 6, 5, 3327, 0)),
     ((3326, 2, 0, 6, 3323, 6, 0, 3328, 0, 5, 3325, 6, 3326, 3324, 3323, 3328, 5, 4, 6, 3323, 5, 3323, 3326, 3323, 1, 0, 3327, 2, 3324, 3328, 2, 5, 3327, 3, 3, 3324, 3325, 3328, 4, 3, 3324, 0, 3324, 4, 0, 1, 3324, 6, 3326, 3324, 3326, 3326, 3326, 4, 5, 3328, 3327, 0, 3324, 5, 4, 2, 5, 2),
      (3327, 3, 2, 4, 3, 4, 5, 6, 3324, 4, 3324, 1, 2, 3, 3326, 3324, 1, 3323, 3323, 3323, 3326, 3323, 3326, 3323, 3328, 3327, 3328, 3323, 3326, 3326, 5, 3327, 3324, 6, 5, 2, 0, 3325, 0, 3, 5, 1, 0, 0, 3326, 3327, 1, 3326, 3323, 3327, 3325, 3328, 0, 3328, 6, 3327, 5, 3325, 3323, 5, 3323, 3327, 3327, 3324)),
     ((3326, 3324, 5, 0, 1, 3326, 3326, 6, 3, 4, 3327, 5, 3326, 5, 5, 5, 3327, 3, 3, 3326, 3328, 3327, 2, 3327, 5, 2, 3, 3324, 0, 6, 3323, 3328, 2, 5, 3327, 6, 3324, 6, 3326, 3327, 3324, 2, 3, 3, 3323, 3324, 2, 3328, 3323, 5, 0, 6, 1, 0, 3323, 3326, 1, 4, 3323, 6, 3, 3328, 3324, 5),
      (4, 3328, 6, 3327, 3323, 0, 3, 3326, 3325, 2, 5, 6, 2, 0, 3325, 3, 3327, 1, 6, 5, 2, 0, 3328, 4, 6, 3328, 3327, 6, 3, 6, 3327, 3327, 3323, 1, 3325, 3323, 3323, 6, 3324, 0, 3323, 3323, 3324, 5, 3328, 6, 3, 5, 6, 3324, 3, 2, 5, 3327, 3, 3, 1, 1, 6, 3, 3, 3324, 3326, 2)),
     ((3324, 3324, 3324, 0, 2, 3323, 3326, 3327, 3, 1, 3324, 3326, 3325, 3324, 5, 5, 1, 3326, 3, 5, 2, 5, 3, 6, 3327, 1, 3325, 5, 3, 1, 6, 0, 3323, 2, 2, 3326, 5, 3, 6, 5, 4, 3324, 4, 3324, 4, 3325, 3, 3, 4, 0, 6, 4, 3325, 0, 2, 3323, 3327, 3328, 3328, 3326, 5, 2, 2, 3324),
      (3324, 6, 0, 1, 1, 1, 5, 2, 0, 3326, 3323, 3326, 5, 1, 3324, 3326, 5, 5, 1, 3327, 2, 3326, 5, 6, 1, 1, 6, 5, 3325, 5, 6, 3323, 3325, 3328, 3323, 3323, 0, 3324, 3326, 3326, 3323, 4, 0, 3324, 6, 3325, 2, 1, 4, 3327, 3324, 3325, 0, 3328, 6, 3325, 4, 6, 3323, 3327, 1, 3323, 4, 4)),
     ((3327, 3325, 1, 5, 1, 6, 4, 5, 6, 4, 6, 4, 6, 3324, 6, 3324, 3327, 3326, 1, 3, 3325, 1, 2, 3328, 3325, 6, 3327, 4, 6, 1, 3325, 1, 3326, 3328, 3323, 3323, 5, 0, 2, 3323, 3328, 3326, 1, 1, 5, 3326, 6, 1, 3325, 3324, 2, 0, 3324, 3327, 3324, 3326, 3323, 2, 3327, 1, 5, 3327, 5, 5),
      (3324, 4, 5, 1, 3325, 4, 5, 6, 3326, 2, 6, 1, 6, 1, 2, 0, 4, 3325, 1, 4, 0, 3327, 5, 1, 0, 2, 3324, 6, 3324, 3, 3324, 3324, 3, 2, 2, 5, 6, 1, 3326, 1, 5, 1, 5, 3325, 4, 3327, 3324, 3325, 3327, 0, 3, 6, 3327, 3, 5, 3323, 3323, 1, 3324, 3327, 3, 3323, 3323, 3326)),
     ((1, 6, 3, 6, 3328, 6, 3, 3326, 0, 3324, 5, 3327, 6, 6, 6, 2, 5, 3323, 3326, 5, 5, 2, 3324, 3323, 2, 3324, 5, 4, 5, 5, 2, 3327, 3327, 3327, 3, 3327, 5, 6, 3327, 3325, 3326, 6, 1, 4, 3326, 6, 3326, 2, 6, 1, 4, 5, 3323, 1, 3328, 3323, 3325, 5, 3328, 3324, 3323, 4, 3323, 3324),
      (4, 3325, 3328, 6, 3, 5, 1, 3324, 6, 5, 0, 2, 3326, 0, 3325, 3326, 6, 3324, 0, 3325, 3328, 3327, 3325, 4, 3324, 3328, 3325, 2, 3, 3326, 1, 0, 3325, 6, 3327, 5, 3323, 3, 1, 5, 3, 6, 2, 6, 4, 0, 6, 3, 3326, 3325, 3328, 0, 3324, 5, 3327, 3325, 3327, 5, 3326, 3323, 3324, 1, 3326, 2)),
     ((6, 5, 3327, 5, 6, 3, 6, 6, 0, 3327, 6, 5, 3, 6, 4, 3323, 2, 3325, 3326, 3325, 1, 4, 3326, 3323, 4, 6, 3323, 2, 3328, 6, 3323, 0, 1, 6, 3327, 1, 3326, 3327, 5, 3323, 3324, 3326, 4, 3326, 1, 3323, 4, 3324, 6, 6, 2, 3325, 3328, 3327, 6, 3325, 2, 3325, 3324, 3, 5, 3327, 4, 3328),
      (2, 5, 5, 5, 3324, 3328, 3328, 3328, 3328, 3327, 2, 3325, 1, 0, 3327, 3324, 3327, 3325, 6, 3327, 3327, 3328, 3323, 2, 3324, 4, 0, 3325, 3326, 6, 3328, 6, 3323, 4, 2, 5, 3327, 2, 4, 4, 0, 2, 3326, 3, 3328, 6, 6, 4, 5, 1, 3323, 3323, 3327, 3324, 6, 1, 3323, 5, 3325, 1, 1, 3323, 3326, 3328)),
     ((1, 6, 3328, 1, 0, 3328, 3324, 3323, 0, 6, 4, 3323, 6, 3327, 6, 3325, 3323, 5, 0, 3325, 3327, 4, 4, 0, 3323, 3324, 3328, 3327, 2, 3324, 3327, 3325, 0, 3328, 5, 3324, 6, 3324, 3327, 5, 3324, 3326, 3326, 6, 3326, 3, 3327, 3326, 5, 2, 0, 3327, 3323, 2, 3323, 3324, 3326, 3325, 3326, 2, 3, 3323, 3325, 4),
      (3326, 6, 6, 3, 1, 0, 6, 1, 4, 3327, 0, 3325, 6, 5, 3, 3323, 3324, 3323, 3323, 1, 3324, 3323, 5, 3326, 4, 3325, 3324, 3325, 1, 3, 6, 3325, 2, 4, 3325, 3324, 3327, 3327, 3327, 3, 5, 3324, 3325, 3326, 2, 5, 4, 6, 3325, 5, 3327, 6, 3323, 3326, 3, 5, 3325, 3325, 3327, 0, 3328, 2, 3323, 3)),
     ((2, 4, 3, 5, 3327, 3326, 1, 3323, 3325, 3327, 3, 3325, 3323, 3323, 3327, 3328, 3327, 6, 3326, 6, 3327, 1, 3327, 3325, 3, 3328, 6, 3327, 4, 6, 6, 3323, 3327, 0, 6, 6, 1, 3323, 6, 5, 4, 5, 4, 2, 3326, 5, 3327, 4, 3323, 3324, 4, 3326, 3328, 3323, 3326, 3328, 3326, 4, 4, 3, 3324, 3324, 5, 4),
      (0, 3325, 3324, 3325, 3324, 3327, 1, 3325, 3327, 3325, 1, 3326, 3325, 6, 5, 0, 3324, 3, 3325, 3326, 0, 3328, 1, 4, 5, 0, 6, 5, 5, 2, 5, 6, 6, 0, 2, 3323, 3325, 3323, 3324, 3324, 3327, 3325, 5, 3324, 3326, 3328, 3328, 3323, 3324, 5, 1, 2, 4, 6, 4, 1, 5, 4, 3327, 6, 3323, 0, 3325, 4)),
     ((6, 3323, 4, 0, 6, 3323, 3323, 3323, 5, 3324, 3327, 3325, 2, 3323, 3324, 3327, 3326, 3326, 3, 3326, 0, 4, 6, 3327, 3324, 2, 3, 3327, 3324, 5, 3327, 0, 3323, 6, 3326, 4, 3324, 4, 3325, 5, 2, 6, 3323, 3323, 0, 3324, 6, 3323, 4, 3324, 5, 3324, 3323, 3323, 3327, 0, 3, 3326, 4, 5, 6, 3323, 0, 5),
      (3323, 3324, 3328, 3328, 3328, 0, 1, 0, 3327, 3323, 1, 1, 3326, 2, 0, 1, 3323, 2, 3324, 1, 3, 1, 5, 1, 3328, 4, 3325, 2, 3, 3328, 5, 5, 3327, 0, 0, 2, 3328, 3326, 0, 1, 3325, 3325, 3324, 3324, 3323, 3325, 1, 3, 3325, 3324, 3328, 3326, 3327, 0, 4, 1, 3327, 6, 3326, 3328, 3, 3327, 5, 6)),
     ((3325, 1, 5, 0, 0, 3323, 3328, 3323, 3323, 3326, 3327, 3324, 3324, 2, 0, 3324, 3324, 3323, 0, 1, 2, 5, 4, 6, 3, 3326, 1, 3327, 6, 3323, 2, 3328, 3328, 3324, 6, 1, 3328, 6, 6, 3325, 3326, 4, 3324, 3328, 2, 1, 3323, 5, 3326, 6, 3326, 5, 3326, 6, 3, 5, 3323, 3327, 6, 2, 1, 0, 3, 3324),
      (4, 3323, 3324, 6, 3, 3324, 3324, 3324, 1, 3327, 3326, 3323, 5, 0, 3323, 3328, 3328, 3326, 2, 1, 3328, 3, 3327, 3327, 3323, 1, 4, 3327, 6, 3327, 3, 6, 4, 3325, 3327, 3323, 2, 3325, 1, 3323, 3324, 3324, 1, 3327, 3327, 3327, 3327, 3325, 3325, 3324, 3327, 2, 5, 3328, 4, 6, 3328, 0, 0, 6, 3327, 0, 0, 6)),
     ((3, 3328, 2, 4, 1, 3326, 0, 3327, 3327, 3326, 3, 6, 3324, 0, 3324, 3327, 5, 3323, 3327, 3325, 0, 3325, 6, 6, 5, 3328, 3327, 4, 5, 2, 4, 3328, 3326, 3326, 3327, 3325, 3327, 5, 3, 6, 0, 2, 4, 3323, 6, 6, 5, 3325, 5, 3328, 3326, 3328, 6, 3324, 2, 1, 4, 2, 1, 5, 3326, 5, 0, 3328),
      (3328, 1, 3326, 6, 3323, 3327, 3324, 3325, 2, 3, 0, 3324, 2, 3328, 3326, 0, 3328, 3328, 2, 0, 5, 6, 0, 2, 6, 0, 4, 6, 6, 3, 4, 1, 0, 3323, 2, 3325, 3325, 3323, 5, 2, 3325, 3324, 5, 3324, 4, 3325, 6, 3327, 1, 0, 3323, 3, 3326, 6, 6, 6, 3327, 6, 4, 3, 2, 3327, 2, 1)),
     ((2, 0, 3323, 3, 5, 3325, 3324, 3327, 1, 3328, 3325, 0, 3326, 3, 3323, 0, 3327, 3325, 0, 3326, 3325, 3, 3323, 4, 3, 5, 3327, 1, 4, 3328, 4, 3327, 4, 2, 0, 3327, 2, 1, 4, 3323, 6, 3326, 1, 6, 3326, 3, 6, 3327, 3323, 6, 3324, 3324, 1, 5, 3323, 3327, 3328, 1, 3325, 5, 5, 6, 1, 0),
      (2, 5, 3323, 3328, 2, 3325, 3323, 3327, 6, 3326, 3325, 4, 3326, 2, 1, 3324, 3323, 3327, 3324, 3324, 3324, 3325, 6, 4, 2, 4, 4, 0, 5, 0, 4, 2, 3323, 4, 3323, 3324, 4, 3, 3328, 3326, 0, 3323, 3325, 3325, 3, 3326, 3327, 3, 6, 3328, 3325, 3327, 3323, 1, 3328, 1, 6, 5, 2, 3326, 0, 2, 3323, 3)),
     ((3323, 5, 3323, 4, 3323, 3328, 1, 3, 3326, 6, 1, 3326, 3327, 3328, 5, 4, 3328, 3, 3327, 3323, 2, 3326, 3323, 3327, 3326, 3326, 1, 6, 3, 3323, 3324, 3326, 6, 3324, 3324, 3328, 0, 3325, 3325, 0, 2, 3323, 4, 3324, 2, 6, 3325, 3328, 0, 2, 3323, 4, 3324, 2, 3328, 6, 6, 3328, 3327, 3, 3327, 3325, 3328, 3323),
      (4, 5, 0, 4, 3, 3327, 3324, 2, 5, 1, 2, 0, 3324, 5, 1, 2, 0, 3, 4, 3326, 3325, 6, 3323, 3, 4, 6, 3327, 5, 6, 3324, 3328, 3323, 3326, 2, 6, 1, 1, 3, 4, 6, 3324, 2, 5, 4, 3325, 6, 2, 3325, 3325, 0, 3, 6, 2, 5, 2, 3325, 0, 3, 3325, 3326, 3326, 3324, 6, 1)),
     ((3323, 4, 3327, 2, 3326, 5, 3327, 2, 3324, 3328, 0, 2, 4, 5, 3324, 3, 3327, 3327, 6, 0, 4, 3325, 5, 3, 3325, 4, 5, 1, 3323, 3323, 1, 6, 3324, 3328, 6, 6, 1, 3323, 3328, 3324, 0, 5, 6, 3325, 6, 5, 3325, 6, 3328, 5, 3325, 3, 3326, 2, 2, 3328, 3325, 3324, 5, 1, 3328, 0, 4, 3325),
      (3324, 2, 3323, 2, 3323, 3328, 3328, 2, 3328, 3326, 6, 3328, 3325, 3323, 3323, 3325, 5, 2, 0, 3326, 3326, 3325, 3327, 5, 1, 4, 3324, 1, 3, 5, 3323, 4, 3325, 5, 3323, 0, 3326, 3325, 3, 4, 3324, 3325, 3325, 3323, 5, 3325, 3323, 3323, 3, 3323, 3324, 2, 3325, 3325, 3328, 3327, 3327, 4, 3, 2, 1, 1, 3, 6)),
     ((3323, 1, 3, 3327, 6, 3323, 1, 3326, 3325, 3328, 3325, 2, 3323, 3325, 3327, 0, 2, 3323, 3327, 3326, 3328, 5, 0, 3326, 6, 5, 5, 6, 5, 3325, 3325, 3324, 1, 3323, 3323, 3, 1, 3324, 3323, 1, 5, 5, 3, 3328, 2, 5, 5, 3324, 2, 6, 4, 0, 4, 3, 2, 3, 0, 1, 5, 5, 6, 3327, 3326, 2),
      (3326, 3324, 3328, 3325, 3, 3, 3326, 0, 4, 3328, 3325, 3323, 0, 0, 0, 3323, 3326, 3327, 3323, 3328, 6, 3325, 3324, 0, 3, 3327, 2, 6, 0, 6, 5, 3325, 6, 1, 3326, 3324, 4, 0, 3323, 3324, 3, 1, 3324, 3323, 3323, 3, 3324, 3324, 3327, 1, 3328, 3, 3325, 5, 3323, 4, 6, 0, 6, 6, 3326, 3324, 3, 1)),
     ((3328, 0, 3326, 5, 3326, 3, 4, 5, 3327, 0, 5, 3324, 3326, 3325, 3323, 0, 3326, 3328, 3328, 3328, 3326, 3326, 3326, 5, 3323, 6, 3326, 2, 5, 6, 3323, 0, 2, 2, 3327, 3328, 4, 3328, 0, 3325, 6, 3327, 3328, 1, 3328, 3328, 3, 5, 4, 3, 6, 6, 3325, 3324, 3323, 3, 3325, 3328, 3323, 3325, 4, 6, 3325, 6),
      (3326, 3324, 3326, 0, 3323, 3328, 4, 3325, 3, 2, 3326, 3326, 3325, 3327, 3325, 5, 3324, 3326, 2, 3323, 1, 3326, 3325, 3323, 3, 5, 3323, 1, 1, 5, 3328, 4, 0, 3325, 3324, 0, 3328, 3327, 3325, 3327, 3323, 5, 6, 3326, 3, 3323, 6, 3324, 3327, 3328, 5, 3324, 2, 2, 3325, 3, 3327, 1, 1, 3323, 0, 2, 0, 3326)),
     ((4, 3323, 3324, 0, 3327, 3326, 5, 3325, 6, 3327, 3328, 3323, 4, 6, 3327, 3325, 3324, 3328, 3328, 3323, 3324, 3328, 3, 3, 3328, 3, 3, 6, 3326, 6, 3327, 3324, 1, 3327, 3327, 3324, 3325, 1, 3328, 2, 3328, 3328, 3328, 1, 5, 4, 3326, 6, 6, 3323, 5, 3325, 6, 4, 6, 3323, 3323, 3326, 5, 3326, 5, 6, 3323, 3326),
      (3323, 1, 3323, 4, 3327, 3324, 2, 3323, 3323, 3326, 3328, 3324, 3324, 3328, 3324, 1, 1, 3327, 3325, 3327, 3327, 3326, 3327, 6, 3328, 3323, 0, 3324, 1, 5, 3, 6, 3326, 2, 3327, 3324, 3323, 3325, 3324, 3324, 3327, 6, 5, 3325, 3324, 3325, 3323, 3325, 6, 3, 3325, 3327, 3326, 3328, 3, 3, 3324, 3327, 5, 3327, 3327, 1, 3, 0)),
     ((3326, 3326, 5, 3, 5, 3325, 2, 2, 2, 3325, 3, 3328, 1, 0, 6, 3, 0, 5, 4, 0, 4, 1, 6, 3328, 4, 1, 4, 3327, 5, 3325, 3325, 3323, 3325, 5, 3, 6, 5, 3328, 2, 2, 5, 1, 0, 3, 3, 3328, 3325, 6, 3323, 3325, 4, 0, 3328, 3326, 2, 5, 6, 3328, 5, 0, 6, 2, 3328, 4),
      (2, 2, 4, 3327, 5, 5, 3325, 2, 3, 1, 4, 3325, 2, 3, 6, 3327, 0, 2, 3327, 6, 4, 6, 1, 6, 2, 4, 5, 4, 3327, 3323, 3328, 0, 3326, 5, 3324, 3, 6, 4, 4, 3328, 3327, 3, 1, 2, 3, 3328, 0, 3328, 4, 3323, 2, 0, 3324, 3324, 2, 4, 2, 4, 0, 2, 3328, 2, 3327, 4)),
     ((3325, 3325, 3327, 3323, 0, 2, 3323, 0, 3327, 6, 3323, 4, 4, 3, 6, 2, 5, 6, 6, 3323, 0, 2, 3323, 3328, 3323, 0, 4, 0, 3324, 5, 3328, 3328, 0, 3327, 6, 0, 4, 6, 3323, 3328, 3328, 3, 3328, 6, 3328, 3323, 3323, 1, 4, 3324, 4, 0, 3323, 3, 3326, 6, 3327, 4, 3327, 4, 3325, 2, 4, 3323),
      (2, 3323, 4, 3, 3325, 1, 4, 1, 5, 1, 0, 2, 5, 2, 6, 6, 3323, 2, 3327, 3328, 1, 3328, 6, 2, 5, 6, 3326, 3326, 3324, 3324, 2, 3324, 1, 2, 4, 3327, 3323, 0, 4, 6, 0, 6, 1, 6, 5, 3325, 5, 4, 3327, 3326, 5, 1, 3326, 4, 6, 3, 6, 6, 6, 6, 3323, 1, 3324, 3327)),
     ((3323, 3323, 3, 6, 3324, 3324, 3323, 3323, 3325, 3, 3, 3326, 3327, 3325, 2, 3328, 3327, 3, 3323, 3327, 3328, 6, 3326, 3323, 3324, 3, 3328, 0, 3323, 6, 3326, 3, 0, 3324, 5, 3327, 3324, 3327, 3327, 6, 3, 3326, 3323, 4, 3, 3324, 5, 6, 6, 3325, 1, 5, 3324, 5, 5, 1, 3323, 3327, 4, 3, 3327, 5, 3323, 3324),
      (2, 4, 3326, 3323, 5, 3323, 3323, 3327, 3328, 3326, 3327, 0, 4, 1, 3, 3323, 2, 3324, 3325, 3325, 3324, 6, 1, 1, 1, 3325, 3323, 3325, 0, 0, 3323, 3325, 3323, 3325, 3324, 3324, 3325, 2, 3325, 3326, 1, 3324, 3323, 3324, 6, 3328, 3327, 4, 3326, 1, 5, 3325, 3324, 4, 5, 1, 3324, 3326, 3327, 3325, 3327, 3325, 5, 2)),
     ((3323, 5, 4, 3323, 3326, 3328, 3328, 3, 3323, 5, 3325, 2, 3327, 6, 1, 6, 3, 3325, 6, 3, 3327, 2, 4, 1, 4, 3325, 4, 2, 3327, 3324, 3323, 2, 3324, 3328, 3, 3325, 3324, 2, 1, 6, 2, 1, 3325, 3327, 5, 5, 0, 1, 3323, 3328, 3, 3328, 3323, 3, 3323, 3325, 3327, 4, 5, 4, 3323, 3327, 3, 2),
      (3, 5, 2, 3323, 5, 4, 2, 3323, 3327, 6, 6, 3326, 6, 3328, 3, 3328, 4, 5, 1, 3328, 0, 4, 0, 3, 3325, 3325, 3328, 3, 6, 3, 3323, 3323, 3325, 5, 1, 4, 3326, 3325, 2, 0, 6, 4, 5, 4, 5, 2, 3323, 3327, 5, 0, 5, 3327, 0, 4, 5, 3325, 3328, 2, 3, 4, 3326, 6, 3327, 5)),
     ((6, 3327, 3327, 3326, 1, 0, 3328, 0, 3323, 3328, 4, 5, 3326, 3326, 3328, 3324, 3325, 6, 2, 3324, 3325, 6, 5, 3324, 6, 3323, 3327, 3323, 3325, 3328, 3327, 1, 0, 3328, 3325, 3323, 2, 3327, 3323, 2, 3326, 2, 5, 3323, 3323, 3324, 3325, 3323, 3, 5, 5, 3326, 2, 6, 3326, 3326, 1, 4, 3328, 6, 3324, 2, 3, 5),
      (3, 3325, 4, 3324, 3324, 3323, 1, 3328, 3323, 3326, 3326, 2, 5, 5, 3326, 3328, 3326, 0, 3327, 3326, 3327, 3323, 4, 0, 3325, 3324, 2, 2, 3328, 3323, 3326, 6, 2, 1, 3327, 3326, 3324, 3328, 3325, 3326, 3327, 2, 1, 3325, 3324, 2, 3323, 2, 3323, 3324, 3326, 6, 3323, 0, 5, 3325, 3326, 3, 3327, 3327, 3328, 3324, 3324, 6)),
     ((3, 6, 3325, 3324, 3326, 0, 0, 3326, 3, 3, 4, 3324, 5, 3327, 3, 3, 0, 3324, 3326, 4, 1, 5, 3323, 2, 1, 3323, 3324, 3328, 3326, 2, 3328, 3, 3325, 3, 4, 3323, 3325, 3328, 3327, 3323, 3325, 3323, 3325, 5, 6, 3324, 4, 6, 0, 5, 3326, 2, 2, 6, 3, 3326, 6, 6, 3327, 6, 0, 3325, 5, 3325),
      (3323, 2, 3323, 6, 3325, 3328, 2, 3326, 0, 3323, 4, 3324, 3323, 3325, 3323, 3327, 3325, 3323, 3326, 3327, 4, 3324, 3, 3328, 3326, 1, 3326, 3327, 3, 1, 0, 3327, 0, 3326, 3328, 3326, 3327, 3326, 3323, 3323, 6, 3323, 3323, 5, 6, 3324, 3323, 3324, 3324, 3327, 3, 3325, 3324, 5, 4, 3324, 3327, 3324, 3324, 4, 3328, 3328, 3327, 3327))]


def send_vec(v):
    v = [(c if c < q // 2 else c - q) for c in v]
    p.sendline(str(v)[1:-1].encode())


for _ in range(5):
    c = int(p.recvline_startswith(b'challenge').split()[1].decode())
    r, e1 = D[c.bit_length() - 1]
    send_vec(r)
    send_vec(e1)

p.recvline()
flag = p.recvline(False)
print(flag)
print(hashlib.sha256(flag).hexdigest())