Hgame2025 writeup

Hgame2025 writeup（Crypto方向）

1.sieve

题目：

#sage
from Crypto.Util.number import bytes_to_long
from sympy import nextprime

FLAG = b'hgame{xxxxxxxxxxxxxxxxxxxxxx}'
m = bytes_to_long(FLAG)

def trick(k):
    if k > 1:
        mul = prod(range(1,k))   #阶乘
        if k - mul % k - 1 == 0:
            return euler_phi(k) + trick(k-1) + 1
        else:
            return euler_phi(k) + trick(k-1)
    else:
        return 1

e = 65537
p = q = nextprime(trick(e^2//6)<<128)
n = p * q
enc = pow(m,e,n)
print(f'{enc=}')
#enc=2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546

分析：

分析并结合Wilson定理可知，我们要求的是从1到e^2//6的欧拉函数之和加上这之间的素数个数。

联系题目我们就可以联想到筛法，然后就是写脚本，这里求欧拉函数之和时python脚本运行时间过长，并且把电脑搞得非常卡，于是就改成了C++。

解答

//(筛法求欧拉函数之和)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    uint64_t n = 715849728;
    vector<uint64_t> phi(n + 1);
    for (uint64_t i = 0; i <= n; ++i) 
    {
        phi[i] = i;
    }
    vector<char> is_prime(n + 1, 1);
    is_prime[0] = is_prime[1] = 0;
    vector<uint32_t> primes;
    primes.reserve(n / 20);             // 预估质数数量

    uint64_t total = 1;                 // φ(1) = 1

    for (uint64_t i = 2; i <= n; ++i) 
    {
        if (is_prime[i]) 
        {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        total += phi[i];                // 累加当前φ(i)

        for (uint32_t p : primes) 
        {
            if (p > n / i) break;       // 防止i*p溢出
            uint64_t m = i * p;
            is_prime[m] = 0;
            if (i % p == 0) 
            {
                phi[m] = phi[i] * p;
                break;
            } else 
            {
                phi[m] = phi[i] * (p - 1);
            }
        }
    }

    cout << "ans=" << total << endl;    //155763335410704472
    return 0;
}

from Crypto.Util.number import long_to_bytes
from sympy import nextprime
import gmpy2

e = 65537
k = e*e//6
sum_phi=155763335410704472  #上个脚本中求出的值
enc = 2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546

def sieve_prime(n: int) -> list:
    #厄拉托塞筛法
    if n < 2:
        return []
    elif n == 2:
        return [2]
    end = (n - 3) // 2
    is_prime = [True for _ in range(end + 1)]
    for i in range(3, int(pow(n, 0.5)) + 1, 2):
        k = (i - 3) // 2  
        if is_prime[k]:
            for j in range(i * i, n + 1, 2 * i):
                is_prime[(j - 3) // 2] = False
    return [2] + [2 * i + 3 for i in range(end + 1) if is_prime[i]]

prime_list = sieve_prime(k)
print("first 10 prime:", prime_list[:10])
print("last 10 prime:", prime_list[-10:])

print("num== ",len(prime_list))
trick_k = sum_phi + len(prime_list)

shifted = trick_k << 128
p=nextprime(shifted)
print("p== ",p)
n = p * p
phi = p * (p - 1)

d=gmpy2.invert(e,phi)
print(d)

m = pow(enc, d, n)
print(long_to_bytes(m))  #b'hgame{sieve_is_n0t_that_HArd}'

2.ezbag

题目：

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secrets import flag


list = []
bag = []
p=random.getrandbits(64)    
assert len(bin(p)[2:])==64 
for i in range(4):                              
    t = p
    a=[getPrime(32) for _ in range(64)]        
    b=0                                        
    for x in a:
        temp=t%2                               
        b+=temp*x                              
        t=t>>1                                
    list.append(a)                             
    bag.append(b)                              
print(f'list={list}')
print(f'bag={bag}')

key = hashlib.sha256(str(p).encode()).digest()  
cipher = AES.new(key, AES.MODE_ECB)             
flag = pad(flag,16)                            
ciphertext = cipher.encrypt(flag)              
print(f"ciphertext={ci

"""
list=[[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 367956082
bag=[123342809734, 118191282440, 119799979406, 128273451872]
ciphertext=b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'
"""

分析：

稍微变形了的背包密码，同时出现了四组背包。

构造格，但LLL算法格不出，这里用BKZ出结果了。

$$ [x_1,x_2,...,x_{64},-1]\\ \begin{bmatrix} 2 & 0 & 0 & \cdots & 0 & list[3][-1] & list[2][-1] & list[1][-1] &list[0][-1]\\ 0 & 2 & 0 & \cdots & 0 & list[3][-2] & list[2][-2] & list[1][-2] &list[0][-2]\\ \vdots & \vdots & \vdots & \ddots & \vdots &\vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 2 & list[3][0] & list[2][0] & list[1][0] &list[0][0]\\ 1 & 1 & 1 & \cdots & 1 & bag[3] & bag[2] & bag[1] & bag[0] \end{bmatrix}\\ =[2x_1-1,2x_2-1,...,2x_{64}-1,0,0,0,0] $$

解答：

import hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES

list=[[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 3679560821]]
bag=[123342809734, 118191282440, 119799979406, 128273451872]
ciphertext=b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'

L=Matrix(ZZ,65,68)
for i in range(64):
    L[i,i]=2
    L[i,-1]=list[0][-i-1]
    L[i,-2]=list[1][-i-1]
    L[i,-3]=list[2][-i-1]
    L[i,-4]=list[3][-i-1]
L[-1,:]=1
L[-1,-1]=bag[0]
L[-1,-2]=bag[1]
L[-1,-3]=bag[2]
L[-1,-4]=bag[3]
x=L.BKZ()
print(x[0])
p=''
for i in x[0][:64]:
    if i==1:
        p+='1'
    else:
        p+='0'
p=int(p,2)
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(flag)
#b'hgame{A_S1mple_Modul@r_Subset_Sum_Problem}\x06\x06\x06\x06\x06\x06'

3.suprimeRSA

题目：

from Crypto.Util.number import *
import random
from sympy import prime

FLAG=b'hgame{xxxxxxxxxxxxxxxxxx}'           #已知部分明文
e=0x10001                                   #e=65537

def primorial(num):                         #primorial的意思是所有小于或等于某个给定素数的素数的乘积。
    result = 1
    for i in range(1, num + 1):
        result *= prime(i)
    return result
M=primorial(random.choice([39,71,126]))     #M=小于等于39，71，126中随机一个数的素数的乘积

def gen_key():
    while True:
        k = getPrime(random.randint(20,40)) #20 <= k <= 40
        a = getPrime(random.randint(20,60)) #20 <= k <= 60
        p = k * M + pow(e, a, M)            #p=kM + 65537^a mod M
        if isPrime(p):                      #确保p是素数
            return p

p,q=gen_key(),gen_key()
n=p*q
m=bytes_to_long(FLAG)           
enc=pow(m,e,n)                              #简单RSA

print(f'{n=}')
print(f'{enc=}')

"""
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
"""

分析：

可以看到$p=kM+65537^a \mod M$,其中M 是前 n 个连续素数的乘积，n 是仅取决于所需密钥大小的常数，这种素数生成形式会受到ROCA攻击。

我这里直接使用ROCA的sagemath脚本进行解答，当然也可以使用neca工具。

解答：

from Crypto.Util.number import *
import gmpy2
## Coppersmith-howgrave
def coppersmith_howgrave(f, N, beta, m, t, R):
    #Check if parameters are within bounds
    assert 0 < beta <= 1, 'beta not in (0, 1]'
    assert f.is_monic(), 'f is not monic'

    #get delta and the matrix dimension
    delta = f.degree()
    n = delta * m + t

    #Building the polynomials
    fZ = f.change_ring(ZZ) #change the ring from Zmod(N) to ZZ
    x = fZ.parent().gen()  #make x a variable in ZZ
    f_list = [] 
    for ii in range(m):
        for j in range(delta):
            #We want them ordered that's we have N^(m-ii1) and fZ^ii
            f_list.append(((x*R)^j) * N^(m-ii) * fZ(x*R)^(ii)) #the g_{i,j}
    for ii in range(t):
        f_list.append((x*R)^ii * fZ(x*R)^m) #the h_i

    #Build the lattice
    B = matrix(ZZ, n) # n = delta * m + t
    for ii in range(n):
        for j in range(ii+1):
            B[ii, j] = f_list[ii][j]

    #LLL it
    B_lll = B.LLL(early_red = True, use_siegel = True)

    #take the shortest vector to construct our new poly g
    g = 0
    for ii in range(n):
        g += x^ii * B_lll[0, ii] / R^ii

    #factor the polynomial
    potential_roots = g.roots()
    #print('potential roots:', potential_roots)

    #we don't need to do this Since our we test in our roca function
#     #test roots
#     roots = []
#     for r in potential_roots:
#         if r[0].is_integer():
#             res = fZ(ZZ(r[0]))
#             if gcd(N, res) >= N^beta:
#                 roots.append(ZZ(r[0]))
    #print('roots:', roots)
    return potential_roots
    #return roots
def roca(N, M_prime, g, m, t, beta):
    g = int(g)
    c_prime = discrete_log(Zmod(M_prime)(N), Zmod(M_prime)(g))
    ord_M_prime = Zmod(M_prime)(g).multiplicative_order()

    #search boundaries
    bottom = c_prime // 2 
    top =(c_prime + ord_M_prime) // 2 
    print('numbers to check',   top - bottom, ' between ', (bottom, top))


    #constants for coppersmith
    P.<x> = PolynomialRing(Zmod(N))
    epsilon = beta / 7
    X = floor(2 * N^beta / M_prime)

    #the search
    for i, a in enumerate(range(bottom, top)):
        if i % 1000 == 0: #count iterations
            print(i)

        #construct polynomial
        f = x + int((inverse_mod(M_prime, N)) * int(pow(g, a, M_prime)))

        #roots = f.small_roots(X, beta, epsilon) #coppersmith
        roots = coppersmith_howgrave(f, N, beta, m, t, X)
        #check solutions
        for k_prime, _ in roots:
            p = int(k_prime * M_prime) + int(pow(g, a, M_prime))
            if N % p == 0:
                return p, N//p
    return -1, -1
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
e=65537

def get_M1_m_t_values(key_size):
    print("111")
    if 512 <= key_size < 1024:
        m = 5
        M1=0x1b3e6c9433a7735fa5fc479ffe4027e13bea
    elif 1024 <= key_size < 2048:
        m = 4
        M1=0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
    elif 2048 <= key_size < 3072:
        m = 6
        M1=0x016928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
    elif 3072 <= key_size < 4096:
        m = 25
    else:
        m = 7
    return M1,m, m+1
M_prime,m, t = get_M1_m_t_values(512)
p, q = roca(n, M_prime, e, m, t, .5) 
assert(p*q==n)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
m=pow(enc,d,n)
print(long_to_bytes(m))

#b'hgame{ROCA_ROCK_and_ROll!}'

4.Intergalactic Bound

题目：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):  #曲线加法
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):  #曲线乘法
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


p = getPrime(96)
a = randint(1, p)
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p   #d=(a * x0^3 + y0^3 + 1)modp * (x0*y0)^-1 modp 
x = randint(1, p)
Q = mul_THCurve(x, G)   #Q=x*G
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()  #分析可知，目的就是求出x
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

分析：

上网搜索可知道，THCurve的形式

$$ ax^3+y^3+1=dxy $$

通过联立两个点，可以求出参数a,d。

然后想办法把曲线和点映射到椭圆曲线上，然后进行离散对数求解。

#sage
#THCurve曲线
from Crypto.Util.number import *
p = 55099055368053948610276786301       #模数p
G = (19663446762962927633037926740, 35074412430915656071777015320)  #已知点G
Q = (26805137673536635825884330180, 26376833112609309475951186883)  #已知点Q
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"   #密文
Gx,Gy=G     #提取G的x，y坐标
Qx,Qy=Q     #提取Q的x，y坐标

M=matrix(GF(p),[[-Gx**3,Gx*Gy],[-Qx**3,Qx*Qy]]) #构造2*2矩阵
y=vector(GF(p),[Gy**3+1,Qy**3+1])               #构造向量
a,d=M.solve_right(y)                            #求解线性方程组
print(a,d)

def calculate_coefficients(a, d):
    d_3 = d*inverse(3, p)%p             # d / 3
    tmp = a - d_3**3                    # a - d^3/27
    a0 = 1
    a1 = (-3 * d_3 * inverse(tmp, p))%p
    a3 = (-9 * inverse(tmp**2, p)) % p
    a2 = (-9 * d_3**2 * inverse(tmp**2, p))%p
    a4 = (-27 * d_3 * inverse(tmp**3, p))%p
    a6 = (-27 * inverse(tmp**4, p))%p

    return [a1, a2, a3, a4, a6]

aa = calculate_coefficients(a, d)
E = EllipticCurve(GF(p), aa)
def Herssian_to_Weierstrass(Point):
    x, y = Point
    u = ((-3 * inverse((a - d^3*inverse(27, p)), p)*x * inverse(d*x*inverse(3,p) - (-y) + 1, p))) % p
    v = ((-9 * inverse((a - d^3*inverse(27, p))^2, p) ) * (-y) * inverse(d*x*inverse(3,p) - (-y) + 1, p))%p
    return (u, v)


G = E(Herssian_to_Weierstrass(G))
Q = E(Herssian_to_Weierstrass(Q))
k = discrete_log(Q,G,operation='+')
print(k)
from Crypto.Cipher import AES
from hashlib import sha256
key=sha256(str(k).encode()).digest()
aes=AES.new(key,AES.MODE_ECB)
print(aes.decrypt(ciphertext))
"""
39081810733380615260725035189 8569490478014112404683314361
2633177798829352921583206736
b'hgame{N0th1ng_bu7_up_Up_UP!}\x04\x04\x04\x04'
"""

5.Ancient Recall

题目：

import random

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
print(Minor_Arcana)
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card)^k)
            if k == -1:
                YOUR_initial_FATE.append("re-"+card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue
print("Oops!lets reverse 1T!")

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")   #可知我们的目的是求YOUR_initial_FATE

YOUR_final_Value = Value
def Fortune_wheel(FATE):
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
    return FATEd

for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
    YOUR_final_FATE.append(tarot[i%78])
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

分析：

重点在于逆YOUR_initial_Value来求Value。

假设YOUR_initial_Value上一状态为a,b,c,d,e,则下一状态为a+b,b+c,c+d,d+e,e+a，所以逆向(a+b)-(b+c)+(c+d)-(d+e)+(e+a)//2=a来分别求上一状态的a,b,c,d,e，循环250次即可得到Value。

然后按条件拼接，即可得到flag。

解答：

#提取信息，分析所需量，再逆向分析如何求得所需值
Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana

Value=[]
YOUR_initial_FATE=[]
YOUR_final_Value=[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]

def re_Fortune_wheel(FATE):
    FATE[0] = (FATE[0]-FATE[1]+FATE[2]-FATE[3]+FATE[4]) // 2
    for i in range(4,0,-1):
        FATE[i]=FATE[i]-FATE[(i+1)%5]
    return FATE

for i in range(250):
    YOUR_final_Value = re_Fortune_wheel(YOUR_final_Value)

print(YOUR_final_Value)
Value=YOUR_final_Value

for i in Value:
    if i < 0:
        i = i ^ -1
        print(tarot[i])
        YOUR_initial_FATE.append("re-"+tarot[i])
    else:
        print(tarot[i])
        YOUR_initial_FATE.append(tarot[i])

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")
print(FLAG)
#hgame{re-The_Moon&re-The_Sun&Judgement&re-Temperance&Six_of_Cups}

6.SPICa

题目：

from Crypto.Util.number import getPrime, long_to_bytes,bytes_to_long
from secrets import flag
from sage.all import *

def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
flag=long_to_bytes(int(''.join(A[i])))
h = x*A

with open("data.txt", "w") as file:
    file.write(str(m) + "\n")
    file.write(str(p) + "\n")
    for item in h:
        file.write(str(item) + "\n")

其中data.txt内容为

(20469155492003601253253155553986803208931503654660710348720234166881649344003987262947017659012241047835048808070655285602897209239858740637878468266658899337230431317158339301884716019022543563824842749256770110913729930512649260804, 20061197539347089441548703718074268696982927733926399966893938885418017706383655096958576679109275153818455164325651467862757293092935593603331322600268652102317484783972009137643693799482954597365244794142123800753823881292602536480, 20449460766608148327819595887200586456206801278670684512632410913015490167503229582572274670752456522031099839096710051732743590814126659553219421423179332067697185796944680381658040503559588413035145948011713429631258754626251809510, 8694899395827009396141425992800033658778511870582271935710336140733986029271840480988700276909069199154936459475590420059851372448080387583101099303513327440738409895238607476203278712316251695883695113189088200686962847017765865251, 17498906738048927737996405866022970301450352038432120213930838838210038594926299429345553642022023354628862755091766856471553830387207275486875845428629363403317202957206875712023311105409026776222751170693634497194866213310044491948, 21299762658878585689792741107233334119508283391034542047533549461069861697448477916998731369486958411519583373650555867155855962437320409451328328158651213135213221691391305300586647640883613895924445303848945011091274872544725674414, 13858127090108368287746753156610976181884852029313352847097417269439999009242391680724254761571841185603751824488440165104153860614293879561204207753769517496283139692448618313378608851838592204671380865578837501521485226960295757131, 606107901015597672365982103377292862084693785965621044158858796689187941648736569096576321682310287031175045717941165527209428043020224184139162372752993919547870816012630061403517257290792929118011920477984972488980800309428929138, 16411347559169875469676322308290176281268630976465248631394286269278754960475346068565041099592979349979405282500383230219337689652572250821233598049978719348544790979587439571926076421698781802827344619141310395216702580071924399522, 6068129514673183503857587322729184998437772152551135658369680702133087671031996497962264049216246290631119377494262423727768860757742407967523061034172791840869912562774945606863954031992955819024967183759253919768822212999747782744, 16164073883659743891300469301841345466013040331496294498459841128458772221808605865298982279094019325297165362518613472961615756988375470180863560145427159107654477630571820179272488975849163426474631458599008988483395281798203200528, 6002652834833034433754084876025091748505356485760658745433173659340361267044983148952514860044218624345794714339893198968695437915359546317081144940354972707822464098838782671025813140852500245911841467802762732970205945777188441808, 17671459116121703756342696273829703490771262874572413082113674648287158047430332224637950989312667436860899021459708831070319841598164702019251450606454194564607879044661224315550514675652908609424461409598055757760711713272045049260, 9747804618981818225871997793952044666360767497788933437958387359050267555950930083105832397549316456989456304967283430526550121320745106610566272812291168897483422111931300711618308924263505765555678625775964949832562993340397250411, 21996324872073077242827998678880398901946388402016282475335311894567710762615152283467554531548297081386048827720410652120091647717684967177129064563480634873781425892452230881151261828547497099982851340353851101348946158575303726724, 20241128353291496652549108347619870477868850796680814076775175545760753973504668850036916374732720117160823389137853705825323283084380525440155558201212646427779126805749122859405488144164760267716232853839558997235342814050866837305, 13077656588899945700177181105263191868661064142860342679420184386239288545559858208951244435002966218243471420411045127025170552814160049125443370520964733258446212562129228879028530411822623695945498142516847896364762727423847457569, 7071530328065960890228453106008174199753371584339217118863740503556709237910489181283781927314970563878932442685277071347084354303239011911501455742585794028015220762730525765723336697380407902300153076264167533419216642860030224808, 22629252419865938253406009966521328587876533319128691562733593432194850726544929405088413178711982271889635298452313176698526192124305038839672198237812975135604141185210235559237447902236397265515318102940456244538398518752792480319, 5761459282176273118441944774799317407926062706007941700537400300748276958322349624237180755323800649847915919270480127859496807988229286598479624333300775674629423967322510405098758253061619727977005010935095672626407042895060271117, 13639378161376676791792650903794774452153629456935313476059754419699524574293526097694165098576687387486041665215960405733414879557245739928959501291435121608217008600392918108625339394853036499361173570509333162629246799468258136355, 1112221399019911081496513796105161716836267107501837651409516901292548472550496647130548616639784532217354650999157000279855022754714713097738729659495163953274484703014544784112610298442477231451271844048275322265529309125867188484, 12169161457053461668887038869671670176419946971662802953933166632081503259881448728851846332111194017082971192703865066066994163285010795828715477686499512514182295671281701232618183396077110570747529444745554508737426539555889099083, 11995511934849768905988062930456188671563166274831822681485210668895901448904842487096473591287554694509756168119490699415704136424403683840102743199694489304702405180406601329931714339410923612708808717358223085506757046662329629503, 13398528474737208001694948941230339341569100018647773619061861109738576104252100110443962069174319732180553417809151715735410100005179978063724591835291397314433312440421293983105825390167635459002960994550698739443052006993415149287, 21685721078976945602014626559051952462522937081933691461596237088189849657600841978193227429482306484131038624804443150311960061590035031144063153270840224125769186685588909207004132946200580900994078282900107456593588235003169921354, 21958932659990459795087732047584541007461325015275566949343681883128871386631056478783893068511478481080998508038344707524693059394150326940234855081823341566958854943322931261168562807321821084640569487228751077318094170704981650643, 18575326074968673858478938102428524301651676277226235867758079277741745360252102636120213638047957826270155136845469846718570511376252915803608625919614831191687134838436838444619000754054647327991321858217571418142823485948838843485, 21925408319719932198647415634718243407859189936679904356040860926584581042313625039619815019247876519120113207553707089727019778893587018690751305364116444902853587524322159019276550794203235986634843194549273092242442491313448819261, 21971769237171245388162249651275023141695912811218668240216220140957909617367793495291879198350993947099136765615466319867553659408044799043226321654345805093608432328775587162697826122051456089057951721736470156996789589476553105264, 11663665652950097951023874167071177053010440547278309973779798672676245675511213044752231769369800098096803991421401406373428185323198016967614776368177594490205473987491609921616943160817435319509156480489438442748695594208064506220, 8571733767532539591744305084238785438241372113715037973018068103542160069189369810177762541226540971969214853589594936813485292570840550755458909361226931687465304387382031888400449142008298116395068621612620111710861173184866936140, 7265641014493092305952899792692591083374900624337072072988050601814681241595404157641546803250164823540836286168102490427911208624069282838605171970733970339707601992725288390921333947799040016958678972693235850470014270495531454783, 18357683019971557309259589537387305852885630835264669230196131340413934504145103735168294472683744065174013315114812930463567210171038311927245433959034948205776155437226711665133074869096527958147737755278545942090787842643719386293, 11249630823936690987701184435328330983163223168635101989339377911187086984695870497253721111980469167097885275676200751043669504762094425614665999696903436973710297025883232331081137662411660725420763463582758176584701928482618894781, 21368417704130086095517329969849814675572842583190085389984103090985523417424304950647847490274582711171880575904265538743919551938416088883734546870704471113682032872096669715559005389583617506786922899538736534449123490145292870717, 14804820832711028510069420293910842363490984270818804823036282440726358025681287768311485300453811070788732988003156703771994750175077965636968452087698951366737342420716417627361539128824909909441296599842507450408639167847785653915, 10434593401661546638239269531721470859924069355256379358171970711096840647467279929406877589003350835919284031476862418858161422460097377292030151489346187334893502923880428533662123412400043690091517722265611541955158862687687083713, 24561443937015608720032402685089937637576551127866411331840220467266147984636152386876296689017192384827778734671122241130228223938051376943961096583907106197792850273311466092875658575488249813416281385686228639897799476137433072794, 18809508978562914770986641825424844673983326011247074637810890215219273029154108492496227431003955064765815763011903046546663244351135252376892253084070542641533081339319510865846592705413531461782231583683139065833462426977193323114, 1170325200926282785717575909542245218787696779459745550244912972650806869414330169502410895858680097983058617766512675739980564138645468322689195204967563486996177593733827238558844633804910336361508567070012845430162557209140318922, 9099530973344423583417798796448265698513331818761124724904157320649249490671748034442773080315290728734123593584766820587431677397350547048991745367397003023697063690573732401873466117208072387527262379544046633911232863713321651057, 6186545629812301877416853524734068114160450574994337117451587850263036761908385044092582990344042147406495912347645194115630652437606943173745789382845771049426443196019424697520894541338185145315971072044570777761063733877553713897, 18998733646999927412724741294417250892695086218116871981646202453146130670287277614970454171035798941213673467661889691048080971104465387696449499673490777958698659977825222598637449610957807490964624239691466685216040180063226979122, 2029035413823102082844939452656558074099805593476575872183225270283922006193130394920312821210960344438963206668816623318138806516660963226561860797911308864515985218753289984687939495010747187617345807068432674609822226022395002612, 1224334924830478941430540036421292246508644320238722677095883999889500298055876272715003687287887258419587507272093701524018402394087314059455381046013880303534485492492854314287356722191065404686438496257734600194353825409365914860, 15388830123476635874371535682309831543921413772062742670104698630978096538706065152811565310857194947646535508434358944071335015150277106407625487947363537743602712388716945337353159986787039117453435890006787376090096478885097896793, 10420053457335214342250034515332590797688043330675602278978659239127226996657084329075623919952172290482707420754415548245461942799120532008714972162634055331774926378534698291836555381029033314988303673575302329970048819875247229179, 12996570101872386881673806472032213506289839322758639432467242407197962401207255061640708238859358713382396645910306730272104173292864961862992132326434563495453537396958298185516874532647829493332700756725404634790257544413340701179, 11310001007421937130740204981515298136120181111962805563938085404289034278582061516301247258497064123414338657565189590291572623864937738084898059354622789358315367559028252287238789841719507080364615405563645390035528060316587102434, 7649920628929819175111413039486903286582015040923724934131761955991728816695088157076979052445031028120246103984026955901706105551535103282597498033031299709784514740469952209886314525277234547727841567842751063166501691717457807447, 8282767661876353703033480225670583969116738681062155629579190289397580081693316541581172493468366688140769336848827009811751348916039495262878858557738835369246631011150499694799485418164185557834866797870483707948444235231858169626, 10348065215991838887653401510489462098163485305574734545999066167894062235647455464256295931687781439097474305106334560598277885818537337701043155862614830925253569580192693898982318220593792046251125806231585329780902132617095557605, 11280967838102140047754377333560306350439648795137561969675963243081381329614099288939779782707558436465906221877404058208128414128559781592656246480955369758626788333375306898903783463959673000218175927160948442088191543414186131128, 11818929318729599124873943942145086021537273013997542692590943191077407938431043519607803418206555258214868688916182982805626078211252859082557253484889098137542929253460999852448424761935728458750150144937944771790308225982842690991, 5412969967721429139669566091956620099392941108847901064147423662180279827506836216754081912452764251675143575201910182189452840950356093575193249038624088662404268095962548749560674786705087512264668188729966989099888520624252744742, 17547356830409485892450749625199098509352498837601257846778404113094407637374346871392480581359187302653977880177675827091282945951962337410850311708191191160617963235512211658386260536823783677847875240999663432436509923589359888700, 8591887831833320840353196012263813111833998698446912587048628554388758958894496922493509033622609997670078612331200032453354380661501616871254995529921741954557910165239506265116743029658460390005477758921580324576966499950007047698, 24240608152025765890027400489331384103622640389639440068870645610439083379801706312111003846522258870692561041435455283169383633954853734692273153399247032151636823004018903792154640252253321042038217671452847628056591095001306376447, 18175238845322126323124732491839020080710712641999842067614816417084136046584647549081884372712146959940542383332663098640914320062272677772398521802893135140152503676658094543636706418059620569628737841646560680792630698212823857262, 10173862342693636575822816691492648273969020863129335004286001570695771568655492268044889845820019987659485915423299727906247618142386037838017456563194751538355466980296232841821674366111391576715244751705262011350337874749069345128, 17662887672308755659019635470333733858782416229711314422114693688837435216071004353298349767965595195988075045297248229654838457705997370106886962462023530886801849382037053188597909092732733084276903712706650614116210171460124448702, 12181524874770358579756085310138062154649043402053826988100381472344586613507823529632552464702544146652926312223695774383330894873770697330113566788363326971512196767946895811541430690548268356821209678371607727953997755838859126774, 11706994803516619040652442122624584733481017689525911051638928911326046116787740449573218360698003304996969933288041344857060888292758795645873721224079904632765180343552430630220956988207594755397804226083803193344994676329154327493, 8402357024978800071132055381314495648044905341576271257490683211086187354513127161690622199664304716824213610566304398546880266690789434430387528988209454626947248456097541304971867186772981230342257502227623573405137627210448823142, 13448814958668457684435846084935312650492724089658173841576258956348433114343610821298085173624638488238498589587758466360130338576374710075452327343150526934585873779496035836251602780112344762888078216555506331950896199565104006397, 23261851067858529243006512692328544765212250343687275283881011048369283487674444025254618141024372715313068675809489228084809200986696814193106301463035744067133170413056991023684452021013779169832348352784939483901536220423645197942, 2956461782787803412373184373521537264070982785668285831540757975387873992581341347760818916518443181764106275140479051787993901624417517942973131286068209774333764601237951091135348213764981692825938722977028088836454760352308033758, 3064486829635307133829604105999736772476219409968765985793477839736080127528728977191920114031725863884495929381858399046617507423360505816138935964152136380493092256651231150405966672895186096713142246153609317333657783049782151637, 10534802040612029540164483914330039254596233735171946359486562702340646071277688198935825397890574505178778613602867388545647349934716384895425051636497444634355043931879515977147131722039200347425808771386164417873392627039032929381, 16347587561440747118213871772022312563284652196262767324725458541109438659123670691624550736479719729504505614345452675461481177780240509736905011159885741573570625495043362505744257188005059869496076647939661464052864550390489436392, 932904564223742245423974397013211219322210230063409757135997988238048200833511900713764471854227396545059725844299953686973316362284758928784205613692959818986324717887966604059912158445010080457313116226499514698345116888739045201, 14155784829547910297069256239291885565427894076067719732956480982423435038774293432631990332881685973262975579857568134342058023430988483873438365184934853154265957089486695576174902453654823300612278786604052983027801579290159697757, 15059083507189045339756950559733288471657088114328896031836676598008347915133424684726963231247503783837186267424615012969099328203791879946151584653751983269080942728473598803375881811206929641186341006775658793858164370672638305414, 24050946955204789955533896427147712239350820947048633709193663894730552442910167865457955759634279229427681904250200157386924869101980949385253708656818328215342828689475987104598173819168455976517935776911361022122188385844429827861, 19717014416567816150124583987528154859466839421475505938275277134544233978125970101441724416647563320808697850421129369459770642837401448140038995613160278102100098417142249160683605942010321574730955450415122680160957836958254976336, 18341739025196342781439155614541180114644324261593971049987391428771657889467166499305558227635786922038300709465635665032362788821657236521443750938108440264564014080412870675324633423190226880338075753190002816740212167912541667386, 1813015948270605170494327027462767927668238016932441018204770850364166891479780348149629127108953561818359981896571545563617551207948156571122643027237671390832571624849892766565662348404168867487258425853064191070395435566239448528, 1703147790278812545808919311803253465091977239190220478003554114391300310923920435402284572213975190078137810042295522772486405957891397177306562281878529791622615529533777964508592563167873221257377134938914666430743351377618599468, 6278178489775796378230960195168194198865191514369599946855978876059738107235833955372780564515702681152913705996119810470327292606622329414011316101619726547400486206707034436148811872252943718668515788898176009551715308155411378252, 18502372570762310433863217616808095626038090932776074429027848581566215187912012261455455254801851855136832053610149165093284302575637475929697357817164914767314039550045344473538968895886764268535726243745335200504802864455745224374, 4619546424150636720632675449805339943017962539019526400964585316199619112511814181720051470848623690283063163236111719759442441616569278847685187351643033457613638640496754781862046330458169376039112280170067629393555816168818241121, 17415120259263326575917785021419190975482450501413944929888356972186654579803176474572508975215766509194009235591715149336564009819560581298723878336153312453947335918616023490225580430289839613029201222545734451097726880722839921382, 8307522287111865592770453226202115257484524653842503182672038744879218056275899543441543776625702705787596409072729458316533724848741039140250187914824007142564158445077159333307590448478263879269330063036285504424990516198257896295, 11263353891678243397276227460314841929873607735065191631233072436184881556807080115175345410349873166932751571268937511388565445447370133162623474541842794012489039636114698489895111355542309742024144040488016432324050920900295291917, 22637221521096771355782848874319356640240782235023169163186886225331051134680206995051142472351972293320891064080813070515162355530485444273200297804821736770540507890630957957945276656133277989360715398965382403686702660132053087389, 17919419877135534987371117199483506832865643179065513875403972803516315262685396424216812524399278928565319596834323499540921207386454692592496134156868095555234425205678332118842419128184729949597616863672987401083957030450961088118, 6084785464319055531520936804008603920136226720135667541062857654162604072088374635967414294340045316322725709290667559576429084868775969096858901672894136646463280390764523549103315360820057333674907169174163429153014379285872747201, 22582646848247815349822384029625982294969862652773702071458460690402019599859783915087863321522598200340080081814722953057928887642522789124256212970552071481336495429114943130059072461748175646464632989698260874422879732797887630047, 18669626144014838256754393744104130472295922668789204770557829273317529078229484347843108989561950816009995418160306613843824685195742442008837587483298470746325730371307237685260665649724430226456422634290254179870262594544431983580, 20052406002140826214070462061355742833483311314204273816436922246583813045591993339752776465796599006048131075796594497697843310687048655947142956234427753793119501583467069339507721514048187534341243065632056453879312603380628033984, 8536998978578217458444546841067601712321613656238053987413723752276637535354443999372125303631295704610057669756260574243930397078353340155663182523975349073323122272823468525187727995554596366377566035875710779754713058741421952297, 18434625855226899883321256831367130395454266215612264702708075963791303925781592538547918831568109391525493791354981671339894441519904308962763998161987029013446729670718008148129133450351098070931554566261249895846253603636590459596, 4836589882106604573232223783562904282390113141134832184116904820708055678518566213625282539739120591243833386887356618441208163640057659125158988736716688790394207262106963544742980383712576206460105345350538386057072108474044619762, 6151404576887692192610418168194331069192875548920158964829022752513950390283339567156423340910687221576158002429133456052555654098031826362939557645155801837456631388169151822830860248697122438884510698830753889483429000372055663270, 1574957139018125716198556939124476979519175929549560352017864438659995599753619766161008956285299169458623403378359963178580562501544136272165783563207087197050431991062774440640781210997705052555763881548707362577843167934254303211, 17391739152895538066781672275956234672907920242794599378833168697429044919890739257714041398214783661258560907470027798397029764878415624758336877129671514678297353821687758143698229059859378874838953846176893688321578130610211565286, 22442775423196539068158317596467259088950472981582207880432855826287481502251341833382328178251544577017724250630849093658390304250535679234308101654761044939170582837625840089519904382455956192527790359472609400260135910142621984804, 7748145694686025228235215160750244287356340902395751036047680266668756996397350960420787060972587276915359606276766739777861347852878339037039524614848022448512348644599427802285464351651684733130472167279398416173868476456640343912, 968331055615348886946161174142596323259279195401290249125471421855394873300085582575869103540417932149745449924520552363175883831558583706411049245922455751591766401028527194162506783887475373042174297269540922518114299818971515732, 4074196420936964179766581964556249617600508808814880297307983370447540931003863746901029660929911106973066021649873857071560682302121391895434719968587180495592648327726491322805723227506930292583988197314499826859508435423130136511, 19864987974362234107843653929873500108136815262278445784737257026822472090684137983310497635654575899271214537322575710548691021536061053470964176925313591634748257211956578723604063519794172805717329303553656399286725199286782179098, 5980232223078727426630626502373985853071880541561981005218776841139298756434767290311430618487388592202253565417179231192022611316234657898418924157525655172678865435399101556073022390243434214511995519696285633065317753437363140899, 9821319966095560427870562540391515794742864976782463778999916398549075070208007164914970520077561657764076828409003343933376170855999484408246466687946900127907046008389427535470321658506118424459143900724118409798821454695603532413, 7827061760058169599128916445957168975571796630781465189931078722702870872684431267074675693818964100116677523139537724577680225755195092012197924786849023733994256374790421775024816070942174050947871976107979562435932865310494883087, 22444668052197480392921780325089923182285523366742407483346175183018618880471398182443968590402259809874065978185849126448188342895030137619253767196685974598148578223227750661256523638369688545340957145235941267699205041015976512893, 20917044400441994043876270524213483352610260969649420453302372823720482527762724079002988257467288936795890599751896104615953448223734081092408051311403775183351145101060024221646952031995834916254264079757831184110975778281092887507, 23140912538412009642128425132684342938279634667238702284276382497865489723993571612771587585503991716334178974558961918251076413896005571217843917697675846778156724083976226196922651714668362270739315887073416139790810854613161221205, 22777946012556717221075832833653666836629416861635512682775171879258070731828427066106777275170219181994163961386136705459389933201518366302644543778363562846466085257052188326159339853787923581481741947880793477699405480147382158494, 23851586262216165721855485651763540041901511489076454491269387584732596518981375859161694969885462872348599346737087824666606523489542019629415264018415534655453799899565276989370343113997814318338527314054146555972083061531585827540, 20241416376929699761750802558413112170873703541929048761197148717657034619071841172624649616126693643941848760178381682942801111935776714336673825991096083096572342885484491597788757271226301779632972642169838769965985177058217188038, 2692623658541928573101809574838111935515631623595566809258680332737841700723177581136913483180407761165968252907913185839978546543265283140651614694449288264776969017249235506292038168449124679820126351493857549856356121231151653092, 16131290371505918809335910442479495479841565683249366748358361988494535045927568460325417586137766570965946466933319709361295018081273755953428838543656376509391831612977590017091825515705947022941510609863748269022738241991112543488, 1335160611734517210645206538933135972937544803451806751759630093284405592061360484816228430621641176590985805245868699739008511603795763736239195005005100364118036164638319077433065549088587459341808702399982456843190373618829758380, 10340884655343139837671785768186602936214734136755477567866586190929922502684799328216935326848576904458087728141043911084892486564116287640011646899861462113035901153299622043759499282128564846901160241967532876328459689814413762415, 5401801998031885667933094843069088272827013350970253067554899772704793572618267277623489486460813952487852750203234532174602055095351744072948091510037938518921258719623872400909307218937680691436513657947420608446304518643433543806, 22418868106953255259925166180079659279224737549892921884878026172626266645583784111270814808165875702359326672598830454977959663875880390431168563609899967914132355212711052456153248630704103482626553682618348908416775395116183421160, 20136816925897836048772212824296976042694611960736454057157846271343943360453902970773845024303002259554524096897822838253842365660027362116226399377625905232718459877264554224090369414896236479377060541879764953830249057877045251555, 417007008641601538653131077937620123593549306092323725176317590989242946892864900660489655668904173115128836432434611768470228830641521176358301458746585411902484062496874795344596497020100855878780454061487570562235412769427686317, 9816475565441529661291824775139176002345288049562161459635217819610547571837959753097093100495711176071908644218955109371081139417135838663380195844736613456931438981238662973400611171398897919439637129498647633743885607728861261845, 23870935413324621348274921404095042947875585668987906695837586539050798799854533446390296432839375770804268047327372595660396408173256820274722381200344879062334763587710033759647191441214875827380395128531108963710853637847394865713, 5298283449173550237355629570588050847341460771573182634769894887770904533264599629995486512196147997419360308122234130045379554651637311836030578449665827917483073270459896882565258770161952823438641471340977976030370479284643371508, 9100837458325934090298687047369486564792435663532832334039514867133941164867094239825017906066058129874353079407264039259148505190526558442923936093553694722216375206807028548669491820363396636679859686397489340148773407722045937270, 17038367322359956199612085432647045245163774933791813550948476894306406589837225702818847799733173871855718021202472793156228757158103629792922793811988464842161571581127798138726439413898369919443095650665934234847679938496501082548, 5299931840319151047971338206132253854280031927943516805614636255095356530922613677536304699331683053630885588152231978881663325811744339303687716269251042135117691288866254176400980454233864302175455006617533230769750479680704003803, 12540635716642138050069818430585456163343167481815665545278957523114902416154894156857128176013092728156227339170914675236740354318471661079175938598595792244472546173729361758589747726406890065450274035377585868728685758016648252277, 20322491326674638034817966107240137846880079505122662915547658066684133128524680689280031204806726531719600178717407242432128474388718978132706799940782382379254141734042970031880774214699826014425312091260412469194792303194943312541, 5229662284467342488041460575057606427352459717204043541086271154843521129291284032127069339383360917307751194492229261239447923171449428855700540788480851171076934541793501678873893328468428087126295294243102629336566344072435148926, 3285838812530358897545298545597343176030011766358309208184051849657687130054651377685203521819371289947496722092598297091948769435961363706612789578094785479539087879764936323884232849776769800582357588276204554212787884397356609075, 985977908000415897087132935158491952560421294051636567544225622494066414580751745182595887079757589173529845207284035227594010385666914234516531594517789212163680139291972549513242975229837531367529730153966350998393964527190960780, 17065146968215067842383191941447787644924233733406612558491157934810641836558863455012704342178343064915019207439623922379811619035308569771475626867167513169039770149329185353910699976605853826239989744767067695675074282642081109122, 2895051855443032500114264954131824950223016860747135906862021873334133780972247856024289082902593614686234940918908254535652058807083890041131819711987908379837879596740736424457497974785551048832507207236105596543909624181876322785, 4966900790205893074984989386646008103784297431600598682180814393416207374789387128394225554960559580907084765584389900080293673527269787068249734379554225965935987198682993924271078260562548541634568301366120953043703261984185035492, 1592133000317447857415093607791358078761029097913126706492340352416015371109359886156333987922914888082815145772272973546014967400910445408277918663315594917464634596929536938549199769536365664240519962382595777686556467574333228524, 17035537442662976504922683848715751125264550470049558142661773195755584861517729792053865084739966511957660313727319368149881218522960763762882305808684597990343444747248688404053255935943475864000546643886973794872661260510687280843, 20111698260990344511260405765344080240651285550598954249450996243164491354537997138010932667983387259244493313206064965234304942238230370889100484896673506193390990108890409994241977323914015682399152387423870735159707545233977076770, 4426576652391016795551419713890251009257497077843566944171223794376085011499334139845631881967064569788805218564609553883159372200439972546448048186839777176955653678061337638263702524915401358923560309463124850203968200337852733276, 3556250500712518687819416837629333029165286228062203447561280347508137816614314590932355942707292725328412737236278928580181418156388443710572944973186708461884059491603304783359925238797793594138717291455747294198397870200166947926, 13927320217504747590335052600456317522959386643781341454614326945183478241960544334007376807495121099323703009105189096866855842836770860884311107587040596788037191865762444816790052342380928760217895549688851330716204287404367303487, 19186706038001453829669717777125450932916146002197133081093772142153667138769734136853279989523987832968428625917578008444184262747837927970709245398651581065254203234844684953377568872969107656958355470030477893423131898072422756183, 22381665099391547182936913521847282760348471609353024967760382743808171185913404603975224381726387826288857667025325668082188366555603105557245157448683625346209348265965221897830928437651540759787451097803683602952136978886939848108, 23184966822032599428052602150557101983764751770509578032863780766266522607517592773626111822041493293258042973530264981559695260799033791203372990411009256833559380777212487382283059963062596935284684661031645172162024478226204363138, 16539088490461420703816947102632424948425515660257887809146011235917654678378412523179508616742234368055968310509283732191870030434582732164093099360112011742236459025255884663476536960498964609417125524793004880729910317951965592813, 10627113729566322150048832232683529097355980196490682036544275502457617404334634120165915692104820767017442741956545228542857367270650462946535492128265700535237871862208669509649325009158507616860442008149873107060741021076888884760, 11267125954054697421607144060487028030315221416724761783980425416225401414438268312062546288659852252620731439408156918787311722449792469512045947674206376022808235573921725655145722130002570628702790325686485651094520806647889697625, 4911205202815908515692837431520549683777169253252777007455111883806834073795531698553219580184313225825960948113399800474452261317070334272323032740707835989017948524378048478488428489385565965079763692393689501989320254467985218131, 18225583119089116078692515199163462711367659128624273031302797819688898542857154391879994381461943991555355016609793957171277566919134542789018572504987813438201233787367785338009025648567150953656694093846485220700745696812633035006, 17124234213957098698230284828489924705668475635880795070226911783064579553649755246615473501361642779526435236563455406701400112606551296644981809412927868935422016140603302419472851331702007217744308865951784508265319879878806395169, 18320622251591902268884471566945908729088619624449744135372454032601565510002933121047617779525906112324014260307172465674892213050531659488423104916770768335565948080253402637642044778885182266582275200106953222049633752308706688551, 24457930433564457945771787755968680104666213881444206925098794328782195040157980540838735926561759082225194223736014415351949112479640317187344000165121092686793374287372748091561901721804318156288437459491612736032622243568349516093, 22265804749164546901938171648091768389896829971403003545856878651484500077757482148788299901736948904123686203689202942240180132163143143705283033061770635205827882648633512344457848245098258829095489702543948367764867928232044824058, 18900161492491534779787443646293787626820709943533292051383245169379565231395076945117775620635775969975846765953606343974869577606827971998219045983071563019684594799478738283866960338845191273042733578885765920385538754923673408889, 17889473980262621507727589927197778641872127889134833323841551214539716290976451403348274752633422499728496096883243584042483628894269754398553184329718324889293596658429101772287592368674172804565689105678473019975243407244443523354, 18138536284390228585222991677635066336042468881007408937551554888609804713475952148185850060713096062490706359461940944964671776206024172923126363065585750055088818712488848481717124019308269329827427616383247328426589265783755119376, 6941686913634391288204116641020549765180362394639046952833583665887465570267538795546804523595813342836355168483856050240026251188294030485167045415709628881383778040727359450383956568568106721584184411199839996521253684993422751259, 22992006670212126764824193120058634657001604914414004734821248527368854522227019382280730391923555175806134471061931935927053165225097789175365530407921340026367729574881159034848504162017932940755494323686314491075117479953225503887, 18889844572592402977165311575773286867467454462925891168417511513423729217044120249821731533209860082071111083322002901596453361922574290712584585358411669740150626541648939895944226132920890088469550610507895808585359727591914206085, 6666655710468005649706184115723573365251462187673059249738512161994399275840373987561227970751250766584800647042039279477404087065060050644628381828583861242380931211664820415435317452066274782819115003184163730581681622864948821194, 24442788363614702478160454433556682777614538285899274650364570324147929577042693651515379466649305846727056159265579376386821157221997188678366720354117931257791747671854293025636726315130814360325435461139608811317126380758851246545, 3789221993484155913559741664728461223403980965496397955689870284919836847677745452749044838420054969057924618819059401422484788710618185075911294609519545068730398520559177215399107660641538049803271554736571292247686379194750320543, 21873850228341807328959395050233093703169880159289173724757394227136978403580890202395540529330163397068220942284403794709107289189710029361455418998025336530860787357934895975567129810177776409058257987618326850995771554675384004597, 17536041541204934014076526920758665113043740624193969731730744258387807070596104489532717517216000563908854506010662434077584634386355186944716702706942442940731251780893620899779245846595551333147659316055919062256480970701655279627, 19407120068778690141403380026131453596861551386369479396230505390227653872677134054561992820557367774198282874395704720779245370294312934155682385859613278432890305085004312799356060179682815696304771052136896088704751922242630198409, 22188335278745941318611538342309792101807036715704960353260517879118066222777745210659900238277928630140699521308316838275971289200263131258234641581549364021537324405919384058988041517229292916261500788540253262281872145817866534201, 7747714826763088285107541247818316037397421767027668051138855493363116460000955397824452361102671411632490114848836371357604866226227424954470624642731987025316172767218592207709740356830011790713079523783872784305872540656392291746, 19887371972318133855851604678702556011249418604536222675471406387964064156556715238854177545520609871225101077916367584660715220549065088085292416996064161705548027357359433864169349493060754312050979210446959542252897590259359350334, 8294906413533132168404300931946413998240080166871907188094515783201644742263173979787881022523424957539034934314850416306063309934742997700326726155063016581522865298074769968348111017554707292410938898142597066728208428380878750421, 1653105970991953482899537672062357513065378236063390275343931334625408241297427898336232902361937430133831999674424825099913436268711104010735434651657677108868699978197850769122830586350740906726462895350121007949545664795947860864, 12269618263727745774471362344937708112433146558452944102120330036342787834859494830666143669909939653466690789351178557153188487424122505279563071471514459806106274249298197080596758790096134028357329959992410153187970554647619693992, 1872864619889940685338328801003331116116324125207518914355262445073138404081944205799436751349615602533951192776172397206414216844642872435584612569950411851258148106436686594672345335783969547344634731455993264276684131388107925671, 4513749312512251880604514209077948498027702413440182534839908928178574977910770106795841023217134659344590190863364646266789330386820741397846745980903894024071570509233767128940445989174470003283523091184905302986968451776421561662, 8603337256650354725901662878660176754144664298844747341704003399121600657022664528563551640960916587386129786478309164700432759539464086939903495957787444834354374817296692466731788081058771312703991550181427467022305370277303346983, 23365631034822686706848861837664149512381852299460219050905837202265319818470354800644904900148269920728421546208860389463045551971738217073763540025131975146762487532728885828048839528343788216251920714889888039142680073032018209305, 6607639177853302945854914419510931096388217686583645225143255416189057140379688783625576347008665489422690692808119043773336416572630490641290112319256251209477866830470853168722398019123553430625117729213654554816567713513779344415, 4561566327415935118011554902890982069222860765432388797764984409579792338453618355071397274166466983322420193457204472449461675131240004294130210782759565785798599897601429158065284397449217928577095159769164431353199244868487488744, 20619847566560770217922342108991907691804433910319321142515967407002608932724027977344243536552779741744666018384832452860273148472189048802133349097819957587715301234453466408609901385057101082861479087744559457433976694471408546305, 22491152451840917724221614919594852240132461240517952298400459039237731967027207477770343934142858535807374120125597482004629528875275878346918715932552067774911528110269427267812617484848108111673621932638514453993119718582330140747, 6666474094256099454100470843004001323138491057011536304234976312925807717978405285549794760174974472283543425259849525001185866616280751670606879171557999380642875418172376311718234199272738593712030842861381513444395743918038821115, 14608023366653031088088792776473398626003159629342147637827411108620737788956808756326109569015343711267053685351058998420052502241372531064676603977272048298276216817941298853114867422633812368586103057778170425202194117767754667631, 5252337957400533023141552935190055167419769967624364557832824989834270839854871010838982035707949070995760254952770763066280166814341995798204623431763701829339076952532980539368056515029226923915153022281011140366638060437110366739, 10904306109950562384969710342212030523791112657561334466651023805904078236093287424426677767985064640606514094696576993583613088268461193986220871599701879363215462244945655373954510358026604779860047706432984563536661200078510932373, 271089870966054382062547940599302930208391511305619529931792046885517009708743599677262187984628732739879872484565903195651986883825927888971937651058489837590922157961189702574478434079284762530056683899140620405502763587815843988, 3829615989110076770296742506036176782165844942888782102108951362367146757383686834342989617169804679903591543207522172730554226315074929853710799018658501869041610918943093181700178445519770897725094255926846625256047131752654342562, 21027069518507812270143295031343563349093839199401621816244376936177926406132628307142702486126954172154048366960790803112488498869107125453199712698252176721555768481489241348715849630405805925617213192771837043429514738827417144886, 5881226757843642195966565964653582492820888457331393664539176000660786662815235967860466787943573661827208152609810786722095379797141818015319613457329828625393487501781946972038205996869901009867952429000678385538000284430630706236, 2521923938150189454600306942991910693184006998559434655516630180847991419680039647290350012029220409131874146647660269259895592069243379722647318881158750588650781231049664374429790092745270054520174713929014178340596950439728274560, 8758376499045186974759666603979237567667197537852772637677888896808075273558089282554848789332514021133259149957700137612055862632797830595621934651217892115186467411149352513292138952986429910931491409905668759362630065098560911595, 13191199724136555502957890679396614709016857839416803538397351651347130464502168341817424021127860042268678297183870891307490573812114364969054434627925544210247121163167379363424886928897494782573687523127714204264997876190602437253, 9045856550177265391220629158731617749010212836864098283122546582777883404294009743353817729777617793271710052997379493755741026807844934814727246295235951284912102541728263662595501946149955917048457614526081296501462068421827852976, 6459798973338438966900179181532933692034227569421041783473328776170587260589076396376191246924415837088205177319039971420829034696713874472602132191625410039341612568435551413702295547566220164641447295285720082107354915094875081603, 18130944169824976249131646693653229887900178060915303504243600146230275474872733740668972937137157219543732643704650107251416696945179838232545698726143250813322229855629104391962459755248646534545048139897036809559137651958948270079, 19433961868269193358322214141454667980688775311251629909509283331435001571001860372018368696521955762539089964314003195187700700564577856756527331858387859373880454698968805785663462845204498347648129595364259940616740397244612865478, 8454342596590308643274924755539741595287236546135227564272399966865185286500856241479821014846217497777600310284414611127622114813445233725529927188907572438103992229319436467881065607514441060358976822819421059737228474840057614047, 14537166469005975467747810118162809545827718830406398577270708204918464068241632461987018145489192528509346426457951388255954213424031104985101166216842931291037542011588336951147195358280734815984408580846906869482480502971976426377, 9864795106799668524939736197424521439591891686815014975959473174387504259559952345678395376176078540246526852734596130277519239749484404961484185022437705083689017218701798637167021350243461787680837042187852481891194754984735656290, 12268133299486497651766039892370828813185008783433000037986132221788291415226868620238438503015954126875051172591613715198127704843911983953450929112840971801607634064818730678605607306766453120283358084710064351726230220427399762639, 23200293260215743474524683129751336070441250470963131048954888782126750470082228197816325916628408311922916070082220789486560209004492220118951431198612457889003386630810956350904331757934144293620423858054842692246457187748735062656, 12185058234910532038606592923943044720835384475056406568591532299474530796146503312961639492038042022391680648709583314649821462809663154713418981695840590138378051933292810301094804670835915971975595283960175012458013597273267021942, 11221105904027102766755866944349650081668300046041215931102172400146372526930032156540201468901690818353993076628146864056758574315777576911062494908066762717748155624173988281018555785467232120361958052665957065342986661851276430394, 14146479366643851658329966290610820831402901507964825251479961487541976561960526129163043068554159234344763780262866371744837633699714330248498751352953049997609901897424160840833140698818737335558582310519215832295749211043181569006, 1996209659684880945362862072520668750990547266260431838906384808543405104055069952622618300300584240886900690277630290717169515463002827197894865638271520372178286783553830032501282265213469285397161533556619830350317766403742420992, 18745628006242526136845741349836299919853199739283471770759301677399688289987875667803750091491715203157411890157519643639106751973250183741642640909721507627190884945027790857100678267316925707699884380178101491613670302697083954620, 19418124148220580953761208919068176633948651831328159315391336734636206569887918413082885761812646760978293757398100953133069513030393015847333774689093510445461709841109234535067235898760285824847288504459882411280759715216659582800, 5205682801846809078199714774495380248428185583858806868224581963484209052697538736798790170636398029956181045671089079103657022469597301960581764542974628895184611312183649377529274963873896667201796079779944709584465505596525070672, 23318768639095847871012848772328512763678546109012363992365106641654912272868317312950662675004405062658308032988874110659096548795362930763210615993811303468541570030170160830706399273680692451111580339813777985874728526448601728258, 17663789897713399391329553205656192714527376624862805232162724262629896080514601476156211759120575400809873039830798687701631183863013915733500151932198747020557039729241833096695716114234461112493415456068786767133227958219632605915, 6830010105417894382101110089036680793557109559922111774917409457675491199721642329811584508061936118348231576993991198201242451125213981421233318599225362440072543796138016876550674700452496965047853603139044680407212592626251990309, 20884460900376572824292657271126142123485873790799680755215209134586191820305715480424778276376315900396541154319924699294552460109641193882916333508408848926700539891286011495861364148628583978468945538773985039022758906702197824639, 13531065912700180655643696503956611973995564881435960456381267408672878851671401491817614667804495339344405932207053507762953305764605332944268933111663238888239497791369102852051383458023784915387358708364653218605556527945192953446, 2553816611900270571668114455889943878175117814334437639644905418648197398024478749479929249928897268004570330988939190446533589567173538978234848074204808696098346906993745527874980173125711310145943264700663446068878853419141256703, 7702946127422572691818763664478853337162137782960611620730689560076482803756508559755597150108497423141643340665369251108221062530372412417632117367040091322406174387044200677890005382248858884236589435161310662150368144113087162028, 856622736471280804557194626008729500444312593564382589268324938301776962060843602449805587925812237957752880785112568949132663694077910582967771689119118364920441406196093341412299290918890444268129746265100558792934176787213952281, 13085724187735251902990250756196209600908652053725281294139610919151379144531851103633380912533710102796299853358725400239404987942390816511761529807030939893292168306351094697881403177421950694992263386572648775597583744415784239571, 7100689265695650020381992634740648600984998939714583113848881850701106459614914817851311196581107346332066792064189719153254177748385971715393193581611667136269465698799421805822480100454812068626009149069638986161533799798537549504, 4467099588802620474242283665232546701197788121100881304650783900944358367934303538647332945119694362849091301355005436291078223280753310654713741596387831313076907729367513905299597582977894859084467382251110232442313588731567517722, 5473046296972118327495477534670327059922805992783858593704621531789283121351554409848948934507912406403962506436068909023098369828879491079777608783858939477692990976926108359125684410236904067532064874993279097186185155662101906258, 13591367045303817756921606989622272393926672486200768156018816106702906007663207108105253090224421463114966486892454772900918694500736413865138170304122425783415795355698366106633741954984452451151018930441346568620455282531777867950, 12837435207992697390990569032560187426481997222586386722777778699242138971828789676884863577995903428553893241998604229610814215105950418432582043279620338868532002049158799146484208974875466555076583060832418045530228962180626040480, 7316640175294137713314869727957150382096738798129711776743606346914726499175960701433782404417244551378443800105185050713536694756151112399465628411989410218214135853671061537891268154389537857467508049690878544281069813159134447208, 5151376884557358987102680932801796401429637582605742653829100435795121709703076330975777361528309737649265350014534395043422641886613936452263244119523616000835976669901180725907500239783554884160601160568746329677044574260523365548, 5544576622940386549335576865087877596617926099466042134500548634035376720895126959440244093852186422501431889949044217654362265128303553015621478863491100875988057958166746762260378217552569885430432535094758534858841379918068187007, 14799083878004905781143009556442469081112262413659889639288955718256084634190461545010854679353463115437573577978160713007284612958005397981521383647283702964407693130299777274799243953236030640570493768398572551239990227306733506160, 132844788313325827023495191003662944917431930932901448945118978538428738126330451739237066558502122063099809045229187297346109539648216961234175022847902983869276754945800449898074085412283494856067025963252580204722767954611258179, 9997725379291207116745319316287400946107564644091980910563413554119585263470477093970564227161564056288461504072778119028907789906500076760472149102049287538406258735529830965640424425566731939511108199132607994947515509428756592559, 14646376958061531925518831995658673407931262101501970446265549357832773749183019186120219286620900718201222809743448147362429133751090137661872964022623647740154174784462365444772177633656555414706757146904500779085225231797377050144, 16961346690251629621986345424487239681148326635080182277543308482323385918405862092823934592459138523058683934777987371593649364181974320355468882733898473293716092586268920136699107300230769779047091693711423641803330962855097096925, 2618594245402239609420638325588710628729298505557767536783081437084561636188823448848608313088279895767614513680617644960939796227640357345879653043764575378231433481016175403223796690453962090038403036583909367766156025584252164203, 16129071855649587728956130797915283397821444682369014639788931828703405001025452386772618008541361124591860437269977673096643234091339097919538256670714042876788038021148787313041232229195101391115617710413115586617903468179658293636, 9296460193370583816070265591004199836116409032475859821958373154648206416256688852532615798871909770401306092671009539709487113538354105710364096048695663733075506988691991440779198012260316123759636997605427235081435477049705160552, 1356766159480311231046092117641588893355352105595481615726950290176811339998878309107970938869998059989877968402614403581962019949583734460209881480875822282448127936842922015950977040552638984243226561237288675211033594559512352433, 19197695297715405687227248527900901092786200526800375602428770624109373871809940359427277921210632597272639018938714964263079621574904896862536158251668755864087715415463131002786745060027810126535070270462254705453473599741763642828, 11504919294119244522634617029097854228866432223952020614427505589799731544252763714133524362716131837287869956783968056158486948361614604723869397483955281379172665969413312233383788159684735115665749332738234882920695449340309379522, 18136748881313347797489256490303008973958797121502583070872297973410283357173931060145003395290313809639159364452878423212404968100529416632370960280991488248897643385077173546644657216962479904853980225967792378564740955618790869689, 22555443333166977522691347301347007560400051480503434282172981846969595435546624498334336147388425749569732805395419970503066627849315134643618856767862223712319227590572187001545137380352712433069385477809940371396279834624165048444, 19332410102472644041731759226399070707013106727087481077728390364392367890410961009071561108596168685943298518353047413086954964804844094391018967334543408778135737715163542892702469367908397906585577557910294555212057020330243744038, 17177417284468945229490862308619539417109492506914913062877431832846296734201442477935598961820079857431068892933310664489209467455843404117024994948398426037991145460135427180175565761835499766689618253941365562391662494080561342044, 879611534766674063001632328710680301710464497091520920338941691285492779988149399177086528073474651179894297281827841186309099576047175634809922453338033325127493237666384356566986210156156953604218009901589731044248652021118031620, 23901207038202622707599557245612794049853792927287360450027492049407851837113641371314557090659548570609882944974639719117613653182109642059819516444307658547936689472901123537159776992389462316392381501838566991389570490374017025518, 7294655103119575652652322286451546582028529239995283561722077129773315845389577738996103704019032108880990669128684769525902413906863125164280686381766699292160785541839733876768365575818004233647829515890263347139003166333882303265, 8199949148068603717078157517861527127346508355755818050198576663971835822831527608360661637977726638149791394376076411543777469889828576151097728735193348069053034445800818498132875303434000618724830859612380606691308333135184789022, 12932127055873709636118977200718753643697619875736929170699115793566554057840448101626698069421491300195262169693063575726920790612681778762496689371363586507749098405216335541209813518577176560833970043581650697105699549343835699165, 9917293893368177421397475427602509319278773672321383411846980082270699518174858223780569843589979834443168760567064326549648560205061679870738748816216468066517782541276129041173215780179108422815701857032247139868407259633376154559, 6485828831888305306081814677813540588127941945945034779245913009780868830245510314875533356179894354966906340154886875373143060627077170845158967404313883218225671724777853809740370308868692781589580666606866945869996719967294318732, 19119951246631217104039346142695133667127595492295413599863780403588391811741379549048868909966290463800864082020118315313386877862668618823502190910178365164478013264098319748585627290011516370646420391829298524728641913535537536764, 13215772369693604102761934975932281069170694713655356522695565074039936506383846119163879883348265869353744569056003177315023138985010016601208933546975222998897707503967398686672700803569601825514347043442257463097499547507964305449, 1824804736849693701490461807874708098331129810367417218087931080176315035870555627969047286436604549231593492189121553958901210913466534815129733115561941853007429568739121822292088591127010504328963864942012956577043433126898293277, 6776240363305734174388141780584391816477723528084755437932934198907331150157541368203589425111306785868566064140117304971940704620271781717831300158164114203169466745769627304177491937036545708540956189334174616021603617610568750468)

分析：

参考：

HSSP与正交格学习笔记 - 0xFFFF

Hgame25 - huangx607087’s Blog

HSSP问题：

$A\vec{x}\equiv\vec{b}\mod p，已知\vec{b}和p，而A（0,1矩阵）和\vec{x}（向量）未知。$

四大基本子空间：

• 行空间： $A\vec{x}=\vec{b}$中，所有$\vec{b}$构成的空间，此时A的每一行构成空间的基底向量。

• 列空间： A$\vec{x}=\vec{b}$中，所有$\vec{b}$构成的空间，此时A的每一列构成空间的基底向量。

• 左0空间： 满足$\vec{x}A=\vec{0}$的所有$\vec{x}$构成的集合，在sagemath中为 A.left_kernel().matrix()。其个数为m-r+1，r为A中互相线性无关的行向量个数。

• 右0空间： 满足$\vec{x}A=\vec{0}$的所有$\vec{x}$构成的集合，在sagemath中为 A.right_kernel().matrix()。其个数为n-r+1，r为A中互相线性无关的列向量个数。

性质： 行空间和右0空间正交，列空间和左0空间正交。

问题解法：

• 对已知给定的向量$\vec{h} \mod M，$首先找与$\vec{h}$垂直的m-n个短向量$\vec{\mu_i}$

• 使用$\mu_i$构造格$L_{\frac{1}{x}}$，用$L_{\frac{1}{x}}$找到$L_x$的正交补$\overline{L_x}$

• 对$\overline{L_x}$使用BKZ恢复$x_i$

附上Arch Linux中安装flatter（加速格规约）步骤：

sudo pacman -S gmp mpfr eigen base-devel gcc git cmake
git clone https://github.com/keeganryan/flatter.git
cd flatter
mkdir build && cd ./build
cmake -DCMAKE_INSTALL_PREFIX=/usr ..
make
sudo make install

解答：

#sage
#正交格
import logging
from Crypto.Util.number import *
logging.basicConfig(
    level=logging.DEBUG,
    format="[%(levelname)s] %(message)s"
)

# https://github.com/Neobeo/HackTM2023/blob/main/solve420.sage
# faster LLL reduction to replace `M.LLL()` wiith `flatter(M)`
def flatter(M, **kwds):
    from subprocess import check_output
    from re import findall
    M = matrix(ZZ,M)
    # compile https://github.com/keeganryan/flatter and put it in [imath:0]PATH
    z = '[[' + ']\n['.join(' '.join(map(str,row)) for row in M) + ']]'
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int,findall(b'-?\\d+', ret)))

def checkMatrix(M, wl=[-1, 1]):
    M = [list(_) for _ in list(M)]
    ml = list(set(flatten(M)))
    logging.debug(ml)
    return sorted(ml) == sorted(wl)

def Nguyen_Stern(h, m, n, M):
    B = matrix(ZZ, m)
    B[0, 0] = M
    h0i = Integer(h[0]).inverse_mod(M)
    for i in range(1, m):
        B[i, 0] = - h[i] * h0i
        B[i, i] = 1
    #L = B.BKZ()    # slooooooow
    L = flatter(B)
    logging.info('flatter done.')

    '''
    vh = vector(Zmod(M), h)
    logging.debug([vector(Zmod(M), list(l)) * vh  for l in L])
    '''

    Lxo = matrix(ZZ, L[:m-n])
    Lxc = Lxo.right_kernel(algorithm='pari').matrix() # faster
    logging.info('right_kernel done.')

    '''
    try:
        Lx_real = matrix(ZZ, [xi + [0] * (m - len(xi)) for xi in X])
        rsc = Lxc.row_space()
        logging.debug([xi in rsc for xi in Lx_real])
    except:
        pass
    '''

    e = matrix(ZZ, [1] * m)
    B = block_matrix([[-e], [2*Lxc]])
    Lx = B.BKZ()
    logging.info('BKZ done.')
    assert checkMatrix(Lx)
    assert len(set(Lx[0])) == 1

    Lx = Lx[1:]
    E = matrix(ZZ, [[1 for c in range(Lxc.ncols())] for r in range(Lxc.nrows())])
    Lx = (Lx + E) / 2

    Lx2 = []
    e = vector(ZZ, [1] * m)
    rsc = Lxc.row_space()
    for lx in Lx:
        if lx in rsc:
            Lx2 += [lx]
            continue
        lx = e - lx
        if lx in rsc:
            Lx2 += [lx]
            continue
        logging.warning('Something wrong?')
    Lx = matrix(Zmod(M), Lx2)

    vh = vector(Zmod(M), h)
    va = Lx.solve_left(vh)
    return Lx, va

m = 247
n = 70
M = 24727704801291912268835129736340977567569865784366882566681759917843647658060231409536848349518003784121914409876944135933654762801696486121844572452922377222301017649192408619831637530961997845860817966791811403512683444831050730277  #模数
h = (20469155492003601253253155553986803208931503654660710348720234166881649344003987262947017659012241047835048808070655285602897209239858740637878468266658899337230431317158339301884716019022543563824842749256770110913729930512649260804, 20061197539347089441548703718074268696982927733926399966893938885418017706383655096958576679109275153818455164325651467862757293092935593603331322600268652102317484783972009137643693799482954597365244794142123800753823881292602536480, 20449460766608148327819595887200586456206801278670684512632410913015490167503229582572274670752456522031099839096710051732743590814126659553219421423179332067697185796944680381658040503559588413035145948011713429631258754626251809510, 8694899395827009396141425992800033658778511870582271935710336140733986029271840480988700276909069199154936459475590420059851372448080387583101099303513327440738409895238607476203278712316251695883695113189088200686962847017765865251, 17498906738048927737996405866022970301450352038432120213930838838210038594926299429345553642022023354628862755091766856471553830387207275486875845428629363403317202957206875712023311105409026776222751170693634497194866213310044491948, 21299762658878585689792741107233334119508283391034542047533549461069861697448477916998731369486958411519583373650555867155855962437320409451328328158651213135213221691391305300586647640883613895924445303848945011091274872544725674414, 13858127090108368287746753156610976181884852029313352847097417269439999009242391680724254761571841185603751824488440165104153860614293879561204207753769517496283139692448618313378608851838592204671380865578837501521485226960295757131, 606107901015597672365982103377292862084693785965621044158858796689187941648736569096576321682310287031175045717941165527209428043020224184139162372752993919547870816012630061403517257290792929118011920477984972488980800309428929138, 16411347559169875469676322308290176281268630976465248631394286269278754960475346068565041099592979349979405282500383230219337689652572250821233598049978719348544790979587439571926076421698781802827344619141310395216702580071924399522, 6068129514673183503857587322729184998437772152551135658369680702133087671031996497962264049216246290631119377494262423727768860757742407967523061034172791840869912562774945606863954031992955819024967183759253919768822212999747782744, 16164073883659743891300469301841345466013040331496294498459841128458772221808605865298982279094019325297165362518613472961615756988375470180863560145427159107654477630571820179272488975849163426474631458599008988483395281798203200528, 6002652834833034433754084876025091748505356485760658745433173659340361267044983148952514860044218624345794714339893198968695437915359546317081144940354972707822464098838782671025813140852500245911841467802762732970205945777188441808, 17671459116121703756342696273829703490771262874572413082113674648287158047430332224637950989312667436860899021459708831070319841598164702019251450606454194564607879044661224315550514675652908609424461409598055757760711713272045049260, 9747804618981818225871997793952044666360767497788933437958387359050267555950930083105832397549316456989456304967283430526550121320745106610566272812291168897483422111931300711618308924263505765555678625775964949832562993340397250411, 21996324872073077242827998678880398901946388402016282475335311894567710762615152283467554531548297081386048827720410652120091647717684967177129064563480634873781425892452230881151261828547497099982851340353851101348946158575303726724, 20241128353291496652549108347619870477868850796680814076775175545760753973504668850036916374732720117160823389137853705825323283084380525440155558201212646427779126805749122859405488144164760267716232853839558997235342814050866837305, 13077656588899945700177181105263191868661064142860342679420184386239288545559858208951244435002966218243471420411045127025170552814160049125443370520964733258446212562129228879028530411822623695945498142516847896364762727423847457569, 7071530328065960890228453106008174199753371584339217118863740503556709237910489181283781927314970563878932442685277071347084354303239011911501455742585794028015220762730525765723336697380407902300153076264167533419216642860030224808, 22629252419865938253406009966521328587876533319128691562733593432194850726544929405088413178711982271889635298452313176698526192124305038839672198237812975135604141185210235559237447902236397265515318102940456244538398518752792480319, 5761459282176273118441944774799317407926062706007941700537400300748276958322349624237180755323800649847915919270480127859496807988229286598479624333300775674629423967322510405098758253061619727977005010935095672626407042895060271117, 13639378161376676791792650903794774452153629456935313476059754419699524574293526097694165098576687387486041665215960405733414879557245739928959501291435121608217008600392918108625339394853036499361173570509333162629246799468258136355, 1112221399019911081496513796105161716836267107501837651409516901292548472550496647130548616639784532217354650999157000279855022754714713097738729659495163953274484703014544784112610298442477231451271844048275322265529309125867188484, 12169161457053461668887038869671670176419946971662802953933166632081503259881448728851846332111194017082971192703865066066994163285010795828715477686499512514182295671281701232618183396077110570747529444745554508737426539555889099083, 11995511934849768905988062930456188671563166274831822681485210668895901448904842487096473591287554694509756168119490699415704136424403683840102743199694489304702405180406601329931714339410923612708808717358223085506757046662329629503, 13398528474737208001694948941230339341569100018647773619061861109738576104252100110443962069174319732180553417809151715735410100005179978063724591835291397314433312440421293983105825390167635459002960994550698739443052006993415149287, 21685721078976945602014626559051952462522937081933691461596237088189849657600841978193227429482306484131038624804443150311960061590035031144063153270840224125769186685588909207004132946200580900994078282900107456593588235003169921354, 21958932659990459795087732047584541007461325015275566949343681883128871386631056478783893068511478481080998508038344707524693059394150326940234855081823341566958854943322931261168562807321821084640569487228751077318094170704981650643, 18575326074968673858478938102428524301651676277226235867758079277741745360252102636120213638047957826270155136845469846718570511376252915803608625919614831191687134838436838444619000754054647327991321858217571418142823485948838843485, 21925408319719932198647415634718243407859189936679904356040860926584581042313625039619815019247876519120113207553707089727019778893587018690751305364116444902853587524322159019276550794203235986634843194549273092242442491313448819261, 21971769237171245388162249651275023141695912811218668240216220140957909617367793495291879198350993947099136765615466319867553659408044799043226321654345805093608432328775587162697826122051456089057951721736470156996789589476553105264, 11663665652950097951023874167071177053010440547278309973779798672676245675511213044752231769369800098096803991421401406373428185323198016967614776368177594490205473987491609921616943160817435319509156480489438442748695594208064506220, 8571733767532539591744305084238785438241372113715037973018068103542160069189369810177762541226540971969214853589594936813485292570840550755458909361226931687465304387382031888400449142008298116395068621612620111710861173184866936140, 7265641014493092305952899792692591083374900624337072072988050601814681241595404157641546803250164823540836286168102490427911208624069282838605171970733970339707601992725288390921333947799040016958678972693235850470014270495531454783, 18357683019971557309259589537387305852885630835264669230196131340413934504145103735168294472683744065174013315114812930463567210171038311927245433959034948205776155437226711665133074869096527958147737755278545942090787842643719386293, 11249630823936690987701184435328330983163223168635101989339377911187086984695870497253721111980469167097885275676200751043669504762094425614665999696903436973710297025883232331081137662411660725420763463582758176584701928482618894781, 21368417704130086095517329969849814675572842583190085389984103090985523417424304950647847490274582711171880575904265538743919551938416088883734546870704471113682032872096669715559005389583617506786922899538736534449123490145292870717, 14804820832711028510069420293910842363490984270818804823036282440726358025681287768311485300453811070788732988003156703771994750175077965636968452087698951366737342420716417627361539128824909909441296599842507450408639167847785653915, 10434593401661546638239269531721470859924069355256379358171970711096840647467279929406877589003350835919284031476862418858161422460097377292030151489346187334893502923880428533662123412400043690091517722265611541955158862687687083713, 24561443937015608720032402685089937637576551127866411331840220467266147984636152386876296689017192384827778734671122241130228223938051376943961096583907106197792850273311466092875658575488249813416281385686228639897799476137433072794, 18809508978562914770986641825424844673983326011247074637810890215219273029154108492496227431003955064765815763011903046546663244351135252376892253084070542641533081339319510865846592705413531461782231583683139065833462426977193323114, 1170325200926282785717575909542245218787696779459745550244912972650806869414330169502410895858680097983058617766512675739980564138645468322689195204967563486996177593733827238558844633804910336361508567070012845430162557209140318922, 9099530973344423583417798796448265698513331818761124724904157320649249490671748034442773080315290728734123593584766820587431677397350547048991745367397003023697063690573732401873466117208072387527262379544046633911232863713321651057, 6186545629812301877416853524734068114160450574994337117451587850263036761908385044092582990344042147406495912347645194115630652437606943173745789382845771049426443196019424697520894541338185145315971072044570777761063733877553713897, 18998733646999927412724741294417250892695086218116871981646202453146130670287277614970454171035798941213673467661889691048080971104465387696449499673490777958698659977825222598637449610957807490964624239691466685216040180063226979122, 2029035413823102082844939452656558074099805593476575872183225270283922006193130394920312821210960344438963206668816623318138806516660963226561860797911308864515985218753289984687939495010747187617345807068432674609822226022395002612, 1224334924830478941430540036421292246508644320238722677095883999889500298055876272715003687287887258419587507272093701524018402394087314059455381046013880303534485492492854314287356722191065404686438496257734600194353825409365914860, 15388830123476635874371535682309831543921413772062742670104698630978096538706065152811565310857194947646535508434358944071335015150277106407625487947363537743602712388716945337353159986787039117453435890006787376090096478885097896793, 10420053457335214342250034515332590797688043330675602278978659239127226996657084329075623919952172290482707420754415548245461942799120532008714972162634055331774926378534698291836555381029033314988303673575302329970048819875247229179, 12996570101872386881673806472032213506289839322758639432467242407197962401207255061640708238859358713382396645910306730272104173292864961862992132326434563495453537396958298185516874532647829493332700756725404634790257544413340701179, 11310001007421937130740204981515298136120181111962805563938085404289034278582061516301247258497064123414338657565189590291572623864937738084898059354622789358315367559028252287238789841719507080364615405563645390035528060316587102434, 7649920628929819175111413039486903286582015040923724934131761955991728816695088157076979052445031028120246103984026955901706105551535103282597498033031299709784514740469952209886314525277234547727841567842751063166501691717457807447, 8282767661876353703033480225670583969116738681062155629579190289397580081693316541581172493468366688140769336848827009811751348916039495262878858557738835369246631011150499694799485418164185557834866797870483707948444235231858169626, 10348065215991838887653401510489462098163485305574734545999066167894062235647455464256295931687781439097474305106334560598277885818537337701043155862614830925253569580192693898982318220593792046251125806231585329780902132617095557605, 11280967838102140047754377333560306350439648795137561969675963243081381329614099288939779782707558436465906221877404058208128414128559781592656246480955369758626788333375306898903783463959673000218175927160948442088191543414186131128, 11818929318729599124873943942145086021537273013997542692590943191077407938431043519607803418206555258214868688916182982805626078211252859082557253484889098137542929253460999852448424761935728458750150144937944771790308225982842690991, 5412969967721429139669566091956620099392941108847901064147423662180279827506836216754081912452764251675143575201910182189452840950356093575193249038624088662404268095962548749560674786705087512264668188729966989099888520624252744742, 17547356830409485892450749625199098509352498837601257846778404113094407637374346871392480581359187302653977880177675827091282945951962337410850311708191191160617963235512211658386260536823783677847875240999663432436509923589359888700, 8591887831833320840353196012263813111833998698446912587048628554388758958894496922493509033622609997670078612331200032453354380661501616871254995529921741954557910165239506265116743029658460390005477758921580324576966499950007047698, 24240608152025765890027400489331384103622640389639440068870645610439083379801706312111003846522258870692561041435455283169383633954853734692273153399247032151636823004018903792154640252253321042038217671452847628056591095001306376447, 18175238845322126323124732491839020080710712641999842067614816417084136046584647549081884372712146959940542383332663098640914320062272677772398521802893135140152503676658094543636706418059620569628737841646560680792630698212823857262, 10173862342693636575822816691492648273969020863129335004286001570695771568655492268044889845820019987659485915423299727906247618142386037838017456563194751538355466980296232841821674366111391576715244751705262011350337874749069345128, 17662887672308755659019635470333733858782416229711314422114693688837435216071004353298349767965595195988075045297248229654838457705997370106886962462023530886801849382037053188597909092732733084276903712706650614116210171460124448702, 12181524874770358579756085310138062154649043402053826988100381472344586613507823529632552464702544146652926312223695774383330894873770697330113566788363326971512196767946895811541430690548268356821209678371607727953997755838859126774, 11706994803516619040652442122624584733481017689525911051638928911326046116787740449573218360698003304996969933288041344857060888292758795645873721224079904632765180343552430630220956988207594755397804226083803193344994676329154327493, 8402357024978800071132055381314495648044905341576271257490683211086187354513127161690622199664304716824213610566304398546880266690789434430387528988209454626947248456097541304971867186772981230342257502227623573405137627210448823142, 13448814958668457684435846084935312650492724089658173841576258956348433114343610821298085173624638488238498589587758466360130338576374710075452327343150526934585873779496035836251602780112344762888078216555506331950896199565104006397, 23261851067858529243006512692328544765212250343687275283881011048369283487674444025254618141024372715313068675809489228084809200986696814193106301463035744067133170413056991023684452021013779169832348352784939483901536220423645197942, 2956461782787803412373184373521537264070982785668285831540757975387873992581341347760818916518443181764106275140479051787993901624417517942973131286068209774333764601237951091135348213764981692825938722977028088836454760352308033758, 3064486829635307133829604105999736772476219409968765985793477839736080127528728977191920114031725863884495929381858399046617507423360505816138935964152136380493092256651231150405966672895186096713142246153609317333657783049782151637, 10534802040612029540164483914330039254596233735171946359486562702340646071277688198935825397890574505178778613602867388545647349934716384895425051636497444634355043931879515977147131722039200347425808771386164417873392627039032929381, 16347587561440747118213871772022312563284652196262767324725458541109438659123670691624550736479719729504505614345452675461481177780240509736905011159885741573570625495043362505744257188005059869496076647939661464052864550390489436392, 932904564223742245423974397013211219322210230063409757135997988238048200833511900713764471854227396545059725844299953686973316362284758928784205613692959818986324717887966604059912158445010080457313116226499514698345116888739045201, 14155784829547910297069256239291885565427894076067719732956480982423435038774293432631990332881685973262975579857568134342058023430988483873438365184934853154265957089486695576174902453654823300612278786604052983027801579290159697757, 15059083507189045339756950559733288471657088114328896031836676598008347915133424684726963231247503783837186267424615012969099328203791879946151584653751983269080942728473598803375881811206929641186341006775658793858164370672638305414, 24050946955204789955533896427147712239350820947048633709193663894730552442910167865457955759634279229427681904250200157386924869101980949385253708656818328215342828689475987104598173819168455976517935776911361022122188385844429827861, 19717014416567816150124583987528154859466839421475505938275277134544233978125970101441724416647563320808697850421129369459770642837401448140038995613160278102100098417142249160683605942010321574730955450415122680160957836958254976336, 18341739025196342781439155614541180114644324261593971049987391428771657889467166499305558227635786922038300709465635665032362788821657236521443750938108440264564014080412870675324633423190226880338075753190002816740212167912541667386, 1813015948270605170494327027462767927668238016932441018204770850364166891479780348149629127108953561818359981896571545563617551207948156571122643027237671390832571624849892766565662348404168867487258425853064191070395435566239448528, 1703147790278812545808919311803253465091977239190220478003554114391300310923920435402284572213975190078137810042295522772486405957891397177306562281878529791622615529533777964508592563167873221257377134938914666430743351377618599468, 6278178489775796378230960195168194198865191514369599946855978876059738107235833955372780564515702681152913705996119810470327292606622329414011316101619726547400486206707034436148811872252943718668515788898176009551715308155411378252, 18502372570762310433863217616808095626038090932776074429027848581566215187912012261455455254801851855136832053610149165093284302575637475929697357817164914767314039550045344473538968895886764268535726243745335200504802864455745224374, 4619546424150636720632675449805339943017962539019526400964585316199619112511814181720051470848623690283063163236111719759442441616569278847685187351643033457613638640496754781862046330458169376039112280170067629393555816168818241121, 17415120259263326575917785021419190975482450501413944929888356972186654579803176474572508975215766509194009235591715149336564009819560581298723878336153312453947335918616023490225580430289839613029201222545734451097726880722839921382, 8307522287111865592770453226202115257484524653842503182672038744879218056275899543441543776625702705787596409072729458316533724848741039140250187914824007142564158445077159333307590448478263879269330063036285504424990516198257896295, 11263353891678243397276227460314841929873607735065191631233072436184881556807080115175345410349873166932751571268937511388565445447370133162623474541842794012489039636114698489895111355542309742024144040488016432324050920900295291917, 22637221521096771355782848874319356640240782235023169163186886225331051134680206995051142472351972293320891064080813070515162355530485444273200297804821736770540507890630957957945276656133277989360715398965382403686702660132053087389, 17919419877135534987371117199483506832865643179065513875403972803516315262685396424216812524399278928565319596834323499540921207386454692592496134156868095555234425205678332118842419128184729949597616863672987401083957030450961088118, 6084785464319055531520936804008603920136226720135667541062857654162604072088374635967414294340045316322725709290667559576429084868775969096858901672894136646463280390764523549103315360820057333674907169174163429153014379285872747201, 22582646848247815349822384029625982294969862652773702071458460690402019599859783915087863321522598200340080081814722953057928887642522789124256212970552071481336495429114943130059072461748175646464632989698260874422879732797887630047, 18669626144014838256754393744104130472295922668789204770557829273317529078229484347843108989561950816009995418160306613843824685195742442008837587483298470746325730371307237685260665649724430226456422634290254179870262594544431983580, 20052406002140826214070462061355742833483311314204273816436922246583813045591993339752776465796599006048131075796594497697843310687048655947142956234427753793119501583467069339507721514048187534341243065632056453879312603380628033984, 8536998978578217458444546841067601712321613656238053987413723752276637535354443999372125303631295704610057669756260574243930397078353340155663182523975349073323122272823468525187727995554596366377566035875710779754713058741421952297, 18434625855226899883321256831367130395454266215612264702708075963791303925781592538547918831568109391525493791354981671339894441519904308962763998161987029013446729670718008148129133450351098070931554566261249895846253603636590459596, 4836589882106604573232223783562904282390113141134832184116904820708055678518566213625282539739120591243833386887356618441208163640057659125158988736716688790394207262106963544742980383712576206460105345350538386057072108474044619762, 6151404576887692192610418168194331069192875548920158964829022752513950390283339567156423340910687221576158002429133456052555654098031826362939557645155801837456631388169151822830860248697122438884510698830753889483429000372055663270, 1574957139018125716198556939124476979519175929549560352017864438659995599753619766161008956285299169458623403378359963178580562501544136272165783563207087197050431991062774440640781210997705052555763881548707362577843167934254303211, 17391739152895538066781672275956234672907920242794599378833168697429044919890739257714041398214783661258560907470027798397029764878415624758336877129671514678297353821687758143698229059859378874838953846176893688321578130610211565286, 22442775423196539068158317596467259088950472981582207880432855826287481502251341833382328178251544577017724250630849093658390304250535679234308101654761044939170582837625840089519904382455956192527790359472609400260135910142621984804, 7748145694686025228235215160750244287356340902395751036047680266668756996397350960420787060972587276915359606276766739777861347852878339037039524614848022448512348644599427802285464351651684733130472167279398416173868476456640343912, 968331055615348886946161174142596323259279195401290249125471421855394873300085582575869103540417932149745449924520552363175883831558583706411049245922455751591766401028527194162506783887475373042174297269540922518114299818971515732, 4074196420936964179766581964556249617600508808814880297307983370447540931003863746901029660929911106973066021649873857071560682302121391895434719968587180495592648327726491322805723227506930292583988197314499826859508435423130136511, 19864987974362234107843653929873500108136815262278445784737257026822472090684137983310497635654575899271214537322575710548691021536061053470964176925313591634748257211956578723604063519794172805717329303553656399286725199286782179098, 5980232223078727426630626502373985853071880541561981005218776841139298756434767290311430618487388592202253565417179231192022611316234657898418924157525655172678865435399101556073022390243434214511995519696285633065317753437363140899, 9821319966095560427870562540391515794742864976782463778999916398549075070208007164914970520077561657764076828409003343933376170855999484408246466687946900127907046008389427535470321658506118424459143900724118409798821454695603532413, 7827061760058169599128916445957168975571796630781465189931078722702870872684431267074675693818964100116677523139537724577680225755195092012197924786849023733994256374790421775024816070942174050947871976107979562435932865310494883087, 22444668052197480392921780325089923182285523366742407483346175183018618880471398182443968590402259809874065978185849126448188342895030137619253767196685974598148578223227750661256523638369688545340957145235941267699205041015976512893, 20917044400441994043876270524213483352610260969649420453302372823720482527762724079002988257467288936795890599751896104615953448223734081092408051311403775183351145101060024221646952031995834916254264079757831184110975778281092887507, 23140912538412009642128425132684342938279634667238702284276382497865489723993571612771587585503991716334178974558961918251076413896005571217843917697675846778156724083976226196922651714668362270739315887073416139790810854613161221205, 22777946012556717221075832833653666836629416861635512682775171879258070731828427066106777275170219181994163961386136705459389933201518366302644543778363562846466085257052188326159339853787923581481741947880793477699405480147382158494, 23851586262216165721855485651763540041901511489076454491269387584732596518981375859161694969885462872348599346737087824666606523489542019629415264018415534655453799899565276989370343113997814318338527314054146555972083061531585827540, 20241416376929699761750802558413112170873703541929048761197148717657034619071841172624649616126693643941848760178381682942801111935776714336673825991096083096572342885484491597788757271226301779632972642169838769965985177058217188038, 2692623658541928573101809574838111935515631623595566809258680332737841700723177581136913483180407761165968252907913185839978546543265283140651614694449288264776969017249235506292038168449124679820126351493857549856356121231151653092, 16131290371505918809335910442479495479841565683249366748358361988494535045927568460325417586137766570965946466933319709361295018081273755953428838543656376509391831612977590017091825515705947022941510609863748269022738241991112543488, 1335160611734517210645206538933135972937544803451806751759630093284405592061360484816228430621641176590985805245868699739008511603795763736239195005005100364118036164638319077433065549088587459341808702399982456843190373618829758380, 10340884655343139837671785768186602936214734136755477567866586190929922502684799328216935326848576904458087728141043911084892486564116287640011646899861462113035901153299622043759499282128564846901160241967532876328459689814413762415, 5401801998031885667933094843069088272827013350970253067554899772704793572618267277623489486460813952487852750203234532174602055095351744072948091510037938518921258719623872400909307218937680691436513657947420608446304518643433543806, 22418868106953255259925166180079659279224737549892921884878026172626266645583784111270814808165875702359326672598830454977959663875880390431168563609899967914132355212711052456153248630704103482626553682618348908416775395116183421160, 20136816925897836048772212824296976042694611960736454057157846271343943360453902970773845024303002259554524096897822838253842365660027362116226399377625905232718459877264554224090369414896236479377060541879764953830249057877045251555, 417007008641601538653131077937620123593549306092323725176317590989242946892864900660489655668904173115128836432434611768470228830641521176358301458746585411902484062496874795344596497020100855878780454061487570562235412769427686317, 9816475565441529661291824775139176002345288049562161459635217819610547571837959753097093100495711176071908644218955109371081139417135838663380195844736613456931438981238662973400611171398897919439637129498647633743885607728861261845, 23870935413324621348274921404095042947875585668987906695837586539050798799854533446390296432839375770804268047327372595660396408173256820274722381200344879062334763587710033759647191441214875827380395128531108963710853637847394865713, 5298283449173550237355629570588050847341460771573182634769894887770904533264599629995486512196147997419360308122234130045379554651637311836030578449665827917483073270459896882565258770161952823438641471340977976030370479284643371508, 9100837458325934090298687047369486564792435663532832334039514867133941164867094239825017906066058129874353079407264039259148505190526558442923936093553694722216375206807028548669491820363396636679859686397489340148773407722045937270, 17038367322359956199612085432647045245163774933791813550948476894306406589837225702818847799733173871855718021202472793156228757158103629792922793811988464842161571581127798138726439413898369919443095650665934234847679938496501082548, 5299931840319151047971338206132253854280031927943516805614636255095356530922613677536304699331683053630885588152231978881663325811744339303687716269251042135117691288866254176400980454233864302175455006617533230769750479680704003803, 12540635716642138050069818430585456163343167481815665545278957523114902416154894156857128176013092728156227339170914675236740354318471661079175938598595792244472546173729361758589747726406890065450274035377585868728685758016648252277, 20322491326674638034817966107240137846880079505122662915547658066684133128524680689280031204806726531719600178717407242432128474388718978132706799940782382379254141734042970031880774214699826014425312091260412469194792303194943312541, 5229662284467342488041460575057606427352459717204043541086271154843521129291284032127069339383360917307751194492229261239447923171449428855700540788480851171076934541793501678873893328468428087126295294243102629336566344072435148926, 3285838812530358897545298545597343176030011766358309208184051849657687130054651377685203521819371289947496722092598297091948769435961363706612789578094785479539087879764936323884232849776769800582357588276204554212787884397356609075, 985977908000415897087132935158491952560421294051636567544225622494066414580751745182595887079757589173529845207284035227594010385666914234516531594517789212163680139291972549513242975229837531367529730153966350998393964527190960780, 17065146968215067842383191941447787644924233733406612558491157934810641836558863455012704342178343064915019207439623922379811619035308569771475626867167513169039770149329185353910699976605853826239989744767067695675074282642081109122, 2895051855443032500114264954131824950223016860747135906862021873334133780972247856024289082902593614686234940918908254535652058807083890041131819711987908379837879596740736424457497974785551048832507207236105596543909624181876322785, 4966900790205893074984989386646008103784297431600598682180814393416207374789387128394225554960559580907084765584389900080293673527269787068249734379554225965935987198682993924271078260562548541634568301366120953043703261984185035492, 1592133000317447857415093607791358078761029097913126706492340352416015371109359886156333987922914888082815145772272973546014967400910445408277918663315594917464634596929536938549199769536365664240519962382595777686556467574333228524, 17035537442662976504922683848715751125264550470049558142661773195755584861517729792053865084739966511957660313727319368149881218522960763762882305808684597990343444747248688404053255935943475864000546643886973794872661260510687280843, 20111698260990344511260405765344080240651285550598954249450996243164491354537997138010932667983387259244493313206064965234304942238230370889100484896673506193390990108890409994241977323914015682399152387423870735159707545233977076770, 4426576652391016795551419713890251009257497077843566944171223794376085011499334139845631881967064569788805218564609553883159372200439972546448048186839777176955653678061337638263702524915401358923560309463124850203968200337852733276, 3556250500712518687819416837629333029165286228062203447561280347508137816614314590932355942707292725328412737236278928580181418156388443710572944973186708461884059491603304783359925238797793594138717291455747294198397870200166947926, 13927320217504747590335052600456317522959386643781341454614326945183478241960544334007376807495121099323703009105189096866855842836770860884311107587040596788037191865762444816790052342380928760217895549688851330716204287404367303487, 19186706038001453829669717777125450932916146002197133081093772142153667138769734136853279989523987832968428625917578008444184262747837927970709245398651581065254203234844684953377568872969107656958355470030477893423131898072422756183, 22381665099391547182936913521847282760348471609353024967760382743808171185913404603975224381726387826288857667025325668082188366555603105557245157448683625346209348265965221897830928437651540759787451097803683602952136978886939848108, 23184966822032599428052602150557101983764751770509578032863780766266522607517592773626111822041493293258042973530264981559695260799033791203372990411009256833559380777212487382283059963062596935284684661031645172162024478226204363138, 16539088490461420703816947102632424948425515660257887809146011235917654678378412523179508616742234368055968310509283732191870030434582732164093099360112011742236459025255884663476536960498964609417125524793004880729910317951965592813, 10627113729566322150048832232683529097355980196490682036544275502457617404334634120165915692104820767017442741956545228542857367270650462946535492128265700535237871862208669509649325009158507616860442008149873107060741021076888884760, 11267125954054697421607144060487028030315221416724761783980425416225401414438268312062546288659852252620731439408156918787311722449792469512045947674206376022808235573921725655145722130002570628702790325686485651094520806647889697625, 4911205202815908515692837431520549683777169253252777007455111883806834073795531698553219580184313225825960948113399800474452261317070334272323032740707835989017948524378048478488428489385565965079763692393689501989320254467985218131, 18225583119089116078692515199163462711367659128624273031302797819688898542857154391879994381461943991555355016609793957171277566919134542789018572504987813438201233787367785338009025648567150953656694093846485220700745696812633035006, 17124234213957098698230284828489924705668475635880795070226911783064579553649755246615473501361642779526435236563455406701400112606551296644981809412927868935422016140603302419472851331702007217744308865951784508265319879878806395169, 18320622251591902268884471566945908729088619624449744135372454032601565510002933121047617779525906112324014260307172465674892213050531659488423104916770768335565948080253402637642044778885182266582275200106953222049633752308706688551, 24457930433564457945771787755968680104666213881444206925098794328782195040157980540838735926561759082225194223736014415351949112479640317187344000165121092686793374287372748091561901721804318156288437459491612736032622243568349516093, 22265804749164546901938171648091768389896829971403003545856878651484500077757482148788299901736948904123686203689202942240180132163143143705283033061770635205827882648633512344457848245098258829095489702543948367764867928232044824058, 18900161492491534779787443646293787626820709943533292051383245169379565231395076945117775620635775969975846765953606343974869577606827971998219045983071563019684594799478738283866960338845191273042733578885765920385538754923673408889, 17889473980262621507727589927197778641872127889134833323841551214539716290976451403348274752633422499728496096883243584042483628894269754398553184329718324889293596658429101772287592368674172804565689105678473019975243407244443523354, 18138536284390228585222991677635066336042468881007408937551554888609804713475952148185850060713096062490706359461940944964671776206024172923126363065585750055088818712488848481717124019308269329827427616383247328426589265783755119376, 6941686913634391288204116641020549765180362394639046952833583665887465570267538795546804523595813342836355168483856050240026251188294030485167045415709628881383778040727359450383956568568106721584184411199839996521253684993422751259, 22992006670212126764824193120058634657001604914414004734821248527368854522227019382280730391923555175806134471061931935927053165225097789175365530407921340026367729574881159034848504162017932940755494323686314491075117479953225503887, 18889844572592402977165311575773286867467454462925891168417511513423729217044120249821731533209860082071111083322002901596453361922574290712584585358411669740150626541648939895944226132920890088469550610507895808585359727591914206085, 6666655710468005649706184115723573365251462187673059249738512161994399275840373987561227970751250766584800647042039279477404087065060050644628381828583861242380931211664820415435317452066274782819115003184163730581681622864948821194, 24442788363614702478160454433556682777614538285899274650364570324147929577042693651515379466649305846727056159265579376386821157221997188678366720354117931257791747671854293025636726315130814360325435461139608811317126380758851246545, 3789221993484155913559741664728461223403980965496397955689870284919836847677745452749044838420054969057924618819059401422484788710618185075911294609519545068730398520559177215399107660641538049803271554736571292247686379194750320543, 21873850228341807328959395050233093703169880159289173724757394227136978403580890202395540529330163397068220942284403794709107289189710029361455418998025336530860787357934895975567129810177776409058257987618326850995771554675384004597, 17536041541204934014076526920758665113043740624193969731730744258387807070596104489532717517216000563908854506010662434077584634386355186944716702706942442940731251780893620899779245846595551333147659316055919062256480970701655279627, 19407120068778690141403380026131453596861551386369479396230505390227653872677134054561992820557367774198282874395704720779245370294312934155682385859613278432890305085004312799356060179682815696304771052136896088704751922242630198409, 22188335278745941318611538342309792101807036715704960353260517879118066222777745210659900238277928630140699521308316838275971289200263131258234641581549364021537324405919384058988041517229292916261500788540253262281872145817866534201, 7747714826763088285107541247818316037397421767027668051138855493363116460000955397824452361102671411632490114848836371357604866226227424954470624642731987025316172767218592207709740356830011790713079523783872784305872540656392291746, 19887371972318133855851604678702556011249418604536222675471406387964064156556715238854177545520609871225101077916367584660715220549065088085292416996064161705548027357359433864169349493060754312050979210446959542252897590259359350334, 8294906413533132168404300931946413998240080166871907188094515783201644742263173979787881022523424957539034934314850416306063309934742997700326726155063016581522865298074769968348111017554707292410938898142597066728208428380878750421, 1653105970991953482899537672062357513065378236063390275343931334625408241297427898336232902361937430133831999674424825099913436268711104010735434651657677108868699978197850769122830586350740906726462895350121007949545664795947860864, 12269618263727745774471362344937708112433146558452944102120330036342787834859494830666143669909939653466690789351178557153188487424122505279563071471514459806106274249298197080596758790096134028357329959992410153187970554647619693992, 1872864619889940685338328801003331116116324125207518914355262445073138404081944205799436751349615602533951192776172397206414216844642872435584612569950411851258148106436686594672345335783969547344634731455993264276684131388107925671, 4513749312512251880604514209077948498027702413440182534839908928178574977910770106795841023217134659344590190863364646266789330386820741397846745980903894024071570509233767128940445989174470003283523091184905302986968451776421561662, 8603337256650354725901662878660176754144664298844747341704003399121600657022664528563551640960916587386129786478309164700432759539464086939903495957787444834354374817296692466731788081058771312703991550181427467022305370277303346983, 23365631034822686706848861837664149512381852299460219050905837202265319818470354800644904900148269920728421546208860389463045551971738217073763540025131975146762487532728885828048839528343788216251920714889888039142680073032018209305, 6607639177853302945854914419510931096388217686583645225143255416189057140379688783625576347008665489422690692808119043773336416572630490641290112319256251209477866830470853168722398019123553430625117729213654554816567713513779344415, 4561566327415935118011554902890982069222860765432388797764984409579792338453618355071397274166466983322420193457204472449461675131240004294130210782759565785798599897601429158065284397449217928577095159769164431353199244868487488744, 20619847566560770217922342108991907691804433910319321142515967407002608932724027977344243536552779741744666018384832452860273148472189048802133349097819957587715301234453466408609901385057101082861479087744559457433976694471408546305, 22491152451840917724221614919594852240132461240517952298400459039237731967027207477770343934142858535807374120125597482004629528875275878346918715932552067774911528110269427267812617484848108111673621932638514453993119718582330140747, 6666474094256099454100470843004001323138491057011536304234976312925807717978405285549794760174974472283543425259849525001185866616280751670606879171557999380642875418172376311718234199272738593712030842861381513444395743918038821115, 14608023366653031088088792776473398626003159629342147637827411108620737788956808756326109569015343711267053685351058998420052502241372531064676603977272048298276216817941298853114867422633812368586103057778170425202194117767754667631, 5252337957400533023141552935190055167419769967624364557832824989834270839854871010838982035707949070995760254952770763066280166814341995798204623431763701829339076952532980539368056515029226923915153022281011140366638060437110366739, 10904306109950562384969710342212030523791112657561334466651023805904078236093287424426677767985064640606514094696576993583613088268461193986220871599701879363215462244945655373954510358026604779860047706432984563536661200078510932373, 271089870966054382062547940599302930208391511305619529931792046885517009708743599677262187984628732739879872484565903195651986883825927888971937651058489837590922157961189702574478434079284762530056683899140620405502763587815843988, 3829615989110076770296742506036176782165844942888782102108951362367146757383686834342989617169804679903591543207522172730554226315074929853710799018658501869041610918943093181700178445519770897725094255926846625256047131752654342562, 21027069518507812270143295031343563349093839199401621816244376936177926406132628307142702486126954172154048366960790803112488498869107125453199712698252176721555768481489241348715849630405805925617213192771837043429514738827417144886, 5881226757843642195966565964653582492820888457331393664539176000660786662815235967860466787943573661827208152609810786722095379797141818015319613457329828625393487501781946972038205996869901009867952429000678385538000284430630706236, 2521923938150189454600306942991910693184006998559434655516630180847991419680039647290350012029220409131874146647660269259895592069243379722647318881158750588650781231049664374429790092745270054520174713929014178340596950439728274560, 8758376499045186974759666603979237567667197537852772637677888896808075273558089282554848789332514021133259149957700137612055862632797830595621934651217892115186467411149352513292138952986429910931491409905668759362630065098560911595, 13191199724136555502957890679396614709016857839416803538397351651347130464502168341817424021127860042268678297183870891307490573812114364969054434627925544210247121163167379363424886928897494782573687523127714204264997876190602437253, 9045856550177265391220629158731617749010212836864098283122546582777883404294009743353817729777617793271710052997379493755741026807844934814727246295235951284912102541728263662595501946149955917048457614526081296501462068421827852976, 6459798973338438966900179181532933692034227569421041783473328776170587260589076396376191246924415837088205177319039971420829034696713874472602132191625410039341612568435551413702295547566220164641447295285720082107354915094875081603, 18130944169824976249131646693653229887900178060915303504243600146230275474872733740668972937137157219543732643704650107251416696945179838232545698726143250813322229855629104391962459755248646534545048139897036809559137651958948270079, 19433961868269193358322214141454667980688775311251629909509283331435001571001860372018368696521955762539089964314003195187700700564577856756527331858387859373880454698968805785663462845204498347648129595364259940616740397244612865478, 8454342596590308643274924755539741595287236546135227564272399966865185286500856241479821014846217497777600310284414611127622114813445233725529927188907572438103992229319436467881065607514441060358976822819421059737228474840057614047, 14537166469005975467747810118162809545827718830406398577270708204918464068241632461987018145489192528509346426457951388255954213424031104985101166216842931291037542011588336951147195358280734815984408580846906869482480502971976426377, 9864795106799668524939736197424521439591891686815014975959473174387504259559952345678395376176078540246526852734596130277519239749484404961484185022437705083689017218701798637167021350243461787680837042187852481891194754984735656290, 12268133299486497651766039892370828813185008783433000037986132221788291415226868620238438503015954126875051172591613715198127704843911983953450929112840971801607634064818730678605607306766453120283358084710064351726230220427399762639, 23200293260215743474524683129751336070441250470963131048954888782126750470082228197816325916628408311922916070082220789486560209004492220118951431198612457889003386630810956350904331757934144293620423858054842692246457187748735062656, 12185058234910532038606592923943044720835384475056406568591532299474530796146503312961639492038042022391680648709583314649821462809663154713418981695840590138378051933292810301094804670835915971975595283960175012458013597273267021942, 11221105904027102766755866944349650081668300046041215931102172400146372526930032156540201468901690818353993076628146864056758574315777576911062494908066762717748155624173988281018555785467232120361958052665957065342986661851276430394, 14146479366643851658329966290610820831402901507964825251479961487541976561960526129163043068554159234344763780262866371744837633699714330248498751352953049997609901897424160840833140698818737335558582310519215832295749211043181569006, 1996209659684880945362862072520668750990547266260431838906384808543405104055069952622618300300584240886900690277630290717169515463002827197894865638271520372178286783553830032501282265213469285397161533556619830350317766403742420992, 18745628006242526136845741349836299919853199739283471770759301677399688289987875667803750091491715203157411890157519643639106751973250183741642640909721507627190884945027790857100678267316925707699884380178101491613670302697083954620, 19418124148220580953761208919068176633948651831328159315391336734636206569887918413082885761812646760978293757398100953133069513030393015847333774689093510445461709841109234535067235898760285824847288504459882411280759715216659582800, 5205682801846809078199714774495380248428185583858806868224581963484209052697538736798790170636398029956181045671089079103657022469597301960581764542974628895184611312183649377529274963873896667201796079779944709584465505596525070672, 23318768639095847871012848772328512763678546109012363992365106641654912272868317312950662675004405062658308032988874110659096548795362930763210615993811303468541570030170160830706399273680692451111580339813777985874728526448601728258, 17663789897713399391329553205656192714527376624862805232162724262629896080514601476156211759120575400809873039830798687701631183863013915733500151932198747020557039729241833096695716114234461112493415456068786767133227958219632605915, 6830010105417894382101110089036680793557109559922111774917409457675491199721642329811584508061936118348231576993991198201242451125213981421233318599225362440072543796138016876550674700452496965047853603139044680407212592626251990309, 20884460900376572824292657271126142123485873790799680755215209134586191820305715480424778276376315900396541154319924699294552460109641193882916333508408848926700539891286011495861364148628583978468945538773985039022758906702197824639, 13531065912700180655643696503956611973995564881435960456381267408672878851671401491817614667804495339344405932207053507762953305764605332944268933111663238888239497791369102852051383458023784915387358708364653218605556527945192953446, 2553816611900270571668114455889943878175117814334437639644905418648197398024478749479929249928897268004570330988939190446533589567173538978234848074204808696098346906993745527874980173125711310145943264700663446068878853419141256703, 7702946127422572691818763664478853337162137782960611620730689560076482803756508559755597150108497423141643340665369251108221062530372412417632117367040091322406174387044200677890005382248858884236589435161310662150368144113087162028, 856622736471280804557194626008729500444312593564382589268324938301776962060843602449805587925812237957752880785112568949132663694077910582967771689119118364920441406196093341412299290918890444268129746265100558792934176787213952281, 13085724187735251902990250756196209600908652053725281294139610919151379144531851103633380912533710102796299853358725400239404987942390816511761529807030939893292168306351094697881403177421950694992263386572648775597583744415784239571, 7100689265695650020381992634740648600984998939714583113848881850701106459614914817851311196581107346332066792064189719153254177748385971715393193581611667136269465698799421805822480100454812068626009149069638986161533799798537549504, 4467099588802620474242283665232546701197788121100881304650783900944358367934303538647332945119694362849091301355005436291078223280753310654713741596387831313076907729367513905299597582977894859084467382251110232442313588731567517722, 5473046296972118327495477534670327059922805992783858593704621531789283121351554409848948934507912406403962506436068909023098369828879491079777608783858939477692990976926108359125684410236904067532064874993279097186185155662101906258, 13591367045303817756921606989622272393926672486200768156018816106702906007663207108105253090224421463114966486892454772900918694500736413865138170304122425783415795355698366106633741954984452451151018930441346568620455282531777867950, 12837435207992697390990569032560187426481997222586386722777778699242138971828789676884863577995903428553893241998604229610814215105950418432582043279620338868532002049158799146484208974875466555076583060832418045530228962180626040480, 7316640175294137713314869727957150382096738798129711776743606346914726499175960701433782404417244551378443800105185050713536694756151112399465628411989410218214135853671061537891268154389537857467508049690878544281069813159134447208, 5151376884557358987102680932801796401429637582605742653829100435795121709703076330975777361528309737649265350014534395043422641886613936452263244119523616000835976669901180725907500239783554884160601160568746329677044574260523365548, 5544576622940386549335576865087877596617926099466042134500548634035376720895126959440244093852186422501431889949044217654362265128303553015621478863491100875988057958166746762260378217552569885430432535094758534858841379918068187007, 14799083878004905781143009556442469081112262413659889639288955718256084634190461545010854679353463115437573577978160713007284612958005397981521383647283702964407693130299777274799243953236030640570493768398572551239990227306733506160, 132844788313325827023495191003662944917431930932901448945118978538428738126330451739237066558502122063099809045229187297346109539648216961234175022847902983869276754945800449898074085412283494856067025963252580204722767954611258179, 9997725379291207116745319316287400946107564644091980910563413554119585263470477093970564227161564056288461504072778119028907789906500076760472149102049287538406258735529830965640424425566731939511108199132607994947515509428756592559, 14646376958061531925518831995658673407931262101501970446265549357832773749183019186120219286620900718201222809743448147362429133751090137661872964022623647740154174784462365444772177633656555414706757146904500779085225231797377050144, 16961346690251629621986345424487239681148326635080182277543308482323385918405862092823934592459138523058683934777987371593649364181974320355468882733898473293716092586268920136699107300230769779047091693711423641803330962855097096925, 2618594245402239609420638325588710628729298505557767536783081437084561636188823448848608313088279895767614513680617644960939796227640357345879653043764575378231433481016175403223796690453962090038403036583909367766156025584252164203, 16129071855649587728956130797915283397821444682369014639788931828703405001025452386772618008541361124591860437269977673096643234091339097919538256670714042876788038021148787313041232229195101391115617710413115586617903468179658293636, 9296460193370583816070265591004199836116409032475859821958373154648206416256688852532615798871909770401306092671009539709487113538354105710364096048695663733075506988691991440779198012260316123759636997605427235081435477049705160552, 1356766159480311231046092117641588893355352105595481615726950290176811339998878309107970938869998059989877968402614403581962019949583734460209881480875822282448127936842922015950977040552638984243226561237288675211033594559512352433, 19197695297715405687227248527900901092786200526800375602428770624109373871809940359427277921210632597272639018938714964263079621574904896862536158251668755864087715415463131002786745060027810126535070270462254705453473599741763642828, 11504919294119244522634617029097854228866432223952020614427505589799731544252763714133524362716131837287869956783968056158486948361614604723869397483955281379172665969413312233383788159684735115665749332738234882920695449340309379522, 18136748881313347797489256490303008973958797121502583070872297973410283357173931060145003395290313809639159364452878423212404968100529416632370960280991488248897643385077173546644657216962479904853980225967792378564740955618790869689, 22555443333166977522691347301347007560400051480503434282172981846969595435546624498334336147388425749569732805395419970503066627849315134643618856767862223712319227590572187001545137380352712433069385477809940371396279834624165048444, 19332410102472644041731759226399070707013106727087481077728390364392367890410961009071561108596168685943298518353047413086954964804844094391018967334543408778135737715163542892702469367908397906585577557910294555212057020330243744038, 17177417284468945229490862308619539417109492506914913062877431832846296734201442477935598961820079857431068892933310664489209467455843404117024994948398426037991145460135427180175565761835499766689618253941365562391662494080561342044, 879611534766674063001632328710680301710464497091520920338941691285492779988149399177086528073474651179894297281827841186309099576047175634809922453338033325127493237666384356566986210156156953604218009901589731044248652021118031620, 23901207038202622707599557245612794049853792927287360450027492049407851837113641371314557090659548570609882944974639719117613653182109642059819516444307658547936689472901123537159776992389462316392381501838566991389570490374017025518, 7294655103119575652652322286451546582028529239995283561722077129773315845389577738996103704019032108880990669128684769525902413906863125164280686381766699292160785541839733876768365575818004233647829515890263347139003166333882303265, 8199949148068603717078157517861527127346508355755818050198576663971835822831527608360661637977726638149791394376076411543777469889828576151097728735193348069053034445800818498132875303434000618724830859612380606691308333135184789022, 12932127055873709636118977200718753643697619875736929170699115793566554057840448101626698069421491300195262169693063575726920790612681778762496689371363586507749098405216335541209813518577176560833970043581650697105699549343835699165, 9917293893368177421397475427602509319278773672321383411846980082270699518174858223780569843589979834443168760567064326549648560205061679870738748816216468066517782541276129041173215780179108422815701857032247139868407259633376154559, 6485828831888305306081814677813540588127941945945034779245913009780868830245510314875533356179894354966906340154886875373143060627077170845158967404313883218225671724777853809740370308868692781589580666606866945869996719967294318732, 19119951246631217104039346142695133667127595492295413599863780403588391811741379549048868909966290463800864082020118315313386877862668618823502190910178365164478013264098319748585627290011516370646420391829298524728641913535537536764, 13215772369693604102761934975932281069170694713655356522695565074039936506383846119163879883348265869353744569056003177315023138985010016601208933546975222998897707503967398686672700803569601825514347043442257463097499547507964305449, 1824804736849693701490461807874708098331129810367417218087931080176315035870555627969047286436604549231593492189121553958901210913466534815129733115561941853007429568739121822292088591127010504328963864942012956577043433126898293277, 6776240363305734174388141780584391816477723528084755437932934198907331150157541368203589425111306785868566064140117304971940704620271781717831300158164114203169466745769627304177491937036545708540956189334174616021603617610568750468)        #给定最终向量

Lx, va = Nguyen_Stern(h, m, n, M)

ans=[]
for i in Lx:
    ans.append(long_to_bytes(int(''.join(map(str,i)),2)))

#print("向量a:",va)
#print("矩阵x:",Lx)
print(ans[-1])
#b'hgame{U_f0und_3he_5pec14l_0n3!}'