VNCTF2025复现

发表于 更新于 阅读次数： 本文字数： 90k 阅读时长 ≈ 2:43

owo

这次比赛做出了三道题，已经感觉燃尽了。不过跟之前比已经有很大进步了。继续加油！

1，easymath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from secret import flag
flag=bytes_to_long(flag)
l=flag.bit_length()//3 + 1
n=[]
N=1
while len(n) < 3:
    p = 4*getPrime(l)-1
    if isPrime(p):
        n.append(p)
        N *= p
 
print(f'c={flag*flag%N}')
 
from sympy import symbols, expand
x = symbols('x')
polynomial = expand((x - n[0]) * (x - n[1]) * (x - n[2]))
 
print(f'{polynomial=}')
# c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
# polynomial=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619

展开一下方程计算式可以发现是x^3^+(a+b+c)x^2^+(ab+bc+ca)x+abc.列三个等式解方程就行了。求出abc之后crt一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from gmpy2 import is_prime
from sympy import symbols, expand, sqrt_mod
from sympy.abc import x
from math import prod
from itertools import product
from Cryptodome.Util.number import long_to_bytes

S = 15264966144147258587171776703005926730518438603688487721465  # 二次项系数的相反数
P = 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923  # 一次项系数
N = 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619 # 常数项的绝对值（因为多项式中的常数项是 -N）

c = 24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944  # 替换为实际输出的c值

p1, p2, p3 =3868765709106144154703556118635822400623994075212553582411 ,5487564316951417093934647798659941512646442958127439071827 ,5908636118089697338533572785710162817248001570348495067227   # 示例素数，需替换

# 验证是否满足生成条件
assert all((pi + 1) % 4 == 0 for pi in [p1, p2, p3])
assert all(is_prime((pi + 1) // 4) for pi in [p1, p2, p3])

# 验证多项式系数
assert sum([p1, p2, p3]) == S
assert p1*p2 + p1*p3 + p2*p3 == P
assert p1 * p2 * p3 == N

# 解每个素数的平方根
def solve_roots(c, primes):
    solutions = []
    for p in primes:
        cp = c % p
        if cp == 0:
            roots = [0]
        else:
            roots = sqrt_mod(cp, p, all_roots=True)
        solutions.append(roots)
    return solutions

primes = [p1, p2, p3]
solution_list = solve_roots(c, primes)

# 生成所有可能的解组合
combinations = product(*solution_list)

# 使用中国剩余定理求解
valid_flags = []
for combo in combinations:
    try:
        # 使用sympy的crt方法
        from sympy.ntheory.modular import crt
        moduli = primes
        remainders = combo
        x, _ = crt(moduli, remainders)
        if (x*x) % N == c % N:
            valid_flags.append(x)
    except:
        continue

# 检查所有可能解
for flag in valid_flags:
    flag_bytes = long_to_bytes(flag)
    if b'VN' in flag_bytes:
        print(flag_bytes.decode())
        break
else:
    # 检查N - x的情况，因为平方根可能在对称位置
    for flag in valid_flags:
        flag = N - flag
        flag_bytes = long_to_bytes(flag)
        if b'VN' in flag_bytes:
            print(flag_bytes.decode())
            break

2，ss0Hurt!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from Crypto.Util.number import *
from flag import flag
 
class DaMie:
    def __init__(self, flag , n = None):
        self.m = ZZ(bytes_to_long(flag))
        self.n = n if n else getPrime(1024)
        self.P = Zmod(self.n)
        print(f'n = {self.n}')
 
    def process(self, x, y, z):
        b = vector([5 * x + y - 5 * z, 5 * y - z, 5 * z])
        print(x,y,z,b)
        return b
 
    def Mat(self, m):
        PR = self.P['x,y,z']
        x,y,z = PR.gens()
 
        if m != 0:
            plana = self.Mat(m//2)
            planb = plana(*plana)
            if m % 2 == 0:
                print('0')
                return planb
            else:
                print(1)
                return self.process(*planb)
        else:
            return self.process(*PR.gens())
 
    def hash(self, A, B, C):
        return self.Mat(self.m)(A, B, C)
 
if __name__ == '__main__':
    
    Ouch = DaMie(flag)
    result = Ouch.hash(2025,208,209)
    print(f'hash(A,B,C) = {result}')

一个看着蛮复杂的题。分析一下可以发现其实是一个矩阵快速幂。也就是给定了𝑣=𝐴^𝑚^mod n求m.也就是一个矩阵的dlp。一看到这个就想起了去年的XY第一次被矩阵支配的恐惧。参考鸡块师傅的blog（2024-XYCTF-wp-crypto | 糖醋小鸡块的blog）其实可以直接用板子，不过我们还是研究研究。要求矩阵幂的第一件事就是对角化，很容易发现A不可对角化，那就算其jordan form， 也就是求出𝐴=𝑃𝐽𝑃−1，其中J是一个上三角矩阵 。其中，𝐴𝑚=(𝑃𝐽𝑃−1)𝑚=𝑃𝐽𝑚𝑃−1，所以可以表示为𝑣′=𝐽𝑚𝑢′ 。看官方wp的时候学习到image-20250224211712275

后面就能求出n了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *

p = 106743081253087007974132382690669187409167641660258665859915640694456867788135702053312073228376307091325146727550371538313884850638568106223326195447798997814912891375244381751926653858549419946547894675646011818800255999071070352934719005006228971056393128007601573916373180007524930454138943896336817929823
G = Zmod(p)


L = Matrix(Zmod(p),[
    [5, 1, -5],
    [0, 5, -1],
    [0, 0, 5]
])
vec1 = (2025,208,209)
vec2=(17199707718762989481733793569240992776243099972784327196212023936622130204798694753865087501654381623876011128783229020278210160383185417670794284015692458326761011808048967854332413536183785458993128524881447529380387804712214305034841856237045463243243451585619997751904403447841431924053651568039257094910, 62503976674384744837417986781499538335164333679603320998241675970253762411134672614307594505442798271581593168080110727738181755339828909879977419645331630791420448736959554172731899301884779691119177400457640826361914359964889995618273843955820050051136401731342998940859792560938931787155426766034754760036, 93840121740656543170616546027906623588891573113673113077637257131079221429328035796416874995388795184080636312185908173422461254266536066991205933270191964776577196573147847000446118311985331680378772920169894541350064423243733498672684875039906829095473677927238488927923581806647297338935716890606987700071)
vec1 = vector(Zmod(p),vec1)
vec2 = vector(Zmod(p),vec2)

M1 = Matrix(Zmod(p),Matrix(vec1).T)
M1 = M1.augment(L*vec1)
M1 = M1.augment(L^2*vec1)

M2 = Matrix(Zmod(p),Matrix(vec2).T)
M2 = M2.augment(L*vec2)
M2 = M2.augment(L^2*vec2)

R = M2*M1^(-1)

gl, P = L.jordan_form(transformation=True)
gr = P^(-1)*R*P

g = gl[0,0]
t = gr[0,1] # t = ng^(n-1)
k = gr[1,1] # k = g^n
#so gt = nk  ->  n = gtk^(-1)

n = g * t * inverse(k,p) % p

print(long_to_bytes(int(n)))

3，Simple prediction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from random import shuffle
from Crypto.Util.number import getPrime
from random import choice, randint
from secret import *
 
# flag来源
flag = b"VNCTF{xxxxxxx}"
assert len(flag)<100
FLAG1=flag[:32]
FLAG2=flag[32:]
 
# part1
class LCG:
    def __init__(self, seed=None, a=None, b=None, m=None):
        if not m:
            self.m = getPrime(512)
        if not seed:
            self.seed = getPrime(512)
        if not a:
            self.a = getPrime(512)
        if not b:
            self.b = getPrime(512)
        #print(f"LCG 初始化参数: seed={self.seed}\n a={self.a}\n b={self.b}\n m={self.m}")
 
    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return self.seed
binary_flag = ''.join(f"{byte:08b}" for byte in FLAG1)
m = [int(bit) for bit in binary_flag]
 
n=[]
lcg=LCG()
 
for i in m:
    z=lcg.next()
    if i == 0:
        n.append(z)
    else:
        z=randint(0, 2**512)
        n.append(z)
print(f"n={n}")

第一部分是个lcg。可以通过VNCTF{的前缀010101100100111001000011010101000100011001111011。会发现有四个连续的0和四个连续间隔1的0.两个分别求出来gcd即可，然后正常步骤恢复参数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from Cryptodome.Util.number import *
#x1 = 47513456973995038401745402734715062697203139056061145149400619356555247755807
x1 = 2904118189775120023459019968272518649734695395069048986022437844918703975644558115383392143444650105913452409637755020483723178514755099834451835881760669
x2 = 2496347446622649570739835604330702398623655492993517020989697292987597836476885607585376289637075420196735804815963859430002179996807900803924440985064670
x3 = 5092430706888567903864571522791342607274393841524837952939293151143112873052820889489487455424060318331863246280679543283523935851978590240976374837185862
x4 = 5841875905599158459362419364618142617028730211782981879796170746183188377680781214397263518308193221936236231314886272772334955629812227434225018741466206

x = [ x1, x2, x3, x4]
t = []

for i in range(1, len(x)):
    t.append(x[i] - x[i-1])

mt = 0
for i in range(1, len(t)-1):
    mt = GCD(t[i+1]*t[i-1] - t[i]*t[i], mt)
    print(mt)
n=[3112694391042354926773258527503185381065155208766365770810259125227315858273584882915278974659442759713556138602562818381472824625797498323576227136840540, 786520206240723735172261009757420248240712167229385012959459782880298311452489264350397371063336640624230104453428663597776321434444090584610343945793660, 7754569747576675124444476463859698281135896797237129188325347781614403755633169372944514845375944974591833050594776051023970647718184479538589092026997450, 10978871322047154319303427738666909216134180533239441865527547245976955391170539397404213362987538079999656622797569425035497528648628186801889140680115470, 415184125088979230381868131662306705231430570032972141500815295250568658520820987452099753091555506318572984156087823561918067558858879113735437647918395, 9714366912431081171564906464961880471711707698812491599768023751085458677159777579545968149071317510381545022553352967040864616769551211477245295688346391, 8092371024146035837349997948385163397190707017788806800986026897219622319284668919277237868044873010504361887344482864009123696754405451607327057609111440, 10436585428619509784309464150307931296272516984470192973796220477752118208825366154709099054615564535911017032120309414411717936665468477272752593939807490, 447305603342948150664988784745387699519951434026852127837772145868706495519135216852266467924181573327190271412684871626668438866189143390133743425082693, 6258382789539676289638693392356433976508824529535654981585175361893403855873239591388514679492519869137377551632089436526817168965584123817538926883004415, 6578459280281502789276376530649184418554320975674197078167114333423000507810642180022772031856026530862489799383804073813561526139629854268000350585566612, 3105804271985778113444078016881015352567661906301742072344003729902592834090816086716179301421395002611330071836937959172008751915356371544312148285941397, 5127587678416216516561596462057578930989568244549184602544457582445902765146101086132777949114594616892034555102233884229669532953434325912113180385189591, 1681442924588151639116433276563473534451382602613595570895775581721843149401494979313072945423375889819333272799813140736767061166995345688865952524678847, 6078642869874003200723208932690378645034656959547344879427148548997772820000250634715135248051520273525771098588692142255436403818018608325143275974733955, 4012523361150861559330864221313828963018749453209042526129800867368717777138746796940156428780116853299962328653590275670160641449729061424004869739613567, 4087452535062195595067394274200281754153594561224879880591706612010600316823470426560921334571972319206745275769663537296296835581079110402423097667972149, 11987901353675361726480103030921089210449430771045316299988549316092607271793911250199421541491725415392936441323452384413917894329798638712720319592293030, 2904118189775120023459019968272518649734695395069048986022437844918703975644558115383392143444650105913452409637755020483723178514755099834451835881760669, 2496347446622649570739835604330702398623655492993517020989697292987597836476885607585376289637075420196735804815963859430002179996807900803924440985064670, 5092430706888567903864571522791342607274393841524837952939293151143112873052820889489487455424060318331863246280679543283523935851978590240976374837185862, 5841875905599158459362419364618142617028730211782981879796170746183188377680781214397263518308193221936236231314886272772334955629812227434225018741466206, 8822998220509619232900481169697664481537213687243135055737490918324236635625751932015349246530733060787880922400103357011039056263913931100456275760018751, 1829427301393099155994835313687991302426344894851330147851048073570161235032513979807480344356619367183014749159832405667673629599879026930073212395410824, 8874937378716753576850453573789326249003541019039439656124625436218713023501508466125664186477683313567607343263520908371451243118020424774779416613284431, 3094214719436429226961245919063208815398034554284969326313725322674015836263311873059825341599355295801961834907564360317827855287772012048456233770648414, 2272952363017630559556957955923359020608484345799712462629628170648722715295981120790102876295983654085449309744008793129064000312354978267334570450316580, 6496050086593645326490832279816459396921735500995471620086880796676279174314036559957741604751933054571983936020744588504368950464191967946656677942899021, 2908005781806019194373618893842561631858638383291599116857909669689194340479675737346427303495425892274736979677443740297777253232987190979789663078725548, 5388837765013859349244026248246407908254127661532056349880470355375929571123210403251766195449198851516630257699755053971912164119717459739252423955246030, 3932085435203368987040270370169028458481400198383481987063012025485880158374650852938797303847848555222501161881776438272815556194118123494398521291295697, 1596085666232061421423007114092508353792922600947831965835268732144143785280657330672864972239387627022937511560443766910692107622093754834918341508104599, 10892117681611280686941153150032271985229693373387407787226285542508269134168395045669092626668774409502094484729473636367607949115031549276342640669975082, 12381058972410501723509665604849175514380953105941348450275208477068514082229866560978025193499168665996771831648645890812123306116098698670457035525902659, 9545745033067721027306889070190247803420756540371596488987366683285356423973234015839573919673127328959418729409177485348542588655200727033820634115195595, 4479761395800283662690601296359321028679912967664335513079404387374415137823818474235937843015783541121766513461305964218999844148219102416295681398216273, 9156731911027542367340528717851854633542405024204364589600569440610994301305995711122403415955733016864883934476560189254464831525094631266907727317565841, 12666226165843230393234580593668809584406452210553760075587696529746311224658137054868869675868832265128577423471263099176912917347422711319558934937736129, 7737065667550567883921030156559155888807672386984437450593392652512287661221384706140560800013674012584773711581005691186997689622045412989344796050391287, 10722711925660632865003648114617468567460695864602168315375920133514224919874108904883202493206779150508025208748543209001260228655832044340651286693647050, 7221989584178899171245167344240261714028153334248896620632489515820094543095415471986280548321052175500724972199931711569861834778349006061026371650725530, 5886738574662494886015789010409089525104778409243680958758049475066582248064522621093649220502324554901044951352389897351932045257540701040679720673182995, 3233031164922457118197051143257856436060509168643015516594248999051329950677781355031891194479912736553900235538373437012785908680742480354059763051926316, 6920408828532601456551620626263287997391364853554222851307650268338227244737275020409310347012172074480549705970215944641795584739931068420792592364550052, 345138692120754413974989722062354894985124386853626820051983950290560303295350640053596083432413833430615738137403155513172015508429643499448532812238302, 6496124631023407996096728606763442237866253608920412620007859687219366730708253684245052162774841972751074153467713038103511069685477261845614949446512946, 4954508795303987697183186252875587490356341561311441407925804955497204676368654384148988141783982847353089058481160501471777024753759971112068258113214565, 3828140752986076468811884163754926568598858918798535569519010381565163308453577351104319634076150030767168383992404786769678070072803711746311572209192530, 1525344587067629160366462540930365317799240672047761683713335407426899660409450594374673147296233196946100880479779947899945565197770752720138099788100242, 5602028537128071394937385481766099952197676084096530706435200857779681493800600692877392655529445220731489748219807533708510871522082289298454440537081195, 8405125104396694306214164667837515476489019008711529371739198500339529156031577667955991513091455659686200628433501522614373035120915300556389897983235246, 9363664670977587308719921639117126893427493571952598074398598354833859096850631443468609493097644882813856223675425304811178510077132476076498042910645127, 9349867197915693633449346578490899128090370835059777452440405839315024154505729422754698383796886447011859369467724281722489773749407392509326759291555650, 3097954855336969231133966616412205217720272446131201205394739397914294852319995680869512637191028462644642196360432400206940604220726553888843484631971992, 7406758029368015050095014975336874387267990662428684874055990633074940508414476853156912578698644499480936056505695505471874708394209454863202578629044781, 5898320635400000335689178353860464283085294033102742946598413410403566655371101483965016006968842853067086240043017626407973320006397434327924399698861420, 3828259549886515897088733478568758658537872498350930339786355733127243099368094714942597822674100789401305391925244644463002021967786404115828714481532179, 10066554692829027637519103501291436097875302262643471195009455832708625591378453822850465340538716551878294551013391681787809106196783898118863498888850156, 3499720133059334106382868629152269068830644098994082476913546750309451292524899143926086345071167411724519536123368519961201709328076205428843169312885318, 1147510368324353143366569189557814239414538057284528926807572528742387641385961348284337024920835614354163427666397191709805222814485017032618600205989876, 1376443474120809546746657939759253350130433377066673914731313628744658444788621480850904944725428749861684141267366595703293257102033695543353727831255656, 1306141012932794251921296999513356011857879354957485278247781515633351554530888210035582022397642308827310053200134973752059059882857529726355628496875096, 413876320654674539071498590563731546775652768958703825687302348932338816891646970452489274333920514493304821523049953031604718378578195970800635452979649, 7136032318103206577710213656015300850977662493466951627466129080713148099950022004835515732817999372224984465182016765597112698961144220566693638971519180, 1756926746502930493055390730808057897946636149296690801994682335268478289364240082508380322318466774154683071200098564629218083632205594961758297148916941, 3316411454937759862626366549533032628711020533003169223587018450894240524473337491784683315945222404515083081588061970401834062233395245203672377474101840, 7599211346182071240062546116924978763380850815873927487248272261113823566573995151834356651681181867857513566992756113461907517519948807226796425859877955, 4827401360947748134984560117351749331549293418478129984842609599519150402230303738934321974655033540771922561714741710181107247544509276801554867550554777, 9961447244710994569376297896009391492177427465332112375195390069257789445371437839302033237974987420665106837111388126490588618960984274087531285094868463, 3970825380935714034877349217971517028903515186410921713051743479793055944068011846527177266662364107500948837234030225959118382828207676389015192534929256, 8608544722853283040859357355424248470567969517050350679760824632753430693341742456610190512333547560909838869247382450069074859055253804037930976168108964, 3997948190249595469689902562163983268236884055830515360341250116190801555461654583247875794079436239650479700066689264532083273326700382295037787195625271, 3017769504296172462769603649703609973556946564740463758564555635077678423150496052443226378694972314861078002173292765046041599543542556913918523347263353, 3018202344977285583885683841870491872320206187912942548780004839181579922416791687842887038054070620041342514501089785820834677670579439549543511926064647, 9891097413298322102982137409604486446161539669050452171012014240832941475729480282491230607708654307021437081745156282474575662423373832233207415281381073, 810743817397722331080383625060943517758354327434640227828749606831684964655697897139622679395918034416371573980787570599833348592060893531005764737629127, 1969958301963944803918256770227669804705344374646067381549018696813216352795715044244066646943740977361192247676332396646834038434975510833138637230427345, 772283527249875882597408338501459146497878473259395153877255706812399634121008456441522976339316844330687671179329753370897387217142932695296763732889342, 3493198662567460016868275788342486589147435611953915935411231579476989982638489118458485903871892142501116430468467002727878349586906097406405889235323788, 4521188033318754929745682253319078580979772923679656226706453809441157032758310389926223236904310972501023754771832793204339998846509477714808315607910281, 1459294332771505218116793124065248690329063109957541959485115472870135095063108761273775418742597190233931321103250699825789092987319750533970824729614370, 6081872280435119283055308076930153339025042098756094797625575179794067581927871061960272319874202717615426152212739549866438480879214105498282015894463289, 7762130387850161469171952821282759615477419337477617017933774362212895431284831425608213005612250003857841615618062878428976530194088816674767021581918361, 7088966648042419634447311723094936418341229460114395537643458905920051387153662615102678231749704070491616519620338946004408977647690235277763140459513851, 8530607388577471706676549252322039165843846873546376646134620680688465635242428455911769685950893069368467175196898490905630827271869358438258138367147920, 8175683960847863703233560555156381607096304894990424846512919663587601289791899748077484807672241130846328052701521081221552165331340951019312677944858747, 2488623773922039763673766132557696145161284575280912275615079393811226460826881195363265124937419976718725662680265519090252785095524620609995052703783900, 6288863230409343367237321449257176176239557761363343791530360335256224431868618032002438377834667134601271040364141807479673109178951459313279813775639777, 1473263923409842234507369539073445638835827020429470695919107120414932038000731541162435599563211189312718420865785265955929068440558364834918540634523353, 10122097127617668407198385940571219425968555754180743969424837212320822902467269904796129323894867285839753668577231263726601359268499019654139049664492061, 1334784462377268162219916937778259079061709480108638225731209555525977073101039827877859407920878225806740943290613416505735060002712675764508538108047998, 12943474412664177820782360094982469843501041500422827324429596710070670418547139028323568955260840820805331899161092350732997070023024881720076933509023643, 5285767084748000524025756084248068414482830127641006763000905479085771014780726785155236576771987096323025767003001338650450684709507257843571038471056162, 11001649396182899266919450751411831463050029968134347011876378247881245085871285736635385336564047956680944211929032745371792404308823898143896080599228135, 1301320300483174681160013837223931621343934678403403829386521051889935307860390561329187310217511171817846283842794896111380527530069209283005624028690286, 1186915169823582113649731511008826333372778559188698285519935265619430618324050874482684013915987326600510246581904647268399723862559309332791209147350358, 7951498363952334154675185909940847757383581919338786100530712059201526109293278830582032249111527249008525526574896069298049360688844794969204346487119319, 5833834084743172317761925197221701570183986273711410703784510000739316288591047658081863870594678124768673286740095552226723863847255410312004390417932230, 250924904422407061995835179415107794137513805961258172932861317085785803121995475899378133391840809508281610679076388256556411152107191872088591037125680, 7085080737844307190711404281467289397811408278819313361734199078382373564224746415235216310673951063158139882956733288219404303997318855194384556303070508, 792899170302377369245819488181982727852356501237495658820211983447692560703122438829983042374409125728040070525543893080924041158974511859677083096607042, 527158028815181308607570985361245658684704283756590449588667033857582910233360333000310180939827834980467750511349128724495152296557091872597733881952730, 3763863417935228217913891578022090207665435628108842338881001530218617625267294739809241731373814499577113686300212286948743727581910857164406047073435145, 958455575406045524652006754606401195502921703814444942723242685507533790960715001629170021188825054149374588782230350772396669475019050028532264494574237, 9809663619882688389709117706867480374978776635047144310439126194904691403735820159227260919973742961860862039967431466740149997606037421959899675267867402, 4928087822912964183306632018065153773912015339056263025033437531290833406852527367467717772039503136111382784824674765619106999131274189533695412345998781, 3306590088110759567187299302153921492468384287750726848496785861124840118140562928463000437634919111218431272400680022915536959360708451855996593223449881, 2515345284450486657989564309908638223504506708787471236561574408125887414773177664899850115276078830612044843742665254526234379016665896380411170870041898, 6134916597901963206086108654185719639522683238742250523950368120774398123587375425774449196409974448759099480799449712533937282087807450665513782605062516, 267008464052948389884730662677557220200174254262230501579203365622730336383874495035799286519129165799047086431118526490317359253783923412623429268099578, 3800295810128139174303610558671254854105124434132150757436144235620260340163872195459646695446468969827264408515318839301568024785647250539243955185201551, 2758490331762821125743858402061695095981818993449415737628690206586999472874851271575996243559646503027769536546139985948732741074951448605054447471168011, 4217864104379220244652908183473678097829823483575612233951544943703293030152224382038691961310245629042826444658756962561354248059403145303196082085209268, 2411546292849014551581200422109249129122050947218550703776810780058841000449832253829636107587459795899860908579554012266416092559036860375897058675166409, 192467681052352162362648778226726733093735914360336666620608894524451640254072987304183265625190436964732828104328784706266808876860847345878920907323799, 10212417168067454275584471588910621010044875852180765650348231827095954171511730230293551305771510545238294425677591538289639404143154924489749365048876082, 6291496406676715628304428700100747835536008647518931914594365410721760743785935426363197093622520575550738520057474256623894578595520825692491818636334669, 1696976360861070329626849480960267540656072393087503300209873513633034266528003865510158759809700233902230575591392391573852821509573062950235240813129994, 1992791476006726756711658531188332687379120992528518705617488065186657920940258074136462208677189526448735990314312679768851854906262932750351345930936464, 3434817150940057687962615407673182936576770534551677026510420824040773940701984366644277648090615900140073539389288521085696480983123237694035190924420756, 1327855956090181552782945714409707635753546680351411598218049923377836087099012280676631016119197258537564513914523176743684952405144923872921314136129035, 5655624154789660915581443648297353167129398768268548216939084854177411698912475597846603256287206167209756880556116572180333055932759436594462434353693400, 8830059371095862735354543958775333718886412721521896475178007834620722932782486718721540179680672790557809311631084845372799308539284214436640810453484170, 1577636678261904797628136271897055906695035001433916913766563447593237424148338744133061689583362391559327011278037905021569850425130860531043753400763154, 1209729863382992194970404071607689320320688269277129054249972346057995988562627526632203534824706401031451800965862577190219536998333754410251454193172633, 10994737712981198858904493523119510510407890704351172608352260610483503932115022636292742662488652484884065872585569714312792595965194541878114072128785076, 13312794948135247102302068858829637693388469161937738162205887768730544767479875477575282537997374804153016347963677479862069345296678731832716900899603869, 879671866755667260350450894660321566144270667616606636933510913412039991903800808345026765023248799436411333541403195209188109276098614860327117137466333, 5997701046258297701008758042981450104850958281608082374179429160139658833748115292822230978073016551491127587310846341263896220866877950242984465975300314, 4192012991959368360991053529958905352101679048106150398842439746093082099247853769361916275353786757483092523746395483254419836006982430015840596420354690, 68767193809701848990678228150938858317438882331616019798227278054229929116354514010496742914593903938654686226703764027981691726307067924749548639740514, 6424878254160617279031510897227083875408892211834672818183106791194425743856659680167277082328488376798715553566764040288391365020947404294241085942635290, 5763317249464667765660677954026422164094163991588225333425943132102988790548347316637489825630840144712298171981025912010655441215703984407721949790844665, 9435550610931315332910244565308657822031673972676538747748776968398830747049322827689121854214080946112570463640185481340896982590325205419757695986071062, 10854423772658513176079671341132085265897789527203502433443146288938098731162432093760781299761018039572586033382650624844107074319936079541582027150668547, 12476951609313059069935100486664524689307116697672515206640540269281371069630100802734228826553881969126349796880152061952354015124626549756257692927815280, 8045796521414377185855048953350733531835029059717165499998684525057576005480100656824730185029760232662916675149548562588330925933690413287605746764047837, 7525718525168133704091970516222857259732335150600005652272906993418956544265228434139051120334482938422989961682491729150475586713499313679353043034729340, 11912046156711704412939411921254931438505716185767663797722530582823134713864014317449272059238099311015018796287244119043500568755668077884967429950325307, 4110376054901462563412017964610800633712664567375745109340224846052194476233004966740187585207654361057339454338701161199087672786000039131447606734749596, 10536181172701505461141355483962316021670309715632294804091924062622834181954003809472637335749074818053519805212673316386352637871822409277633843138677100, 6561239288740833507622012494260145838556069026796406502850578760529949619677685073606417050067995286214075860389141224570430897217267888191050083989435618, 10755390470562648902207547773646277461044027331578910788260151451952594114771257491457728262192103389098572788952846896691668034250236775730674370420267582, 10116754295180959057177541778544392071102857895532245112951561295322574582916144106425865580948674586957980113764584475972905926764533180433076299516058008, 5859608878417010984159585842628477069743251659783200679637533418043397666877873263920551182367857303131476266606376419613220550151623797364003280753673346, 9610161406190042620740875536112128010400982062708691775804712654931587490639820436686157097516436685664421116711173966237809547051696258177713532759654622, 12952646859219149057230927632784421545288507757341307005625287549328732462625896748866127565993868137664264482594593443044220358257862250213102226764516290, 8743024327867380639354449145506317134407105263681845312476151158834148293426515624801487795913107735337606303607388242940871402388276005920082857880323995, 6528451843739479102149304425458509059040659785241941228418879086912730488517357726536788993512031451564270545373930206730980948931647991797715441531367741, 10462017518740882728109987348635133411529189768079438410766717066737589074298615526836492547944144729306982384205899274858973867537303267274981230305808532, 1029921233837757648214250672123683540325541346243252184272242917208678427506067856700714176359513176639295219124015583282618724736476654390655108055903101, 3813391349261399004318771186005512948966760302080394751195459215339735976452080345673275015650542987881482072724697347920803923279413761484112487853082830, 5567045996050241673395722528384148064949240335449353538914263526561311052170653310179306144459952167489810559452323829738704071952158894333072311035879031, 11425297405286583197291193457049007771696095735039713556631639136073340052097230007416451599300613472366227651608125018305022847691340936237133967669922708, 5133133934348577917601648370305907274443352706523623096373752926891789513077352342509229421888477870704293827297467947756322460298412074338824202790298662, 8132583894883560743002824283673059816431507792390355426553765264038429014617881701178853548832309971139375526867381359198874199379920890215643413694501114, 7552142578261419245883966416284664466068563874971828329265494939813613106787130369752313075539493006907320849655211358140332918600081468802258749834843538, 10823636389049155729021217698235275011474838951652434077924344160818782418898312855943115619327929826005003323014892881057453251153402725743243234607047481, 10680178872406574919448166931611181564572199628533089837843429528532479999287256411849181801583448430894803286171601591142410846251190917672344726710377690, 2168298508401712132947640264694148303021343901549723681847049388089284984960261031735310672636540039445007659961609332757733555056471192184304623785463060, 2340178702773145350053705740794686678526767806446745613453910417043858008824651357776795006402716690334747276104571962770647451951039149700422444698013803, 3676298624367829693533841137950983513080397676021901937554619358758723840281650362664181823578881504253223943310514005188069688898221486997715937242429797, 9132445874585857701581851483501762197628317164635776743478088760576246356597389927572170525395684109023421565467382333814897575731125181545766414622099088, 1236243137925014415166903810601870684462468132447802699390566421129254384151914584169607594049615635949605059072399537399196990015228436722954103224215653, 13192075450313439458696227018221283192704089241176023475321514991073667203620836604426092029969501285268881185351240634985221491469526250478508196558288498, 13340639364100809037776647351288754791685500736266676042688472470296642180440487353725930118463893112749814096941496617412376513086275610553120671630855204, 12822843338691780139685033864703978550175201484982849212488267516822394414700586371148840548146427825919367884837033694191706187378673985360389045663493646, 613106102654076279293510245332160984832690077838123347459270922197015039375289301009491620920230388814580074219177117250380323403794569894216049212572690, 741345937780857867091204599859352029451792145933730037837181240026649690120879085854889380733270227213298956191657614314852656479913545582102949822350846, 1521203700405106530197194619784591552753988412072513286448479570991121637695991136022481083784343736454948481506227221936397006695094004044673618612260312, 1754355644745564738949734138715924818354376481147066751091700288494806267133747040362706809811119196525834164870547295032589624983098331611544467054571960, 10558001053790364799640017455585652553441324388003654829669801584264580378288544204384753221615914991531668321760943152912316734446688653889285671939949283, 8952741946129854526912282277915463308468641280017071764259400267418376820661617976517595294079266170889791671184248228428255231332246048645399218317435238, 5708781767915765818163443178888330089981502372897875606734905301563903280544280090906008214416992941521745475840179246419033248441594273683211971541021513, 11207314260945436219908495655323292893171390697333283188618347144146103399541626933000695557155317908996729464557230693586167154225916228852820347109587442, 4768699522653814083595511380194045011712422474943867445270805763976679774502355033727862959062082708142553518870516687367912845280877553823018516820468426, 3573404320052684865673874549697641892027200012970524599604344629480614428866510201242482244849851484812706779763531318294257649114967750248177266575351904, 9842046015326295936713113278372276623162309027668703544974484877511676105923564214126300248193166116770085089143956697998095520184839701995830786470588119, 1064336683929673294424950894292146984741870122993750747944221503261933086121633737427851706261755403775672810611025441884538303946056267106936423845713730, 6119365214772078724433453740633652395125857443726005119583473831076384223906106649768079888760939037051562253507550245597366168645023889061250894710116872, 5602011006464577820650860273674214314948301394399362583056956812763168470596401011938904716955876179317142179854200420737178701879845622918970728218817949, 10688806197588176452780872184778027232553550269662452778559914264819143186851703377917866670279816566644466846812573511478521598670666245892196227297170402, 5749904848759330691912891772384327613924997567829966591570364086794022755761818695314980583632637028499235341576195664559034461478739838517698995139240520, 1473933381482644649246484684948491018110461317434958015735226919261712432035368580090492745146416337225430662664884870906265846689475144165741263419385905, 3552860753236534406946271949447053351616262867581225480251433378405395606162241270360794601150221505524887454619865625159396521192722639689825266164326816, 4025679965704249310939546887743143184778491366293564444733040608202385243934512959804528152567307183957923258841546784019979277638486471342137039310318604, 1428306100235018482450198029802616624310450179792798438669479546266596806004602176194588533054495773950160676878470790570132527471839589294782804506864441, 8072640850617110855241510299723015162827596185892374204250158932214085926781337179437786602123040219341501746957277147294211685494391786439998863901089893, 2290057280367999932259137216825281879413132565849987663338198789524712754992858321893466864733387202649315380456638047854477096168544359491803121243688000, 5583776997173032351635208701832518352809786960319795099887625543547183445391810022036790072533037112330349602788093182421751334721766510178242249083764627, 5555512621486935858457469521156983776299061091073590635447092107028704208540406733047475719028715045501507903325457398941934254799046940278325310033482933, 7665423408493304559035871431129989913357233723249175120897904121412582167441209612658706772501336565843970245726584617492252916378077133678386752447479662, 8831387806623653368662340193363376330252742297757679694064336031013050629164883790422491632189245291105141480142691855687788119534960055111937208761779764, 2348888614969242586632516586799444957926744624366807832492236485549208397119705715567513397392975902694704991295169187766291349081368111899560720396912163, 10451697705774524889255333562630749622276186482567115240625444048980008730091781659382447964280974139805714329640013256846296616477415783127806162072491149, 3250053095409795441799567001241905982447028127895768914842011332740981667697922880047939854625934995462431986184579852033575425135296743961724555021553181, 9499810476412190124599031127163816885315637762750874334393511360938998873472806644408465489819096250688914013976242877525460146303183679634674370610160694, 92257121750173787195460287712066480674189420505795777943741841246701964816851362584581887732119504356154538047167987960370209222391456428961345119032809, 12269893351335732220619942414611484122117650937343569742545802327578718253718985310842132315303704593709644293158237815585049455555135510973664199958693798, 4854713676085574526662356579768501638557898917664535692967710778955911366151402816643274844610774778935107487406502370514549614685656866640401239202834102, 9656855196981957286865007955477554547059961250711019730968709842838157159677727374063090954692895414472966936147114719942275698429255550218956155962518443, 10148197872461036653889170589960841138898378162938634118741365043648210887779860640879042773763373401039437782724679433103797938447652210218046301321938137, 12461232655674858104051817101902990616915757003991956969221908635021591516205957656336468897180110175709862262579877525493916685242872024155795348828400176, 11515492235427136169798424725612219236309642991625654371183731730027788023368799576473412684138684541479647895019245640398756194511932236210019079278656202, 9312723419754943857232652740523874103277584545494275166317053355215205988412434914584577068344668904923765987915402028853045934303862656336563244048246523, 3434383108470049029053666008815308531590134792871525168902104045958390857925829496103793826034582372819627900181087747849310099323713159750797436731923978, 2052825789517422745957370721388573723182830509538514420501723815481790762140713599082002354654158294047326674932865012220392363486715578383070467708932910, 10770872913090420263826876160012447606018440578288754515724315559071314423506980193977270893366351744377445642366389285439123580143916270246988741122493660, 3565988622227549084653994809440615920798581997796422558559355800295965356685917449272144672382620500366078282458866458096806308728686228192532033445531518, 7987937603217906772125351267418794200095217108807309149562138708773233299338480817569011892602088537590687786738273360905876877211262668458875082882458569, 4299751706784176820105715713539239270215624269772955083508652046435502139841633241153109045625048345605751183584593710474010228628095809207445826828301062, 10019327725978208236277427849923401464013536466834817004487325963890302290677170796473911285913485694471557407842663829711790012758636232851048197562076970, 5138403339358284697884990506322543562700235321736382747541248890065001571793729102717066426165866053641894094061304639478393033286059241545837832925687008, 10228090755344960970679747531229256367160327180359671541949607264521381518553697635523334685658730563057199104095247245691811898629769883344461751738921690, 6938402205879718649643358194974950463903056291457329419119162151731390866418293772450507112272848076046486599581272976892364724913119152308769085352795367, 11280255720158022430121620544392035006266764932889864093174004075437976799530373518170066458122923542435209793375705211355694698012831668504105946460564772, 10650080319228068163548466605116849530751339026717564400609682888875984174584984784963847899953214337418229474398753727586147950082377211001219418727734531, 10461022182955578447294079762112754763429164916076790787112090719603654252896897448344420250021620176006659592981968554934943569081480419128363237489108104, 11294589811045347664304912724217788273217094365629355933705003484228821123827955195688346268644297234401605720721740926188866212623659856349759808546053573, 10141937561124400301982173279180416680599842235284290692072537579079974651828622761789618621457566636724264817395463634439628042740828226329973006978891186, 8699118787845988175954950830533895540464426675170903476797484684827478978776067185352151829468201077173776538174395364948214699466188452645619083202335397, 12490958061653463671303817402993043179356302996030558945084439266441544994731844973009447951262224179413736407979270443372343363290613996828606691161987252, 1024823052748991275918423605425827037473451549824180278380702661915820289501105769305592458213604304944573172116472138059298554754383765054848368834515334, 3149474298239740425894423050918867645630001944600705788108027769951125277410290754170234970933196247423050719031598422461389202024499050176806060679677640, 3425483968307644002385892058719086212716261772924539515575616780270386411164460702988525468502203695427847573359486165370995863584865024607875453113258244, 9705357328007201094979830114725957907301023647515885569874620519288750162367785332310027452079098270484040335976686397008724129688151547673302532800076127, 12528067279527694536201251429187719480507077254234508172928714722834454912280936520459764100380973964883571564905066513102812286630954907087130626346683494, 4939295221340286977967875420508917414648818020752361919936291655865071126761352698631110381573442349498218777369829854206818104532768049611248376832646359, 2674716557876676991359847674281575368289805356457334186233684389337165131924171023207759236886479042433988774018170513891058846936762285475702948844499055, 10349676289323318216282440188630692479357100195610794079000469485228064289679720223872904306548414937443200055514794128504939320273714041015087548204878153, 3900480819251156802400683860178242140508599285632000256139953374592431655484257091900097449715624009719169957853282262679600053131204952434804975419266157, 2936159796121585099460866869138570695590259507075990700680474293606587115834002606755454671199622928559535999084787402214470880864183436401195544493052669, 1910402964444746284044322396240628093197632493543757175428655391794593305368776891166511349255068918199319491778066276301997616045939664490448839333489777, 1994054049614957137012968886604855559867627865708330094634548251426006158033188269746591310955375650972289227494847138366482888524799108481062111707291092, 664156672277686579033231849080080037649291816954378169291815494575299687760501487195938458172766680345439694282832959763390366172814696710864218723261259, 12044194267239521602316930974641858743309642634849533309620090028794964787997699723555198411201425083423798765746532735264847882307790354623613697781026231, 3942539316360593180663464837869649035347833269370669444954316124093202605566882860780981381878784090092764043248538409214215435668807650324046261030953106, 2022207880686960702068864642666908666405232483184555226114281753353758352867196196619541592446344511643385335987267677037992230191517430032349313406786081, 1402014237680608398997541757664483469798911191731757908773293414891741210993904795137778388105953527158027010766967713019151683784055836714091379088238996, 12881637058943520423956901175941737505225045806296925357592011092034362689563279912911015222707490108931028304114733886174696720737566341300608005833745897, 4446045521099199793223577547105513509868334848725869867850590717318036002007864766205849908526861560477907094114731908043120644690316329932058243626812356, 6843700571901946528606304715672203413849264849459277102145538041815013380627558590652117209975927071389138841622127095630503721403593938867412536469987491, 13256848318143610462565698482052498172924849571765498593609128597128856288744955029403580962574277927166646836266532151877185351103195822664044510033562329, 8007697821447303394905163825963623638810259844261676281034344373436426075060169272367362853555194864409938774346873718610793473975936622478650660613171538, 3586649574568142335142000007519269169683528720968659015296196828181939727116591794102325463820915540711767580644590211490688908496713342802724330043476999, 2148119040689733972973040760742956506738676028795873896489234121475047906650516542446622516446652580015262674044616995261448674463155184722665447227004333, 9821340975603221880229361526669536689872783036813557603647771598331800920383857008030217981692547058985852914477757546352817156483366517574263281418049287, 5813002327804361264470951734172772898635650829156628675370575721244579958255509366900200447859958423075692155868720900356225705808715378593075570213485367, 7797546330955985239260874007700903991194636476790757497230960507273760017191030055855779426266128617165810023444274355865827356873670975494986772973549125, 6423309376854507951386722651575201498832084523844636913943763204639292900317424599429387036474652852527155873400886510187492547526250061669125362070048744, 2723152586748229745903509454334751207914828385965393570411858405764696535921255866269049955401523836912464812051633276478078278079367329876200075486862158, 13015397720497890352045605342327942324564547581996425748914656936552529102322496213513910991605691739714270616469070784054074203319779518842464992920350770, 8263750714072311979325622454139907993837044439909377414638039002083085784664971877156416417538871908573087847796602637123926505104604610909364895752078257, 9267773779254525056564451118318682125792816185104222973339351298641137957155502345583271175585245232019586303509714408650076668626619185504236159542187892, 6836655782419927384926585500839864398000979295056246948533536997678460444451885936375070616683594003406321130780418789653166843306713089441814025696068247, 8159919519373712666364879313578240235174260133692384793283692113895762771865201015732235336575594273425244597034248180447729832995339556990068559995962558]
print(f'n={n[30]}')
x1 = 8874937378716753576850453573789326249003541019039439656124625436218713023501508466125664186477683313567607343263520908371451243118020424774779416613284431
x2 = 2272952363017630559556957955923359020608484345799712462629628170648722715295981120790102876295983654085449309744008793129064000312354978267334570450316580
x3 = 2908005781806019194373618893842561631858638383291599116857909669689194340479675737346427303495425892274736979677443740297777253232987190979789663078725548
x4 = 3932085435203368987040270370169028458481400198383481987063012025485880158374650852938797303847848555222501161881776438272815556194118123494398521291295697

x = [ x1, x2, x3, x4]
t = []

for i in range(1, len(x)):
    t.append(x[i] - x[i-1])

mk = 0
for i in range(1, len(t)-1):
    mk = GCD(t[i+1]*t[i-1] - t[i]*t[i], mk)
    print(mk)
print(gcd(mk,mt))
m=10916943396243271758266829435555189967315413084893315714705045128417174415341289341427433287377943483933876693839607971139318822507789476490876054697833171
x1 = 2904118189775120023459019968272518649734695395069048986022437844918703975644558115383392143444650105913452409637755020483723178514755099834451835881760669
x2 = 2496347446622649570739835604330702398623655492993517020989697292987597836476885607585376289637075420196735804815963859430002179996807900803924440985064670
x3 = 5092430706888567903864571522791342607274393841524837952939293151143112873052820889489487455424060318331863246280679543283523935851978590240976374837185862
x4 = 5841875905599158459362419364618142617028730211782981879796170746183188377680781214397263518308193221936236231314886272772334955629812227434225018741466206

x = [ x1, x2, x3, x4]
t = []

for i in range(1, len(x)):
    t.append(x[i] - x[i-1])

mt = 0
for i in range(1, len(t)-1):
    mt = GCD(t[i+1]*t[i-1] - t[i]*t[i], mt)
    print(mt)
a = gmpy2.invert(t[0],m) * t[1] % m
b = (x[1] - a*x[0]) % m
a_ = gmpy2.invert(a,m)

seed = a_ * (x[0] - b) % m
for _ in range(18):
    seed = a_ * (seed - b) % m
print(f"LCG 初始化参数: seed={seed}\n a={a}\n b={b}\n m={m}")
n=[3112694391042354926773258527503185381065155208766365770810259125227315858273584882915278974659442759713556138602562818381472824625797498323576227136840540, 786520206240723735172261009757420248240712167229385012959459782880298311452489264350397371063336640624230104453428663597776321434444090584610343945793660, 7754569747576675124444476463859698281135896797237129188325347781614403755633169372944514845375944974591833050594776051023970647718184479538589092026997450, 10978871322047154319303427738666909216134180533239441865527547245976955391170539397404213362987538079999656622797569425035497528648628186801889140680115470, 415184125088979230381868131662306705231430570032972141500815295250568658520820987452099753091555506318572984156087823561918067558858879113735437647918395, 9714366912431081171564906464961880471711707698812491599768023751085458677159777579545968149071317510381545022553352967040864616769551211477245295688346391, 8092371024146035837349997948385163397190707017788806800986026897219622319284668919277237868044873010504361887344482864009123696754405451607327057609111440, 10436585428619509784309464150307931296272516984470192973796220477752118208825366154709099054615564535911017032120309414411717936665468477272752593939807490, 447305603342948150664988784745387699519951434026852127837772145868706495519135216852266467924181573327190271412684871626668438866189143390133743425082693, 6258382789539676289638693392356433976508824529535654981585175361893403855873239591388514679492519869137377551632089436526817168965584123817538926883004415, 6578459280281502789276376530649184418554320975674197078167114333423000507810642180022772031856026530862489799383804073813561526139629854268000350585566612, 3105804271985778113444078016881015352567661906301742072344003729902592834090816086716179301421395002611330071836937959172008751915356371544312148285941397, 5127587678416216516561596462057578930989568244549184602544457582445902765146101086132777949114594616892034555102233884229669532953434325912113180385189591, 1681442924588151639116433276563473534451382602613595570895775581721843149401494979313072945423375889819333272799813140736767061166995345688865952524678847, 6078642869874003200723208932690378645034656959547344879427148548997772820000250634715135248051520273525771098588692142255436403818018608325143275974733955, 4012523361150861559330864221313828963018749453209042526129800867368717777138746796940156428780116853299962328653590275670160641449729061424004869739613567, 4087452535062195595067394274200281754153594561224879880591706612010600316823470426560921334571972319206745275769663537296296835581079110402423097667972149, 11987901353675361726480103030921089210449430771045316299988549316092607271793911250199421541491725415392936441323452384413917894329798638712720319592293030, 2904118189775120023459019968272518649734695395069048986022437844918703975644558115383392143444650105913452409637755020483723178514755099834451835881760669, 2496347446622649570739835604330702398623655492993517020989697292987597836476885607585376289637075420196735804815963859430002179996807900803924440985064670, 5092430706888567903864571522791342607274393841524837952939293151143112873052820889489487455424060318331863246280679543283523935851978590240976374837185862, 5841875905599158459362419364618142617028730211782981879796170746183188377680781214397263518308193221936236231314886272772334955629812227434225018741466206, 8822998220509619232900481169697664481537213687243135055737490918324236635625751932015349246530733060787880922400103357011039056263913931100456275760018751, 1829427301393099155994835313687991302426344894851330147851048073570161235032513979807480344356619367183014749159832405667673629599879026930073212395410824, 8874937378716753576850453573789326249003541019039439656124625436218713023501508466125664186477683313567607343263520908371451243118020424774779416613284431, 3094214719436429226961245919063208815398034554284969326313725322674015836263311873059825341599355295801961834907564360317827855287772012048456233770648414, 2272952363017630559556957955923359020608484345799712462629628170648722715295981120790102876295983654085449309744008793129064000312354978267334570450316580, 6496050086593645326490832279816459396921735500995471620086880796676279174314036559957741604751933054571983936020744588504368950464191967946656677942899021, 2908005781806019194373618893842561631858638383291599116857909669689194340479675737346427303495425892274736979677443740297777253232987190979789663078725548, 5388837765013859349244026248246407908254127661532056349880470355375929571123210403251766195449198851516630257699755053971912164119717459739252423955246030, 3932085435203368987040270370169028458481400198383481987063012025485880158374650852938797303847848555222501161881776438272815556194118123494398521291295697, 1596085666232061421423007114092508353792922600947831965835268732144143785280657330672864972239387627022937511560443766910692107622093754834918341508104599, 10892117681611280686941153150032271985229693373387407787226285542508269134168395045669092626668774409502094484729473636367607949115031549276342640669975082, 12381058972410501723509665604849175514380953105941348450275208477068514082229866560978025193499168665996771831648645890812123306116098698670457035525902659, 9545745033067721027306889070190247803420756540371596488987366683285356423973234015839573919673127328959418729409177485348542588655200727033820634115195595, 4479761395800283662690601296359321028679912967664335513079404387374415137823818474235937843015783541121766513461305964218999844148219102416295681398216273, 9156731911027542367340528717851854633542405024204364589600569440610994301305995711122403415955733016864883934476560189254464831525094631266907727317565841, 12666226165843230393234580593668809584406452210553760075587696529746311224658137054868869675868832265128577423471263099176912917347422711319558934937736129, 7737065667550567883921030156559155888807672386984437450593392652512287661221384706140560800013674012584773711581005691186997689622045412989344796050391287, 10722711925660632865003648114617468567460695864602168315375920133514224919874108904883202493206779150508025208748543209001260228655832044340651286693647050, 7221989584178899171245167344240261714028153334248896620632489515820094543095415471986280548321052175500724972199931711569861834778349006061026371650725530, 5886738574662494886015789010409089525104778409243680958758049475066582248064522621093649220502324554901044951352389897351932045257540701040679720673182995, 3233031164922457118197051143257856436060509168643015516594248999051329950677781355031891194479912736553900235538373437012785908680742480354059763051926316, 6920408828532601456551620626263287997391364853554222851307650268338227244737275020409310347012172074480549705970215944641795584739931068420792592364550052, 345138692120754413974989722062354894985124386853626820051983950290560303295350640053596083432413833430615738137403155513172015508429643499448532812238302, 6496124631023407996096728606763442237866253608920412620007859687219366730708253684245052162774841972751074153467713038103511069685477261845614949446512946, 4954508795303987697183186252875587490356341561311441407925804955497204676368654384148988141783982847353089058481160501471777024753759971112068258113214565, 3828140752986076468811884163754926568598858918798535569519010381565163308453577351104319634076150030767168383992404786769678070072803711746311572209192530, 1525344587067629160366462540930365317799240672047761683713335407426899660409450594374673147296233196946100880479779947899945565197770752720138099788100242, 5602028537128071394937385481766099952197676084096530706435200857779681493800600692877392655529445220731489748219807533708510871522082289298454440537081195, 8405125104396694306214164667837515476489019008711529371739198500339529156031577667955991513091455659686200628433501522614373035120915300556389897983235246, 9363664670977587308719921639117126893427493571952598074398598354833859096850631443468609493097644882813856223675425304811178510077132476076498042910645127, 9349867197915693633449346578490899128090370835059777452440405839315024154505729422754698383796886447011859369467724281722489773749407392509326759291555650, 3097954855336969231133966616412205217720272446131201205394739397914294852319995680869512637191028462644642196360432400206940604220726553888843484631971992, 7406758029368015050095014975336874387267990662428684874055990633074940508414476853156912578698644499480936056505695505471874708394209454863202578629044781, 5898320635400000335689178353860464283085294033102742946598413410403566655371101483965016006968842853067086240043017626407973320006397434327924399698861420, 3828259549886515897088733478568758658537872498350930339786355733127243099368094714942597822674100789401305391925244644463002021967786404115828714481532179, 10066554692829027637519103501291436097875302262643471195009455832708625591378453822850465340538716551878294551013391681787809106196783898118863498888850156, 3499720133059334106382868629152269068830644098994082476913546750309451292524899143926086345071167411724519536123368519961201709328076205428843169312885318, 1147510368324353143366569189557814239414538057284528926807572528742387641385961348284337024920835614354163427666397191709805222814485017032618600205989876, 1376443474120809546746657939759253350130433377066673914731313628744658444788621480850904944725428749861684141267366595703293257102033695543353727831255656, 1306141012932794251921296999513356011857879354957485278247781515633351554530888210035582022397642308827310053200134973752059059882857529726355628496875096, 413876320654674539071498590563731546775652768958703825687302348932338816891646970452489274333920514493304821523049953031604718378578195970800635452979649, 7136032318103206577710213656015300850977662493466951627466129080713148099950022004835515732817999372224984465182016765597112698961144220566693638971519180, 1756926746502930493055390730808057897946636149296690801994682335268478289364240082508380322318466774154683071200098564629218083632205594961758297148916941, 3316411454937759862626366549533032628711020533003169223587018450894240524473337491784683315945222404515083081588061970401834062233395245203672377474101840, 7599211346182071240062546116924978763380850815873927487248272261113823566573995151834356651681181867857513566992756113461907517519948807226796425859877955, 4827401360947748134984560117351749331549293418478129984842609599519150402230303738934321974655033540771922561714741710181107247544509276801554867550554777, 9961447244710994569376297896009391492177427465332112375195390069257789445371437839302033237974987420665106837111388126490588618960984274087531285094868463, 3970825380935714034877349217971517028903515186410921713051743479793055944068011846527177266662364107500948837234030225959118382828207676389015192534929256, 8608544722853283040859357355424248470567969517050350679760824632753430693341742456610190512333547560909838869247382450069074859055253804037930976168108964, 3997948190249595469689902562163983268236884055830515360341250116190801555461654583247875794079436239650479700066689264532083273326700382295037787195625271, 3017769504296172462769603649703609973556946564740463758564555635077678423150496052443226378694972314861078002173292765046041599543542556913918523347263353, 3018202344977285583885683841870491872320206187912942548780004839181579922416791687842887038054070620041342514501089785820834677670579439549543511926064647, 9891097413298322102982137409604486446161539669050452171012014240832941475729480282491230607708654307021437081745156282474575662423373832233207415281381073, 810743817397722331080383625060943517758354327434640227828749606831684964655697897139622679395918034416371573980787570599833348592060893531005764737629127, 1969958301963944803918256770227669804705344374646067381549018696813216352795715044244066646943740977361192247676332396646834038434975510833138637230427345, 772283527249875882597408338501459146497878473259395153877255706812399634121008456441522976339316844330687671179329753370897387217142932695296763732889342, 3493198662567460016868275788342486589147435611953915935411231579476989982638489118458485903871892142501116430468467002727878349586906097406405889235323788, 4521188033318754929745682253319078580979772923679656226706453809441157032758310389926223236904310972501023754771832793204339998846509477714808315607910281, 1459294332771505218116793124065248690329063109957541959485115472870135095063108761273775418742597190233931321103250699825789092987319750533970824729614370, 6081872280435119283055308076930153339025042098756094797625575179794067581927871061960272319874202717615426152212739549866438480879214105498282015894463289, 7762130387850161469171952821282759615477419337477617017933774362212895431284831425608213005612250003857841615618062878428976530194088816674767021581918361, 7088966648042419634447311723094936418341229460114395537643458905920051387153662615102678231749704070491616519620338946004408977647690235277763140459513851, 8530607388577471706676549252322039165843846873546376646134620680688465635242428455911769685950893069368467175196898490905630827271869358438258138367147920, 8175683960847863703233560555156381607096304894990424846512919663587601289791899748077484807672241130846328052701521081221552165331340951019312677944858747, 2488623773922039763673766132557696145161284575280912275615079393811226460826881195363265124937419976718725662680265519090252785095524620609995052703783900, 6288863230409343367237321449257176176239557761363343791530360335256224431868618032002438377834667134601271040364141807479673109178951459313279813775639777, 1473263923409842234507369539073445638835827020429470695919107120414932038000731541162435599563211189312718420865785265955929068440558364834918540634523353, 10122097127617668407198385940571219425968555754180743969424837212320822902467269904796129323894867285839753668577231263726601359268499019654139049664492061, 1334784462377268162219916937778259079061709480108638225731209555525977073101039827877859407920878225806740943290613416505735060002712675764508538108047998, 12943474412664177820782360094982469843501041500422827324429596710070670418547139028323568955260840820805331899161092350732997070023024881720076933509023643, 5285767084748000524025756084248068414482830127641006763000905479085771014780726785155236576771987096323025767003001338650450684709507257843571038471056162, 11001649396182899266919450751411831463050029968134347011876378247881245085871285736635385336564047956680944211929032745371792404308823898143896080599228135, 1301320300483174681160013837223931621343934678403403829386521051889935307860390561329187310217511171817846283842794896111380527530069209283005624028690286, 1186915169823582113649731511008826333372778559188698285519935265619430618324050874482684013915987326600510246581904647268399723862559309332791209147350358, 7951498363952334154675185909940847757383581919338786100530712059201526109293278830582032249111527249008525526574896069298049360688844794969204346487119319, 5833834084743172317761925197221701570183986273711410703784510000739316288591047658081863870594678124768673286740095552226723863847255410312004390417932230, 250924904422407061995835179415107794137513805961258172932861317085785803121995475899378133391840809508281610679076388256556411152107191872088591037125680, 7085080737844307190711404281467289397811408278819313361734199078382373564224746415235216310673951063158139882956733288219404303997318855194384556303070508, 792899170302377369245819488181982727852356501237495658820211983447692560703122438829983042374409125728040070525543893080924041158974511859677083096607042, 527158028815181308607570985361245658684704283756590449588667033857582910233360333000310180939827834980467750511349128724495152296557091872597733881952730, 3763863417935228217913891578022090207665435628108842338881001530218617625267294739809241731373814499577113686300212286948743727581910857164406047073435145, 958455575406045524652006754606401195502921703814444942723242685507533790960715001629170021188825054149374588782230350772396669475019050028532264494574237, 9809663619882688389709117706867480374978776635047144310439126194904691403735820159227260919973742961860862039967431466740149997606037421959899675267867402, 4928087822912964183306632018065153773912015339056263025033437531290833406852527367467717772039503136111382784824674765619106999131274189533695412345998781, 3306590088110759567187299302153921492468384287750726848496785861124840118140562928463000437634919111218431272400680022915536959360708451855996593223449881, 2515345284450486657989564309908638223504506708787471236561574408125887414773177664899850115276078830612044843742665254526234379016665896380411170870041898, 6134916597901963206086108654185719639522683238742250523950368120774398123587375425774449196409974448759099480799449712533937282087807450665513782605062516, 267008464052948389884730662677557220200174254262230501579203365622730336383874495035799286519129165799047086431118526490317359253783923412623429268099578, 3800295810128139174303610558671254854105124434132150757436144235620260340163872195459646695446468969827264408515318839301568024785647250539243955185201551, 2758490331762821125743858402061695095981818993449415737628690206586999472874851271575996243559646503027769536546139985948732741074951448605054447471168011, 4217864104379220244652908183473678097829823483575612233951544943703293030152224382038691961310245629042826444658756962561354248059403145303196082085209268, 2411546292849014551581200422109249129122050947218550703776810780058841000449832253829636107587459795899860908579554012266416092559036860375897058675166409, 192467681052352162362648778226726733093735914360336666620608894524451640254072987304183265625190436964732828104328784706266808876860847345878920907323799, 10212417168067454275584471588910621010044875852180765650348231827095954171511730230293551305771510545238294425677591538289639404143154924489749365048876082, 6291496406676715628304428700100747835536008647518931914594365410721760743785935426363197093622520575550738520057474256623894578595520825692491818636334669, 1696976360861070329626849480960267540656072393087503300209873513633034266528003865510158759809700233902230575591392391573852821509573062950235240813129994, 1992791476006726756711658531188332687379120992528518705617488065186657920940258074136462208677189526448735990314312679768851854906262932750351345930936464, 3434817150940057687962615407673182936576770534551677026510420824040773940701984366644277648090615900140073539389288521085696480983123237694035190924420756, 1327855956090181552782945714409707635753546680351411598218049923377836087099012280676631016119197258537564513914523176743684952405144923872921314136129035, 5655624154789660915581443648297353167129398768268548216939084854177411698912475597846603256287206167209756880556116572180333055932759436594462434353693400, 8830059371095862735354543958775333718886412721521896475178007834620722932782486718721540179680672790557809311631084845372799308539284214436640810453484170, 1577636678261904797628136271897055906695035001433916913766563447593237424148338744133061689583362391559327011278037905021569850425130860531043753400763154, 1209729863382992194970404071607689320320688269277129054249972346057995988562627526632203534824706401031451800965862577190219536998333754410251454193172633, 10994737712981198858904493523119510510407890704351172608352260610483503932115022636292742662488652484884065872585569714312792595965194541878114072128785076, 13312794948135247102302068858829637693388469161937738162205887768730544767479875477575282537997374804153016347963677479862069345296678731832716900899603869, 879671866755667260350450894660321566144270667616606636933510913412039991903800808345026765023248799436411333541403195209188109276098614860327117137466333, 5997701046258297701008758042981450104850958281608082374179429160139658833748115292822230978073016551491127587310846341263896220866877950242984465975300314, 4192012991959368360991053529958905352101679048106150398842439746093082099247853769361916275353786757483092523746395483254419836006982430015840596420354690, 68767193809701848990678228150938858317438882331616019798227278054229929116354514010496742914593903938654686226703764027981691726307067924749548639740514, 6424878254160617279031510897227083875408892211834672818183106791194425743856659680167277082328488376798715553566764040288391365020947404294241085942635290, 5763317249464667765660677954026422164094163991588225333425943132102988790548347316637489825630840144712298171981025912010655441215703984407721949790844665, 9435550610931315332910244565308657822031673972676538747748776968398830747049322827689121854214080946112570463640185481340896982590325205419757695986071062, 10854423772658513176079671341132085265897789527203502433443146288938098731162432093760781299761018039572586033382650624844107074319936079541582027150668547, 12476951609313059069935100486664524689307116697672515206640540269281371069630100802734228826553881969126349796880152061952354015124626549756257692927815280, 8045796521414377185855048953350733531835029059717165499998684525057576005480100656824730185029760232662916675149548562588330925933690413287605746764047837, 7525718525168133704091970516222857259732335150600005652272906993418956544265228434139051120334482938422989961682491729150475586713499313679353043034729340, 11912046156711704412939411921254931438505716185767663797722530582823134713864014317449272059238099311015018796287244119043500568755668077884967429950325307, 4110376054901462563412017964610800633712664567375745109340224846052194476233004966740187585207654361057339454338701161199087672786000039131447606734749596, 10536181172701505461141355483962316021670309715632294804091924062622834181954003809472637335749074818053519805212673316386352637871822409277633843138677100, 6561239288740833507622012494260145838556069026796406502850578760529949619677685073606417050067995286214075860389141224570430897217267888191050083989435618, 10755390470562648902207547773646277461044027331578910788260151451952594114771257491457728262192103389098572788952846896691668034250236775730674370420267582, 10116754295180959057177541778544392071102857895532245112951561295322574582916144106425865580948674586957980113764584475972905926764533180433076299516058008, 5859608878417010984159585842628477069743251659783200679637533418043397666877873263920551182367857303131476266606376419613220550151623797364003280753673346, 9610161406190042620740875536112128010400982062708691775804712654931587490639820436686157097516436685664421116711173966237809547051696258177713532759654622, 12952646859219149057230927632784421545288507757341307005625287549328732462625896748866127565993868137664264482594593443044220358257862250213102226764516290, 8743024327867380639354449145506317134407105263681845312476151158834148293426515624801487795913107735337606303607388242940871402388276005920082857880323995, 6528451843739479102149304425458509059040659785241941228418879086912730488517357726536788993512031451564270545373930206730980948931647991797715441531367741, 10462017518740882728109987348635133411529189768079438410766717066737589074298615526836492547944144729306982384205899274858973867537303267274981230305808532, 1029921233837757648214250672123683540325541346243252184272242917208678427506067856700714176359513176639295219124015583282618724736476654390655108055903101, 3813391349261399004318771186005512948966760302080394751195459215339735976452080345673275015650542987881482072724697347920803923279413761484112487853082830, 5567045996050241673395722528384148064949240335449353538914263526561311052170653310179306144459952167489810559452323829738704071952158894333072311035879031, 11425297405286583197291193457049007771696095735039713556631639136073340052097230007416451599300613472366227651608125018305022847691340936237133967669922708, 5133133934348577917601648370305907274443352706523623096373752926891789513077352342509229421888477870704293827297467947756322460298412074338824202790298662, 8132583894883560743002824283673059816431507792390355426553765264038429014617881701178853548832309971139375526867381359198874199379920890215643413694501114, 7552142578261419245883966416284664466068563874971828329265494939813613106787130369752313075539493006907320849655211358140332918600081468802258749834843538, 10823636389049155729021217698235275011474838951652434077924344160818782418898312855943115619327929826005003323014892881057453251153402725743243234607047481, 10680178872406574919448166931611181564572199628533089837843429528532479999287256411849181801583448430894803286171601591142410846251190917672344726710377690, 2168298508401712132947640264694148303021343901549723681847049388089284984960261031735310672636540039445007659961609332757733555056471192184304623785463060, 2340178702773145350053705740794686678526767806446745613453910417043858008824651357776795006402716690334747276104571962770647451951039149700422444698013803, 3676298624367829693533841137950983513080397676021901937554619358758723840281650362664181823578881504253223943310514005188069688898221486997715937242429797, 9132445874585857701581851483501762197628317164635776743478088760576246356597389927572170525395684109023421565467382333814897575731125181545766414622099088, 1236243137925014415166903810601870684462468132447802699390566421129254384151914584169607594049615635949605059072399537399196990015228436722954103224215653, 13192075450313439458696227018221283192704089241176023475321514991073667203620836604426092029969501285268881185351240634985221491469526250478508196558288498, 13340639364100809037776647351288754791685500736266676042688472470296642180440487353725930118463893112749814096941496617412376513086275610553120671630855204, 12822843338691780139685033864703978550175201484982849212488267516822394414700586371148840548146427825919367884837033694191706187378673985360389045663493646, 613106102654076279293510245332160984832690077838123347459270922197015039375289301009491620920230388814580074219177117250380323403794569894216049212572690, 741345937780857867091204599859352029451792145933730037837181240026649690120879085854889380733270227213298956191657614314852656479913545582102949822350846, 1521203700405106530197194619784591552753988412072513286448479570991121637695991136022481083784343736454948481506227221936397006695094004044673618612260312, 1754355644745564738949734138715924818354376481147066751091700288494806267133747040362706809811119196525834164870547295032589624983098331611544467054571960, 10558001053790364799640017455585652553441324388003654829669801584264580378288544204384753221615914991531668321760943152912316734446688653889285671939949283, 8952741946129854526912282277915463308468641280017071764259400267418376820661617976517595294079266170889791671184248228428255231332246048645399218317435238, 5708781767915765818163443178888330089981502372897875606734905301563903280544280090906008214416992941521745475840179246419033248441594273683211971541021513, 11207314260945436219908495655323292893171390697333283188618347144146103399541626933000695557155317908996729464557230693586167154225916228852820347109587442, 4768699522653814083595511380194045011712422474943867445270805763976679774502355033727862959062082708142553518870516687367912845280877553823018516820468426, 3573404320052684865673874549697641892027200012970524599604344629480614428866510201242482244849851484812706779763531318294257649114967750248177266575351904, 9842046015326295936713113278372276623162309027668703544974484877511676105923564214126300248193166116770085089143956697998095520184839701995830786470588119, 1064336683929673294424950894292146984741870122993750747944221503261933086121633737427851706261755403775672810611025441884538303946056267106936423845713730, 6119365214772078724433453740633652395125857443726005119583473831076384223906106649768079888760939037051562253507550245597366168645023889061250894710116872, 5602011006464577820650860273674214314948301394399362583056956812763168470596401011938904716955876179317142179854200420737178701879845622918970728218817949, 10688806197588176452780872184778027232553550269662452778559914264819143186851703377917866670279816566644466846812573511478521598670666245892196227297170402, 5749904848759330691912891772384327613924997567829966591570364086794022755761818695314980583632637028499235341576195664559034461478739838517698995139240520, 1473933381482644649246484684948491018110461317434958015735226919261712432035368580090492745146416337225430662664884870906265846689475144165741263419385905, 3552860753236534406946271949447053351616262867581225480251433378405395606162241270360794601150221505524887454619865625159396521192722639689825266164326816, 4025679965704249310939546887743143184778491366293564444733040608202385243934512959804528152567307183957923258841546784019979277638486471342137039310318604, 1428306100235018482450198029802616624310450179792798438669479546266596806004602176194588533054495773950160676878470790570132527471839589294782804506864441, 8072640850617110855241510299723015162827596185892374204250158932214085926781337179437786602123040219341501746957277147294211685494391786439998863901089893, 2290057280367999932259137216825281879413132565849987663338198789524712754992858321893466864733387202649315380456638047854477096168544359491803121243688000, 5583776997173032351635208701832518352809786960319795099887625543547183445391810022036790072533037112330349602788093182421751334721766510178242249083764627, 5555512621486935858457469521156983776299061091073590635447092107028704208540406733047475719028715045501507903325457398941934254799046940278325310033482933, 7665423408493304559035871431129989913357233723249175120897904121412582167441209612658706772501336565843970245726584617492252916378077133678386752447479662, 8831387806623653368662340193363376330252742297757679694064336031013050629164883790422491632189245291105141480142691855687788119534960055111937208761779764, 2348888614969242586632516586799444957926744624366807832492236485549208397119705715567513397392975902694704991295169187766291349081368111899560720396912163, 10451697705774524889255333562630749622276186482567115240625444048980008730091781659382447964280974139805714329640013256846296616477415783127806162072491149, 3250053095409795441799567001241905982447028127895768914842011332740981667697922880047939854625934995462431986184579852033575425135296743961724555021553181, 9499810476412190124599031127163816885315637762750874334393511360938998873472806644408465489819096250688914013976242877525460146303183679634674370610160694, 92257121750173787195460287712066480674189420505795777943741841246701964816851362584581887732119504356154538047167987960370209222391456428961345119032809, 12269893351335732220619942414611484122117650937343569742545802327578718253718985310842132315303704593709644293158237815585049455555135510973664199958693798, 4854713676085574526662356579768501638557898917664535692967710778955911366151402816643274844610774778935107487406502370514549614685656866640401239202834102, 9656855196981957286865007955477554547059961250711019730968709842838157159677727374063090954692895414472966936147114719942275698429255550218956155962518443, 10148197872461036653889170589960841138898378162938634118741365043648210887779860640879042773763373401039437782724679433103797938447652210218046301321938137, 12461232655674858104051817101902990616915757003991956969221908635021591516205957656336468897180110175709862262579877525493916685242872024155795348828400176, 11515492235427136169798424725612219236309642991625654371183731730027788023368799576473412684138684541479647895019245640398756194511932236210019079278656202, 9312723419754943857232652740523874103277584545494275166317053355215205988412434914584577068344668904923765987915402028853045934303862656336563244048246523, 3434383108470049029053666008815308531590134792871525168902104045958390857925829496103793826034582372819627900181087747849310099323713159750797436731923978, 2052825789517422745957370721388573723182830509538514420501723815481790762140713599082002354654158294047326674932865012220392363486715578383070467708932910, 10770872913090420263826876160012447606018440578288754515724315559071314423506980193977270893366351744377445642366389285439123580143916270246988741122493660, 3565988622227549084653994809440615920798581997796422558559355800295965356685917449272144672382620500366078282458866458096806308728686228192532033445531518, 7987937603217906772125351267418794200095217108807309149562138708773233299338480817569011892602088537590687786738273360905876877211262668458875082882458569, 4299751706784176820105715713539239270215624269772955083508652046435502139841633241153109045625048345605751183584593710474010228628095809207445826828301062, 10019327725978208236277427849923401464013536466834817004487325963890302290677170796473911285913485694471557407842663829711790012758636232851048197562076970, 5138403339358284697884990506322543562700235321736382747541248890065001571793729102717066426165866053641894094061304639478393033286059241545837832925687008, 10228090755344960970679747531229256367160327180359671541949607264521381518553697635523334685658730563057199104095247245691811898629769883344461751738921690, 6938402205879718649643358194974950463903056291457329419119162151731390866418293772450507112272848076046486599581272976892364724913119152308769085352795367, 11280255720158022430121620544392035006266764932889864093174004075437976799530373518170066458122923542435209793375705211355694698012831668504105946460564772, 10650080319228068163548466605116849530751339026717564400609682888875984174584984784963847899953214337418229474398753727586147950082377211001219418727734531, 10461022182955578447294079762112754763429164916076790787112090719603654252896897448344420250021620176006659592981968554934943569081480419128363237489108104, 11294589811045347664304912724217788273217094365629355933705003484228821123827955195688346268644297234401605720721740926188866212623659856349759808546053573, 10141937561124400301982173279180416680599842235284290692072537579079974651828622761789618621457566636724264817395463634439628042740828226329973006978891186, 8699118787845988175954950830533895540464426675170903476797484684827478978776067185352151829468201077173776538174395364948214699466188452645619083202335397, 12490958061653463671303817402993043179356302996030558945084439266441544994731844973009447951262224179413736407979270443372343363290613996828606691161987252, 1024823052748991275918423605425827037473451549824180278380702661915820289501105769305592458213604304944573172116472138059298554754383765054848368834515334, 3149474298239740425894423050918867645630001944600705788108027769951125277410290754170234970933196247423050719031598422461389202024499050176806060679677640, 3425483968307644002385892058719086212716261772924539515575616780270386411164460702988525468502203695427847573359486165370995863584865024607875453113258244, 9705357328007201094979830114725957907301023647515885569874620519288750162367785332310027452079098270484040335976686397008724129688151547673302532800076127, 12528067279527694536201251429187719480507077254234508172928714722834454912280936520459764100380973964883571564905066513102812286630954907087130626346683494, 4939295221340286977967875420508917414648818020752361919936291655865071126761352698631110381573442349498218777369829854206818104532768049611248376832646359, 2674716557876676991359847674281575368289805356457334186233684389337165131924171023207759236886479042433988774018170513891058846936762285475702948844499055, 10349676289323318216282440188630692479357100195610794079000469485228064289679720223872904306548414937443200055514794128504939320273714041015087548204878153, 3900480819251156802400683860178242140508599285632000256139953374592431655484257091900097449715624009719169957853282262679600053131204952434804975419266157, 2936159796121585099460866869138570695590259507075990700680474293606587115834002606755454671199622928559535999084787402214470880864183436401195544493052669, 1910402964444746284044322396240628093197632493543757175428655391794593305368776891166511349255068918199319491778066276301997616045939664490448839333489777, 1994054049614957137012968886604855559867627865708330094634548251426006158033188269746591310955375650972289227494847138366482888524799108481062111707291092, 664156672277686579033231849080080037649291816954378169291815494575299687760501487195938458172766680345439694282832959763390366172814696710864218723261259, 12044194267239521602316930974641858743309642634849533309620090028794964787997699723555198411201425083423798765746532735264847882307790354623613697781026231, 3942539316360593180663464837869649035347833269370669444954316124093202605566882860780981381878784090092764043248538409214215435668807650324046261030953106, 2022207880686960702068864642666908666405232483184555226114281753353758352867196196619541592446344511643385335987267677037992230191517430032349313406786081, 1402014237680608398997541757664483469798911191731757908773293414891741210993904795137778388105953527158027010766967713019151683784055836714091379088238996, 12881637058943520423956901175941737505225045806296925357592011092034362689563279912911015222707490108931028304114733886174696720737566341300608005833745897, 4446045521099199793223577547105513509868334848725869867850590717318036002007864766205849908526861560477907094114731908043120644690316329932058243626812356, 6843700571901946528606304715672203413849264849459277102145538041815013380627558590652117209975927071389138841622127095630503721403593938867412536469987491, 13256848318143610462565698482052498172924849571765498593609128597128856288744955029403580962574277927166646836266532151877185351103195822664044510033562329, 8007697821447303394905163825963623638810259844261676281034344373436426075060169272367362853555194864409938774346873718610793473975936622478650660613171538, 3586649574568142335142000007519269169683528720968659015296196828181939727116591794102325463820915540711767580644590211490688908496713342802724330043476999, 2148119040689733972973040760742956506738676028795873896489234121475047906650516542446622516446652580015262674044616995261448674463155184722665447227004333, 9821340975603221880229361526669536689872783036813557603647771598331800920383857008030217981692547058985852914477757546352817156483366517574263281418049287, 5813002327804361264470951734172772898635650829156628675370575721244579958255509366900200447859958423075692155868720900356225705808715378593075570213485367, 7797546330955985239260874007700903991194636476790757497230960507273760017191030055855779426266128617165810023444274355865827356873670975494986772973549125, 6423309376854507951386722651575201498832084523844636913943763204639292900317424599429387036474652852527155873400886510187492547526250061669125362070048744, 2723152586748229745903509454334751207914828385965393570411858405764696535921255866269049955401523836912464812051633276478078278079367329876200075486862158, 13015397720497890352045605342327942324564547581996425748914656936552529102322496213513910991605691739714270616469070784054074203319779518842464992920350770, 8263750714072311979325622454139907993837044439909377414638039002083085784664971877156416417538871908573087847796602637123926505104604610909364895752078257, 9267773779254525056564451118318682125792816185104222973339351298641137957155502345583271175585245232019586303509714408650076668626619185504236159542187892, 6836655782419927384926585500839864398000979295056246948533536997678460444451885936375070616683594003406321130780418789653166843306713089441814025696068247, 8159919519373712666364879313578240235174260133692384793283692113895762771865201015732235336575594273425244597034248180447729832995339556990068559995962558]
#seed = (a*seed + b)%m
#print(seed)
class LCG:
    def __init__(self, seed=None, a=None, b=None, m=None):
        self.m = m
        self.seed = seed
        self.a = a
        self.b = b

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return self.seed


flag1 = ""
lcg = LCG(seed, a, b, m)
for i in range(len(n)):
    z = lcg.next()
    if n[i] == z:
        flag1 += "0"
    else:
        flag1 += "1"
print(long_to_bytes(int(flag1, 2)))