CryptoCTF 2024 部分WriteUp

Bada

Points: 90

Solve: 51

Difficulty: Medium 🤔

题面

Bada
The Bada equation contains an undetermined function. By closely examining how this equation behaves, you may be able to discover the concealed flag.

nc 00.cr.yp.toc.tf 17113
Note: There is no file to download in this challenge!

尝试交互

> nc 00.cr.yp.toc.tf 17113
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Hey! It's time to solve the equation of a function f: N x N -> Z.    ┃
┃ Function f has given certain conditions. In each step, solve the     ┃
┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) =  ┃
┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ We know: f(1, 1) = -444045537086 and f(x, y) = 202500187503
┃ Please send x, y separated by comma:

概述

通过将 $f(x, y) - f(1, 1) = n$ 转换成一个因式分解的问题，然后用这种分解来求解 $x$ 和 $y$ 的值。可以有效利用 $n$ 的因子来找到可能的 $x$ 和 $y$

方法详解

设置:
$2n = (x - y)(x + y - 1)$
通过设置 $2n = ab$ ，其中 $a = x - y$ 和 $b = x + y - 1$ ，可以求解 $x$ 和 $y$ 。
求解 $x$ 和 $y$ :
$x = \frac{a + b + 1}{2}, \quad y = \frac{b - a + 1}{2}$
条件检查:
- $a + b + 1$ 应为偶数，以确保 $x$ 是整数。
- $b - a + 1$ 也应为偶数，以确保 $y$ 是整数。
- $x \geq 1$ 和 $y \geq 1$ 确保值在定义域内。

单次询问/求解

def find_xy(n):
    solutions = []
    # 遍历可能的因子 a, b，其中 2n = a * b
    for a in range(1, int(2*n**0.5) + 1):
        if (2*n) % a == 0:
            b = (2*n) // a
            # 检查是否满足 a + b + 1 和 b - a + 1 都是偶数
            if (a + b + 1) % 2 == 0 and (b - a + 1) % 2 == 0:
                x = (a + b + 1) // 2
                y = (b - a + 1) // 2
                if x >= 1 and y >= 1:
                    solutions.append((x, y))
    return solutions

# 设置 f(1, 1) 和目标 f(x, y)
f_1_1 = -793336362005
target_f_xy = 157252801734

# 计算 n
n = target_f_xy - f_1_1

# 查找符合条件的 x, y 对
result = find_xy(n)
if result:
    print(f"Found solutions: {result}")
else:
    print("No solution found.")

提交后发现还有下一个 level, 于是利用 Pwntools 写交互脚本

Exploit

from pwn import *
from z3 import *

# 连接到挑战服务器
context.log_level = "DEBUG"
host, port = "01.cr.yp.toc.tf", 17113
conn = remote(host, port)

while True:

    # 读取数据直到 'f(1, 1) ='
    response = conn.recvuntil(b'f(1, 1) = ').decode()
    print(response)

    # 接着读取f(1, 1)的值直到' and f(x, y) = '
    response += conn.recvuntil(b' and f(x, y) = ').decode()
    # 从响应中提取f(1, 1)的值
    initial_value = int(response.split('f(1, 1) = ')[1].split(' ')[0])
    print(f"[+] f(1, 1) = {initial_value}")


    # 继续接收数据获取f(x, y)的值
    remaining_data = conn.recvline().strip().decode()
    target_value = int(remaining_data)
    print(f"[+] f(x, y) = {target_value}")

    def find_xy(n):
        solutions = []
        # 遍历可能的因子 a, b，其中 2n = a * b
        for a in range(1, int(2*n**0.5) + 1):
            if (2*n) % a == 0:
                b = (2*n) // a
                # 检查是否满足 a + b + 1 和 b - a + 1 都是偶数
                if (a + b + 1) % 2 == 0 and (b - a + 1) % 2 == 0:
                    x = (a + b + 1) // 2
                    y = (b - a + 1) // 2
                    if x >= 1 and y >= 1:
                        solutions.append((x, y))
                        break
        return solutions

    # 设置 f(1, 1) 和目标 f(x, y)
    # f_1_1 = -793336362005
    # target_f_xy = 157252801734
    f_1_1 = initial_value
    target_f_xy = target_value

    # 计算 n
    n = target_f_xy - f_1_1

    # 查找符合条件的 x, y 对
    result = find_xy(n)
    if result:
        print(f"[Y] Found solutions: {result}")
    else:
        print("[N] No solution found.")

    for x, y in result:
        conn.sendline(f"{x},{y}")
        break
    print(f"[+] Sent: {x},{y}")

# CCTF{BADA_iZ_4_K0r3An_5!ngeR!!}
"""
[DEBUG] Received 0x63 bytes:
    00000000  e2 94 83 20  43 6f 6e 67  72 61 74 75  6c 61 74 69  │··· │Cong│ratu│lati│
    00000010  6f 6e 21 20  59 6f 75 20  67 6f 74 20  74 68 65 20  │on! │You │got │the │
    00000020  66 6c 61 67  21 0a e2 94  83 20 66 6c  61 67 20 3d  │flag│!···│· fl│ag =│
    00000030  20 62 27 43  43 54 46 7b  42 41 44 41  5f 69 5a 5f  │ b'C│CTF{│BADA│_iZ_│
    00000040  34 5f 4b 30  72 33 41 6e  5f 35 21 6e  67 65 52 21  │4_K0│r3An│_5!n│geR!│
    00000050  21 7d 27 0a  e2 94 83 20  45 78 69 74  69 6e 67 2e  │!}'·│··· │Exit│ing.│
    00000060  2e 2e 0a                                            │..·│
    00000063
"""

Melek

Points: 73

Solved: 66

Difficulty: Medium 🤔

First 3 solves

    hellman

        solved in 0d 00h 25m 23s

    The Flat Network Society

        solved in 0d 00h 27m 5s

    cyberCryer

        solved in 0d 00h 43m 33s

题面

Melek

Melek is a secret sharing scheme that may be relatively straightforward to break - what are your thoughts on the best way to approach it?

附件

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def encrypt(msg, nbit):
	m, p = bytes_to_long(msg), getPrime(nbit)
	assert m < p
	e, t = randint(1, p - 1), randint(1, nbit - 1)  # e < p, t < nbit
	# C = [randint(0, p - 1) for _ in range(t - 1)] + [pow(m, e, p)]
 
	# 创建一个空的系数列表
	C = []

	# 生成 t-1 个随机系数，并添加到系数列表 C 中
	for _ in range(t - 1):
		random_coefficient = randint(0, p - 1)
		C.append(random_coefficient)

	# 计算消息 m 的 e 次方，然后对 p 取模，并将结果作为最后一个系数添加到列表 C 中
	C.append(pow(m, e, p))
 
	R.<x> = GF(p)[]
	f = R(0)
 
	for i in range(t): 
		f += x ** (t - i - 1) * C[i]
  
	P = [list(range(nbit))]  # P = [[0, 1, 2, ..., nbit-1]]
	shuffle(P)  # 打乱 P
	P = P[:t]  # 取前 t 个
	# PT = [(a, f(a)) for a in [randint(1, p - 1) for _ in range(t)]]
	# 生成 t 个随机点，每个点的值在 1 到 p-1 之间
	# random_points = [randint(1, p - 1) for _ in range(t)]
	random_points = []
	for _ in range(t):
		random_points.append(randint(1, p - 1))

	# 对每个点 a，计算多项式 f 在点 a 的值 f(a)
	PT = []
	for a in random_points:
		value_at_a = f(a)  # 计算多项式在点 a 的值
		PT.append((a, value_at_a))  # 将点和对应的多项式值存储为一个元组，并添加到列表 PT 中
	return e, p, PT

nbit = 512
enc = encrypt(flag, nbit)
print(f'enc = {enc}')
# Data
# enc = (3316473234742974510609176519968107496789324827839883341690084725836178910956015867823194881383215644380418162164089588828798132617649547462723383625707014, 9486915681801496583557174944405629563403346572353787092582704754226121096049954529719556720667960706741084895049852989479773192757968901195529919070579679, [(1424746411702933465168761664402234333249213873879108596709542975421813254055935811165907245232554646109891451758200365650254192269762724831339458440052085, 2859706124672477676289621863558834324498729266108164300463513486510517806463516453222500394243197914522800839569270020085178208656917805561035182618711689), (8277117929992293788166344099185043838738150554230468802946498146083774315393223889766241061619350620533578524728776409338690429055707605032263680829819426, 3727169623840785277647562776452091573986409417114249516246295801959524412458666603828022357635060314510186758437038614637202185824331673337416787823358397), (6005139047205800682033566637113276189278888930018596404539928999588887958042995419673049060782180812140592665582340048099391037097335444646676243523511682, 3278107235780044986383409749482372479982400996226908646743169137133958743948978921046887111172219389792068447102521386182216355201434638140997214571039777), (905853756170083411408013406114819035022521186919364939398665890472860824856114810495020667681235599973539603658513065097459015954831952292601938395143872, 4389646019729685988747362898034635353920371269581626480935211064324579010154060155754291562698660270957985129343885741427699414766813813979259448769969915), (6158065793648572189141996891807305601157028550500203562079315928105643379519817471626258238669595362615531887439472713154268348655665814626132079446144482, 2018394243153909307148270704100848487121945766232942853906717755287277977297222937387940655623889100482886344208902197349067223875785269444024019805905528), (1729477768841421391173683791030640946402906560917673708294056313043140024879149223795753455235577074713609254949219492717749182298826516936798293867360611, 364627659287830736674917151648247016868647883021180036385788885940589686807168773474582426844828151994404713874644958591154422836418021599882636285357316), (6961681989324650030735751247277291431846836978918396940079533642788855808743931566583798013911883889473204966324320273706094191846059590982471122076128160, 3086072099348129662747339019541139233606810248687628141844009841358947579354479577173341090013224155005131255766922977924280563090991025356514852705533074), (3326157205285805909785007726352428114376382546591459449789629146092304687520001709642410898981506916552826061998124344170361044245315500652487616499880442, 3680514542252209701526337414469773613761619237301996404770464995601702317514774838038586256075756484171693667995572300503550189060340128508067904731600106), (8471906674530914252672164490412412261952453965854001241613310806586751524020760643728721248681636572448845034733253183516307646856292816662827285085073323, 5213979787974062409837881611444284394848405954294420128043494398411594635455443095434292374058238404058346907482780695736845630491202340108623714747492790), (4502848627793158373515724053625183418076136787974291917959024508658902453653345932040061668973613424780842673236336997182420453961027867832952782759905923, 426043231346053622980723041090205787021897351313274373535327918465833745190685220207494624063016316176175681106325553180170426114674617534924429936858783), (2513230856611079865375362655363151630816281321849307715966246192225828697108301993296796551667222864242342847067503903593995977512896561206893903849859370, 2868927821218929934999983374493054809170486714832152258142469450307771547865882006447428373988827122419212633010365780557670696462508666430039840087208418), (7471846101664909518039043949060125478264291302030589163063664831705266512608271001215466778398195840132517286074935919620987294396832238645190458203761986, 4738711020129070520795361004525407366168866531533690299353829235044944209681562451791301315584370530775089770338534858602694136460127301764810461486599762), (3966966723120629459465566244227128838625688024732115170445231987381900975596287155559850608740900818120394246691445312924071202479298330418006971639272770, 7571364609958489355880724926035968131876758231695153371183467916726005485392533969467271478716379302832971235952977428539665609495729712221561153003197675), (5510219784916748946022549514295370088299326599237396580313868514005015291957396100794775226032837612375723409396076268094106738679164508614288657009514398, 7691828282085934449093052027580306136033894069159617087204093156306969902708864600944335636927415153261053980099020168372140310466888264767252622858498441), (5169383741561810671864241918462494416690615922834807147067816551834358414385170738961206739820038923405283993405708692798563780727352763654827619035368738, 3412764156231028612089589256700537415043949844621466329107419423826149552919692169304710497782401247583340112983810440612036357528964450778664031208507202), (736493375022815678222989008203212872772780986216707125300951066869271736363680341917890305580755460854569849691182975947748750576551913270151598842116406, 4228473775211940986324094929114893603154989854600838316589428509812833727515639794056147973853029417533706449027607990353480374512578152795768583091691334), (4533377434545318860312246394862695755705532734138028927033370746485046105940429432286812164112061600976519326183009113327201452875105876282276672036157470, 8306068647255755517598325565766862203099488289266258523225114301104190753038737114896001423044588572766824315139435395550835223756261688698374482924285588), (8293015440470589200603239812204147247492679760001136239237305427686057510594321072049723931049790282856180448509838513821350529033704736185849513484874424, 7920930090116903351384758918269173305136160517708524765553896095099982433131328081859599807222257690341274598788265741517196475328723507210348158307288962), (2582748810785502105375254633783066947539339487078927735724820916544473810380327929697981493267385335921347717638867232253595738223040342403171832716312333, 6325756611499194378407910533147768103571075518854437912517697156758049352416527997922820937268219147660362366558305335275057336907334468597499674102016534), (9042221312733113066480123374457412348276158326476677990440663195384486143503908317413531580431004533827149400576730434812917558764232285628316034610458014, 1825675582818026212357181251144743601749930034366506497265596017399508684318264149275390291786062619137769673544164627707022242501808627099009052960771873), (2358246780982734231204994932133842411568627388812687161414029624826553450707043534880847018703742449412878581050420242826703801163024506944068270678084800, 63579588722577124969656775691792302591606910013737420936914464045358836226367326053317335489967022802968113278351018895263080170339066013753143912133009), (3038123048505560543850138482441166655500217137376406720786449247114340443634626850466104505842918683450530629482512013682218427481106415863769066048157478, 8273039594295194301686804613960725936503476886520253294228893355877179678131661528597969841031559177961041706418682582322103557206830586621873501138877137), (7163958895811145540971620111382677000219496449313442920968589459575899904604098388996253497269362420826153068406910403045829147595658309179400343759915624, 2561435706396559131073442806494855070382610740603093578910003596754247037776375148766989314787276544661288455444341855563456783638406070514679779746202240), (7548057921200250343280074362225645134776238328197842344294688341465963963947246819552870446181313114588089241449429520058948932865634724668839836484579743, 5946983388513615210512588626771865400413351748761071203519864906261590288102077590071275890466491402544668714450410254179604152576946238150378858498627794), (7909056611071497941695795267611324103585528429302474910785996334669257762029950644222171556665091853657926866877606491136048767592810147341653130082079251, 6887843650860595501605901422089116838787801911745695010525702973825651424598983382208128728491399397966931723778749207127569595494700481866751026826817869), (2532741114553066384985008100317438004085579230504052920839562383579882405138977815527883136126344110128237721586073922049679289426962182298675547721561979, 8453297680965880153023082348218561503964470094716293383701327010151986420573850752903135997652479394483920125016218131221441299115940970436837106416267246), (7089953932281718569627874096368565479596132531483670747771091362742470548513728889972457259319404602601303413321042152208286655893467992194095168743570928, 3896212361222789814453703193362545965370098318632654604401185026815758198475406614279653900407677165999818616055649632532122858964344678112371764276402520), (419894451555192009927203568788891451116542451888862090814044826670032406883621759992592459615936100955375677713658438121004253880477012945130537224137359, 9378086250763030251327639231960274706166182152364536077778485997213964254907553231974042598488129201407460340237318706374516610305922342697077088839032626), (5498653695623467108832969782105879729004971927222251793852505274657621032320158827794428079610575271700339582765484440677345773413995846357264231856480727, 2454688835760770637177369385850367632434848895929348357716679582033028808576417532459419927521915912634948213742851477660076368397310387012294965507062868), (6192727743769904974035140598714812287767746789540669615684168558592164612503362869024824483174869237801927982950390543611131415329687336979872063410672987, 2429182645625427455309536199449892526572933245894555543000436664997323953673131460598256031926916214120562313439748400945463113391235522988583917491290241), (3813689755081426754193791793488685152690583283270738823806825310318011720332482766990080773160305770595176182214285535359056980987902619529888902617402920, 3904849203271127535874949136780235268306334151401049296670010624905135567338556486064719358127964022218798574336331838940156385916778961536464693189355000), (9011556772108256820339678265755409593938992253129010999469839934762013365728967307571661604992576360251710947608040410548972697310861632971043662428086449, 5398957827055401348330042082610778776998794997111664497653839737155411560101518176618890586925422040692552695324749428337692564444998836995411331630811035), (4070928971295874189876547763622435227074625945669448404457644931181261324367580020502962260804534910855966662840532176596690918982387489262308315557857429, 8984575262740993543352173418494298266455308487258143377003602329838000586923267256729034261036340308553651467034170137175037095703221276322166500398332070), (1177846374338320592559036075650221510847561215501984852347879528231869596515755666390473322598773120561285854537700745480609214999574754658016038410810063, 6016269573373404151928755181925697235798939289808544873986351058701506432286458481933189638884362564274134707290550401159154055082704213770049427155531235), (7810873611260352690866898301237191040710885694462903345569911166138958389340071797306282123290486655844135486605576998740475099684466245876934502150088989, 3293270234503478572491875991006155999175694417892150513290206577038234157555761768639583868063634535025444528819446866399523203517166506056947070243138316), (7578070509595319716581694607337294009986577778916957894233186385435534654035558988586559994275025553798672067117081921271548294909784052778214697062836119, 1698930702725225616741416778478361250925428755202844381471803401787341237483381246318162222264680437653300703544519806187560606017506805847883302690004319), (7776638268449680241436576038740206069099502226174958667446480649642955583588777704829951461707479245182087712219995025530342028497833488918663900030473643, 2438489166975259250425997826852704624243268910433018754178820347785414475779801688508508073520861119556001963783862687266281390779797343650327815321496185), (5824703967633042864626985028923708226310871167855819840779294601188469189343052794415295383868197522038480465320180242019047926546448506793687961405136528, 3268799412515719036666161689345446752314784741866094619719870812074899439448849542786005790416148065595547299846645935832264064674193441756484880636691210), (7174478799846944926236370020946735693011167197848029036460174295118583284770605774523571813419466757469198839674781996811383922984390858634665055895314195, 1465765340799754242167631466719927780805836027864253201555346070209471586165599759807606224472207897806323639526853885381870210147954825897501944843691815), (5855821124879635739946452384431434589315822302377219911965299033718689488174987593933699732814064455122286408323385325152437770627974449761019507101207682, 9166485310751859308960511471614343825283273052492731048591997079310773124795976744601588608885382359839523206795702288102346623954592809813666386858658060), (1690624995822226054146116030288113090177326116502307285455290644258966031301783288362374698019794098177389713469664994565600944339438201167389067033952390, 5545002582325257638621109039302443450713167196314084929502292694894801546563690503091057577089549083150151492156715504599018314637078148189111408539419921), (3658752628375010967944401731767530275355379205345648069725118482367763751267413422785306205322473299869990241692321200177398140038488164792391857011723923, 6180997651663993455344694664683477197387942512237914850897745388007660662792939996671390832154761269767068735384350157956840016746075174309666559324471759), (3030896365872421132014076476726038958049220151519127129229634981162767373231787453362498177541256973096212325153627886534852725897473939263204858710512168, 7005651744249244479929311352608171282809720415762292724561829578096259328372051831323512844298230867484805597346538935893512345607291514637812711876048583), (1497485210943700884215736001434375403555920049552144900577171332914245080922244377574946107413052306250203702951587959804152275607975663003187682125991520, 3051183685754368632266928483280274264302863068240010914009621093916568208375174866264095769989316916162262577668032800810814892605462967499019613452516607), (2131254028956549332664056822684882059771289142480311579977112013139107331132025122581069423190363759291800295705238090804308112081232448184545717254811962, 2115227337665658667251651485683850924807473110231644580354697799150884479894634301059452712364404918265110224099638632116699042837866075065970850963642788), (4644550982460749143551554695693358219443013819536503612785482315078964939332792736254791359141928619979056048615955587222998187938264253231079223936321909, 809763836150053685056677658615689230772611139338838049748066697667660906987502013404016834388175234083058885269936822397469208828620191115380503053029583), (6546995856763735862776423211297922592961424600699762762591072643768080896686731443340412100754304348395743749001313508269371880054260215223770769885684758, 6249741434832318750567888323078224657384927067080698423706440737327807390323998171993880665207588281650006984666522506063253914318278847356181116838831966), (9107741233168090233174535370322059959802641904576577977270149616483391743815271128792203995899642259313749333826364592300447330050460985140997807226027243, 92866937852962990866917261712330640278632413955797136653367789008630133439947040935068988114474449306161049493420086784871265986370605856742174044806504), (5283566008604564013028558847877639059719553637269865455166353640808481705149340611825835932261328414632187065879576069455650304310474971321711085002793236, 6453507393659937138241213708484250644688963291963892677431601261079462082385919456927449499013974497820362111610201671727731809396652607741472285121559060), (662071674962550808428940397194357245531256664181169176935718215414889977936564815140775903964791483853750964341674718689645386278643511767831015586961447, 7879636087870209764258976090389321473527817285201813820523572314379893351896753046331179583191120528308982364914153726480502128793997186529080879084822021), (7244925203255631851685137184226424754864002385759460183351259340831665646566380311467485246005925445642053111063089185360657965094376929082036586326490140, 1112331096575009238026609536458444442869758542318698830679443301073080927791174554837039983203614697385376804698825818304153483643423364482072432945971326), (6109986939622152175404779341657125031101103437078499520564638677016871393122770541640535872458709315409166490153870781173683793537878884967171976677091160, 9221002354371051580966368122510673788801162809154104513840450006565894597894878397610008130543794893270904703844432139590878612159968176401008175860909295), (1344200304047673552513186021805873397055603392016529331080832361496486700239785121579003872699318983653285123461755305158472031605896002889714825004429838, 2304714278319410183769473405645936197780245338990036849139883302421134720412929975872050221588579237103506034953770260255670581286595285281709350305638505), (7490349711814872667587322339316691172237011888645533210482416081153632077881654345728960708312380727984529397702081669684980869353651778245142159692495748, 7082962199931230311417681174129074700563158218306720831575690980794757596195969497506337336696447420708911230053393361814666817461532192835544822183083610), (3008504780282734162225245536402562011207035205530392926022579973299322504929727286407453434255873129901819659242700847545153089450817030060303892056861412, 9397186267893319177396861880000776342078214922844694269438041860849002699816712921851420951874034553740727920629693764110896319508288516868655068723005949), (7504130012453404034718604316531911472938590197024580747209086935348700776405011588441763097246919175785799184722656489210153423598094546462573071028471904, 1857430167341997076006069061792640556874883462969181713826341001163299861758730809809585722948224715466190088901798117393549197481897394947694384128081148), (2020755999316482173157198060537793704258819280448723712605207152418633927232966501945137121392007853689426878942631185545824741072136071025958079749597687, 7209320697822292646421201475103541962576118871133145876061741042334691256648450395835688675758449069026216647608660658716022769189738420556831812118385025), (7317057693730393923391248743152154193678008668784902682059953055968507585204276110848717093019970455411979135290237169674002784904103208649616648882538616, 3486434081742419982532363681443404497985015662815693383981527439541833031631019437161477436027336356444070823415433488327884607504191933833330179393606980), (2782268601938760465087570785726691113405462977745648990749735002364096108475533862377120425718144661316960114689577244558787832334662673899484319233913190, 5756598587610808229372759434240234451134876531398735641765413367621560260210952961843304482799399181128141065719087173199911405534502179517128358059788352), (3317920490173710831776303131172466747219060583549114781336993765630529062551401777905450288798600018054345325146457688781780889409338060079032604734210053, 7659573417583007448101755428765188307582249255857011652404000344200051387370328144344190182663123636734441174002352427014754170562986203536544609162405362), (1060692042415818192735596530684428619702171766186602452914970780501897362139489282543179073841673937731802375774859379222416764874152164887306245357772871, 5761756771186651863189537474040285236018782898372033194827500544480007010132270689326323901909330980210520526791163470331658380081590040006042817534534194), (2889953438705631500852498351242691826715758984914559096265910280675075889172965272379358895125918719240083712491627221287573615050220105929435069093640699, 5122907303787881510534519412752700186241365273820263776215773641825065810277571192276365294372629756620572441559988193353104170795370474088332270553141084), (7976728638199003179378525781826660444883272031943332463741243824911156356482310051743410761517381218390438825701272211485621218371918140019979795660342198, 8483571140530871249938665319163853606781992547904074337269377681542968091893559876741142754311831378220187427358484412480266934894813971165103135932895359), (4602352811986389850007427858306048820046263219456388183459412948117261519273787722061358789899051470326777633678642010414265620170353927296195327380310331, 585966913917179026570367782331167261109684405783746881934668163661831730739236782079137590888623990592272189109657490300571480010568567074572843823901383), (6015983579387075078271814036687732769226132952911441027587576926493187130417111720190518964321786180260688337966109166825215044716250257703244179987880848, 1716814993559468870322140592576195422868593444449130528160477003826621742968000024270539824871378374950303624177826197857022919754398035269998144924563886), (5657536228014358241187129930589417304361528625345713939345660816130699497208039022845409396894780791847470023518886930399417591813595355827159730815545590, 4826464762059687185455870096595500731238036057277724439529138054662250526168295895391437549984357183577796916788160893911745582614167421683104791161065333), (6977129991161166240684415999678868762865237784218342242651802872767087109198308110762881526749286994393633760678742347262057823616919232333059551130631188, 1658171525521914840946883157109915873267270005768049318803666272155367506716642407590847214819432277793412827106351010306324371929752384239976791062901080), (7755769461820363589312508355668101742519876833621427862756061131374431909717358628889194505056659852248578290211559758660887956176639056093586821164250505, 5970681585093100392184546882612471042137173343095652237716615350475052415360867209654766479417809499888654688034182025821182914360020097552148300745099500), (3828696285504574543458502943258527861168612927186886598422675237839425922104559553942721029721740127321518808502324686003557705850912575174565558520232603, 8554323380591945497419771315413259868407314347514442323813658222137512367774765862670803860591835881090128363254324868884678625859609002172327901489053586), (4840904941289908224748802546001971115599491341046177479785782757571610230797093914078421394084276181137936018613985376692610196081456682230823436797731066, 4717543557608533239544507363685128721570857311066396457206308562164757435486795243517981353912648376986277160088736041525171813309956298150732150374048368), (5262843732570233501369276727904938029925326737200588119825919133050432695362975733113648036296033460034984845468177606427182462051945529952272462472703132, 6220648320393812909515726764560553234290195945974054295426196107097606454696029550926019915340643816643034718891817117885080996411451808295041966829937399), (9135951822988755894259888365851188101479688834108732772273889313185031252394088624474527798248293948412480886911121848782908642768836507158925999711950086, 7499586275860403900928906645445899396092839502007583646284814254543536734285024233778651020781548236849895444611204968778289556004986498774139327559804081), (8841601573582707104779796669743701546367926539244569274060550194658028946386553107965291555619321289713737366245403008919061893175480662847647360507950785, 4390188469702299488199639294072496101482312345308905106017318149859210128227955505937789482079335683480125439316170720868524665094779908827165585328775005), (3226816243571766371187323959996189127762950527716175701002273481927631998569993382289091394686099589938796324854249048512941721920075592672255111596085343, 947181071964655747849348053342994510001037406488552895156424106650216729032631401136683160781606017952699314955682059937387207908687475618356513961892998), (1805225174621962963595743691305208700293759749259115719645687187809622133979252791996294454629262439008291873768236771716420113867887059708586283324971096, 4881277902690858565556261401573225319180092034016387734978513967054377558381865735363651081521602154941130347252947876727574683221236965659740035089080799), (552949753767066259441811671695783871880720262351944149895273740645554531196266406362834346249931482184357575589445952545350674393999822294303867572937395, 1276515199594933096332789961046066689371525721443649351865587029454667175018446945283235902998840750592225343176053884967087719817782477346685732551221084), (3694890738583771365828950052008992732649390282089713780074370301485258772336310378965807397713117177895182385284453749542891143382708865527760335821824720, 3234009781938046645176169350162938679649807324553386821051870812372695120783543165409492735215886871655124154588469819782842310245991397485687901588407789), (1863527731998945520837977207684203092145312508172786254391710210066160865686226950486176686284158153422422139270506984210941920543749974569313113961265576, 1275888113434395959209235942675918942518186603836603256565454502288963873582913654911430945973601055675861492330698803334548772127451913412478387787327739), (3148857402127989251456153439825583861330535532414663454981017090283017711967885151952636210161706041891230833791930478168372712142135535100131032607602782, 4889224724832241999921703594114311592742005602550303236070848861037090666958143774676253784264040118846872091421548067348717835410404234616637471930516771), (1382197162529484513958734392479710534587805318061588935970257276985592673950347472609450048524481140237575618578075802658671946330634581507189074557057239, 3463507337282595695318989670437836501089014573914638406295139080666679898104835025069154613084082764225889277738563332116382398087003552875083575189220255), (1122785694590261383229689283434776310681147824357542423549742822575651052359383824570755089000640354394464815274748530844487854410127350853628323652620966, 9362312734680677342502791663651319194942774135743638580401532720185790456959673285493521018496690276015798572491858726548486525317641520637090806791907253), (6723369463198060216057013446746482924984632109287194517348430797049950249969662320698845042036086233952955260540674800384163738615820219187707403677529364, 4514936823881846532149747458562036201990858600236070546385960376478985849621509997326728686356147728772150986310756556251626411375281409914060000026383147), (6205475238673305097627020943138066689348352329080183009585612376819992917518009049299532516822117712592312430147550454817797475145664428891105150978218036, 1099147419896828794494178422693356448893901355183500864180852094621286079668522218931826111713578347225228466630456468852618086441245504431047753956944607), (7316667142106795644035238656781495379220395230415763831410183893124707035934789186683606229267195763855701261996760352125769681408907892421374168114303751, 5757536539585970153752211687042782824914954169649915010621022197283560316592077327462849572576452365611977618850621677066753630414764664607559468961287505), (2405017224749946600544442170452996511105891261032479671728289459601704354716083519793231717555050030285192748417955514685977728596333236395182068856782929, 6526906053407281967443823249654567503551689307748778362095721900566155196819306749826457160135273846389346720271053611184005200121399050179658777872594037), (8215329439006125771132140901325167182246102998766409981719557466515558048019319996795392291044769590532347865902011149728809361939846538074297335780812040, 3449355402950927856540561413620578590608178034014796860435398784014589310817395704505469560683762856269357757145740022720028067007117799575330691114450944), (5299313999350746217753118303762760383890654599660483448408046491696256084479040904664268906324668666912061067982180429805737568564849055857437543220440126, 9288248247815301490283013658751091100588417731677674819762803753320827635827989399230298181893260620330508990871774489210318885115127520131361644451625067), (8324534216467742625003230758416830197450951768776256843787314987615774976744361597822378610019125522664160569141424711113929038448822103429696975846144649, 3947307488605942934015361579399590665493238405611386411343075745421551800289744907020925579564118359978804876066345141679256233934132044204486909461184000), (713112568702674491685413152930996035099954939234602955759899111807815318536270776499014758460563181678015688229862789953184951831506557670395335177672242, 1192968861211653002744778616093206238617444888288480296370192082962450926962146796298164868176360134263824676900071964531880213983433536725030073106766632), (9057024087755748711059416150143910692143081665697520271111617775749172921473811427562706260919309676850206749502116541712001653978533700716720668890743429, 1561403478977518684698409107272133158108611585256088310421964069379276834308215287393564451028610856535857580515201538228420825943382511327573971095479810), (9027390073046126666493588184199100575566801985994317517832037159311457757184287673480957293892078744067154865075691205944395574388328113414144920163261500, 5073492276835231676907956213118705948799734343192185411048166061728571435601925195335861721377989678061397069950148657144658616259474434551444591435715625), (6058986759784233572710074106064361619182910846547588868947064022366463933954593270341464479732657505962880627149462602097977611094840471715603776540186556, 2550014903984175808168610958144097089021721341967672112569676093444782329359792087832747766250130180200590871605055114136485670762969747795978625615419965), (2602655883575160530149880548749950145717389423558686908894645214362132127738576392265932477096100594073759878418664447530186479198648845296239996258291138, 7019925155924665931675572952325893798433499726286314361083986422682936017740994869145135142773196606596204147254993656062781304389753903858418820927245769), (1801249628652737599816823482263684390642551644129626167552472753456277520702222262554154991408071656030423752921520826703733195297336763531023480282243805, 6927795090242220874900535753254885462411198301485964313811168799635870633569888861190167479983374558979455422353805969275620238161576839162897368772448163), (6323844561576438001991183114460530628458625708153819806916595891385062470398421883704915622529761014812009417969689870710303641123562756539140824908562022, 6283268137675830065067331797462537135393689865776596511123455280842914950277764363237009204021207048992455578499364721010077624644377707247990280346975761), (1211610431366764352168402726327510717226348390991562086329999623213932185013237148389574771551909153586017444038918679715846733767162113554897134381786857, 75890730458943333025194715524386369656521071930722746159192711605359854334408336712516971401482485856722264977093568378755332998091145606467524694022005), (244903647802361159234473759033970277101947010972078280024742933642939666938312166876253297285079594918029048929696779885690658485203229552774163307540527, 2373795331710340927904919527431920677134638317001768861997636477879161136565412315842928726459213509128420415469002458262377549273973413456729259645667081), (4518760678060599679909177452948270480104877399738014965483049187460721525493761233760548882732960457851992635218409356153777722692601200073553344031670591, 8844414999289227581153616998777815187477522162918537769044686408474927411650248894785074733623205677554062392358203149515274858608766036991829360470823616), (7592345592757926322533225585965745852381733664983345841921848235641404751106413165968435596336418840336833946175594213776899783902724156504533277309269748, 7089085970387423893470381612277566794495981120588669871468780918688535964500273447679956483769050530778883531638335304643560332298158937945270743814682623), (6652263928445973528434466302310957420312179920242004503659877272306847892439644401804526910545108797451584911334440716904829428455553973370303479137669862, 9458402535034543137688012344871771892718470346089762973959832487262392611917412367148125260118343987049054889021450509161330937353686324687399146372114555), (3534522235625804081782547535129005393640287042945365280156063171164962904773202465068726909215926776493848597544447661981935558256321815553387602224881402, 4837966594238884711619882735799140214707375699662533863057637709791852364423463612041321921688460798299681824759465031813340318932649449330160275599814037), (8489217169805464821985370421508113699907794585340231178253442053530804844014743971524390512911984069946788791398908448504228292544706216842945238075375121, 1215447505302825854620898438338187142379952575453204980113562393440560078665709625633076292146758392214003906956271799784549190844357091614327879810572614), (542866374831280210116868654232269583548182299245184843122199072291421509038698477122793634423164448651492131464211098924060636518840223616582501005368460, 2022629414897055122833264218716283219075820516392915632776088172439409817469170549856636359122073001721945168568859176621426050214204543146034962228130925), (1782068204207063364267463067910651115847153546501372162313291846373210482322316042357998975959880005977040661989026270693434275687048799542828964454143556, 7527340839795294976004901268464466405969396744930623524310193111333174704987886820235949755916965632856605403760085036822434722102962968998264602141837419), (1418655321298053089450639566293571708389203083028128512051014311505595961997136750969632337080188319581703211093221375532451355415558953065439270091246275, 8780404905854165984880955825594617434833470735841570736362399271760415045759401454969595440567888094987607107131023411181252898464341897435202426092732253), (2557725049512369460982587222151820006276273524015733210122228687601619929848317295335814413418199416403368586279369859655510576665124544771264416300202560, 2218787590174677941864769503137342405220099048873671025113239015953562879310874802846442132680849931599500397998164043844369373171785028813840455905285977), (8925411826262344989317995746652264189645582747168173819908014708048810819560392738157920662243568873158086505314125039215400948723812883848663225884234258, 264976718868892674047707027663846314545839377871160129772123452391414702524232165707138561706503125546705393013471483153815333294865019521048053448486872), (7340362364032221022610048805244943440320935503040735511766624640689337450391565131407712237653010296919799745690639779160522406900845288007514282932848348, 4742772816076438667205281996528859317852750219583105541149618162608799420365027958845988095207536082642311229063092035324437677963368050154663839879580619), (4365949468540445040511811447586213628108476160181686420253446029848475024657768944216073001397679033295456031375693858737648264257672489352689406067877617, 2223749695150818564168687901951467379789783275610675971246415907935013907780109590272585537986275885769920206118599310753449867285401783174205526503809762), (5350722282448154373233412291907928460292284176243326731805506774685410428233861282237380097176756299688221909745152758135677944095148037060033199099526138, 7439718518353602761366572490671860022327843069482523579232159503713924377631467295301596927629966721260653012108215871034443528395008490564169724605531766), (5584401176314506460375666578414002406564364590098742288760424993989631883779145334587900630087256201838839023298255001933836792696763816624680469550864929, 3044677290291834330933891769982791070860258184893031587866289786907712627447091771032184404546492158464160746836044825841678393363477263143554017896303515), (7975851701234825778306628233300395596468867250506457411861946084284328346398769049580700355419282117739851979958359701952280028143639203266614446800847216, 3266895609989760838601422476759799373220439444411001571187797365713322063804684335823869436261468949562060013499757466686560730994147465249884498885346713), (7261711521633444897238676688839748649031582198158327009683124099908851677495849411140792062992044779892659474879014132643798388876018423533310926537196366, 2724504365742841057058067566624077192769347482452690219424679614291742555602596903101976443035532054094832695505623548134657809131750793620606807201616546), (5837073769170223814153503982409821882214756194115391113404606835402690287297802278130216141772936613589980154509461019880516933215795002795589091820513640, 4721209364170498790971902755140933756537122384371328524399480214813691394472408574345380541748827977206006931162826144417999285644749435820016509243939352), (305216775383805852506755010695529385671255885181250281533873037490233084671561778673175862904766402670917186812585768107197349714618171026248535551215677, 9272687673876464284222562650314654349340249537644947154621221935889195705461010703204855021431561987318371321195133030451818727146407197435755358188848174), (1578199334399838820482129202986415299606457841496504611068328742602338191259129586197159886191422557906984318607545401150950467045053867379345690991174469, 421774086695026261598804043405769083556585722757120290931398403950305627579724407505778365867236098658694986879803601248515142071959160370620588155703737), (5138242833515182728264711313780772567770339840576237598494302408259746992078664607968386113546456430657122824087653982197663950863757231604709723683796703, 5206157238686405420466991808082763951847196672247376857416224348861235682686721638506580332543252651145006534542113019517668682465350725801153286225643094), (1188738184729606410587697373771816235942088215604021367652259400836828623678124266280546684287032312587245145089395787663364199580483423294824455137650165, 7427696361225590895830969053807925215544522759321061489497634776027834393761970785312408837418303945843448023962824665899967354067054729725781368686743248), (6977213709772716484098593456167368563490387363186132027961769966379158592860130513806590071151546460974151176513929935799961546811613527576713382869472534, 7703342487329438039846856603033236121017144744230118622795867631758503168032241567178314359467799241470862877091966060467887074741634238880804371301530517), (2747388335048822413911860370270751258487626867922755541245915001509008519294203227604635335905371816177820449176783791703135970921629942135233809161321784, 6644730235115100566003558394299724267786156452249800489973451334390302736611173084703201568834658217224928659184890753898905778165989366922969486063984117), (7899055022344052608190588907780843160748584474501107484396845709771251737468732633894808001893702428220070282327863029808775733678221364148546366911815043, 1895079076385395141402009368955285768153260834777258050373805696219882417337122203237726991768169238974315778160133292171129900647017701816484609040537240), (3825382165785894949673765519623197124544723806010714850346819323412725676876679252079139270892068133045270669950243183835684551005583898276526365458944633, 3955873808549008748709411188938540691947471786782580886617928024946557156015647849445046164903447609281349466157453422945625268894514267430411524894756650), (2013039591902424690668410859211841993573457095617527890775299591721610496430219386213734597754259471847638358814929670727612268974557121307350948657278307, 3455596516435345495598473763083818318189143846588226705013351806114185883876871867506211090036628320228245315975841167797364438879222218554439611249533621), (1498368867279899550036153202259498985864880185814488867632779726272063553619326359879185602479190481384127574630030243563071461976494752895229570812995316, 2260899858366918360330342896879673375371597370722679855416236629686741045280595324591474941526473993619509969526785405256725721986489147873163447134420522), (7183455195618691629713544887578048987106610307649665927985548710642853829839129274861284836850112578705969550375117525504494947289060757355595486112066172, 6944915640486881677912339082754284548990789536315324879134155252279829567213294759725914392442435965040404255121518741825741701135482991748014703283970917), (3436874317973899925536904028036232914970427993576670458651862528635607574615796030105939902269570596042914190200538788888320221339091002309674387722987900, 710574693511702850749111752555985627457195606623177479065028444260359885256133351959433066357727644410071785302064682175466410336702777494396500658984627), (1274973064373571423276927452966973920678109621452457241200543206117502001395302165243179420498463730711726004210564020865846402756313081098694496856765214, 7221427190914803448058042295809207837777260141029530541554463370168561300821758592641694716948786441373943189428004839690805913407460883039962704581899799), (8663234201230302096291282144344629189966154536372319806683051797195274034613552797756920015785679176528437113316328514957419624500138853815554602435950682, 3082376371350897777275111944689078773810140354528264036700072232995572011967565170731561120462372072607061345353218225654727207052704423590688477223106493), (3072010823571892800213739365827447092424740397412924028505886779080974885205272456535937015659292546650680363096585025765985218597517808043043257537175058, 6927279702565627558578535152372428254276260537187583207602067843114775472468940061246808776026661643124488882554325029341498931420644367652293244501703446), (4254757264595419254220841391976323603990052824876324065604307570593406786360571404882955267293077847834423900635694059478130013727073367367925691083586571, 7448674929350652455567867947647267235140872525151853145599958042805953658547907349621948050604343015249574350721799519757583230075252459872022913190437155), (9350468776329052217386508981370342987305250462207304937414786674956212314210965222361696653928268607588375596352758287309190903312051581276341676853926842, 7672203015139063815156367302656852261642439479193666397683206945540465074408447450943029402019789664505436396142414191308177856774180441805625552152972086), (8499169930086123817028949487529925313464818333167923835508328897035807600033278669440809049592174161744507445775422143717986669488942695865470383326679853, 7603208108603630973051985099629921189486055829261839126573403452052113143297502139657665874072910312549780812983276276766434661578026110791742290828571207), (8050881089924225262237175395568100631350110428957800272109042075429277717773530768511976918444581072074425368354447715020802645138191244205691763703888080, 5347566572963234886003595444506016063808506984877691673781742526809687509810338037743651581309887241008205739887851594244496073896450008345810041600238437), (9275361824307151047073034838513207425454246368014947069592792155837077704033685567799855491015098299066838489583103638070644772158280947199821341605594515, 2553965182248544953735558048573088676747819873698140502921618959691533030953521426551361108482667053651386860184221469270527825015165496120904380388342274), (2080861581244781371462083263793364554881010192432463616272901196614440665352976325640663828360284317951641351520028466045066398889871939273492822141150985, 7136942703043500582374075561945850141665461618711131158922626756894592856474827931850181298946553163355415996003183916568341758840605962471615387549638046), (2881856365694443644848746355929829221667863219329758399614983098183692708781411558925710849035402805485803564217762062282397254469115022190125597997291584, 2450175296639617192913660177538477943950886697465974536090567599863635018535555998197143759891815748595368877745540366212394452179499044338249295222238375), (6637893390632522776196450918896418795938470451892955584279932687930689454777336867936197378962954444122083501840238558282502052793919306897846860875184385, 8163123491433922867340211504514397120156363796714815048562760994528456873291970209304550376359470779290340304148905455301266800497995211065831936234183087), (2832690587865311194645158043828914814184823646751251432658516853608281629462464292800411472736761465669807695160943297009567030494714366339726682253136235, 8675443214915513581275574406303617273539961588099967179136438180476443370627527378243615749680263746953789545271064847904884350654390246929899375547643343), (3197211586910751335500674499536566156408079580597202277268353111067926604070667606307030791753488540966085566401616469850116297850923839799200717465534216, 7204447534824349967893888668725907985870515915442872106502776297953623682607674152676544817365724739551839012072841757442321902091908343496871169178145051), (6928397780341380648221742695618921644589528866374804486663447505653283579645940100225153166746948030564186785954161455848219356908499594866571443257877333, 2417942818448632609815623149858919357346718836664394822007627740229421178231940333321243090502437243374611567336131300856074576048910234312103338149535091), (1239374417659607805184118472062043530586219343900630716738451985171759455323347704062375203748476394326313362374274985040499657062638339574341886827817961, 8065964916230346899273776449242120413544531002970447776968721916318731058999716624357301206965868012077615492752427086774705888291544636677233561969401128), (7229935260529332441911754680541939925683855566122010414641007671481937143005396157471745005861892252941415905869301140874691676351133872256896358303145464, 9298857305245645872854719696866211898595996462902940489373648372088693749548809197685227670007128966976767711560987354115671462744141176337148189745471003), (2328366231364620211018541289842651200527406359640342124345890150814669116861576918024048374017295456911438094157515946600244325691414597049899202874890487, 7871741582188097112877302840392617949943691167883289014141378204412480087419336199399195361196391825432865522657939448652253895907047958243154894652097262), (277863171009817002250678919947649788495815885393466191900418053845781624192352334170182490351579395980289102473018498779508239167167493355794599872457245, 3396999462520687295787399505278938240427276698419042121752088738781597181521094136017468106501358039497706650688747722827816433718988509184826207998170537), (9149480954290001316559216768739463788040947379018895089542870423400943413131527864909526392211060934305774196488427948053837411807188389242155460058046459, 4120801630161379758207812432405523996264806568755501922907729288103360930909042399788028844538596303050535800024823954195274159467335377831847473977691774), (8695836096530987366407223196920182056305472217722590732831981846538389890023161098497699911559115854576291657995000978740749316019619680599505434389057279, 1585478763376038153664478929094671539545584799534807652944238505582208548995140532411732366357663115156329521902607742868878755578788774458089890396686511), (2104205284304301648293374138746164117107098558319857354452717265686198171899657543394502130179166854778849463716301422999521481262744229754326719338619363, 2249984208662571270055585221750468416740409590722899296115863785492087423096626650446224564347402754713949815211195859404066850016185507674911062987592805), (4586998810153915007501891257541602175735951882728482674067709768797174046894611766560924322287335708373614963809650401573061075778456631100175295635512177, 9271621077768666351770227666743937775736855094835412023178647463529077758442382146575472348281491028656240462880075770886843940989437352264520885722197156), (4219000244755602230979377951387472620373255587926892419464329523396152621913642334383539238709016829100711881966870544376930582469293255394685352694700911, 969869453531526870536026514961004110385997795310139518731763023624639602891047352884655784984777428971624067754739029364270570759346713110566494362117320), (4839003158529356974090596597864866284409002389879415467052986162495468087614526683690948346607305324206922237193100662434226657407999685403408787922247827, 413656969866859264778512184799802854338467425221550306789006183384106601540775834502288718724262307800118453045011140318940045472839038552229524320375839), (6053636273904675440280767005893249601713942043374642335116698466355950466466635004837614633068288010528462050975021056823034076638945005148394198887409487, 1625541625276684110014346576712422313657729012511162302520140444195789593987308621008142059263340846941683515782628042796715992189976616276355648042966407), (8558869195616689350115052074866756792485810825503485258930606884450567591085006179033183751173827798144367014340190894928151988579837265999367136165700546, 2208931173308619506564117222710680880992046076969773741029568907452523371025804243424575699194734530457160809750860589143890316549772289984491188907636584), (7534067116330136603313644029251826745967462652960341763819952775379375746131845380183198486066151766947999431036900865876507997330787083847678111383360032, 4455605347935193831744444402597895770993213316170139642656395936745898298113549750312024334555231244087097535564838421695385283197222489267434465935930551), (5052371196124391632972318477399978756167577180835948165910264366866430095683999100063212779669312287552521074845900363295981046421893016238200316661473597, 2208833610555510039684419075678353744407599241909367319625041751688426775546232027995134939328097959287806094371268665024054151258576553998111908879291250), (8089828724109680518064420204424069012318890162705811097397084988737332919034749698254530426007927566587458549763889388917728037282441472935929231978320253, 1681620148836282913859462769965488859826797776174217754772286962571800889473763036314867925529839059864716712885608914402800666875807109225698725762755842), (5748592703602927773445048555725946441510447919778687441964194737731463365301879238920580085296167254293947366406411469963418265451381433150262442585848074, 5832748850224307452284750496400294425845343047842593490414139851765736189882982637536792075926338572999177446937592220340717678673927129218539656805973797), (3134102131717004202447949657379576920795975238187314136147565911847305921539692505302827911057017001577017591401060325909563628145629948237951095573222136, 3307478247612783581969162903580546045995448391281540168834435207121428174781166096580407088036633330625873854565800924082615447197024864852293884022097511), (6631891429771741207345019960664902321804063798864502375938791165319515544470958075930000771061489655117390341594518201452119682162000578101498064896423750, 13580715017478573533188279079601938641630049499578287463074902999484023326894503336245008050817385378383622009249914825220725787373191837916323686010146), (1377503036887914364289964009091710390139423038126543614441121921668102761367737936991403960924934724246020105942873415686645961498266174624490275822910405, 8528287752809200865369562932558801701185092195849074353057344935892973472904917815304961311973573845414423689801532063160439663336541310278133339246571037), (7294615531949040646521892388542093777747872493961761385753781048309437622531600502197910956722934347657414406605414229432707816362684296821176207191790747, 4088416745457375221599323624647506431289794106922257119539519488224805193266443507177496822097248691638469030149039252242460190025905475039632138297736941), (3711621647755218428315324422933849888136653659883380261865194458886876353333966016160758691979857560560495042770834150205233816896306582504243470357087283, 1155039926045241324400116282411623104333308591406954866408142886845265280243667986897050956837723830710185439940968929136733508321464114996781558837984344), (3048489626890411422195879601701391033838809686946025390738522429255884628501007014652303043909771454866130207680435788667753248445311825163417988308985246, 7307356492552463863922143290133932762940400346726658993840943818766597819343918594568786165404193416424940632123092979404281821844756749413234208372626981), (5005209690083298926583829509401676073188105080776520536069396756882847595405296746105471641668305575246596662195204558647565477389258576211279131436397415, 4125831905539604892858432951804739537534968563316992978251379556122752448796259086386174991165307238395871219169684957379829885825227816297313963711778504), (5611881664809664216528795776278785357344213745796099982492318122673199264352522683644251779306322537952246583459794115106048180356494906868592051349326516, 4366419910963250759757052251103772153444139565188830022454973551521221159049842020891070331223496338937997654580792049532356448182705736687622283619580021), (8828026501555327842127007681014112634285418908052745638436025481454101377563572813881697778315546383530233085767948671632695152694781562400957919793630836, 6980967423269148178670174920189255048934342617772814772700057949856011248068586051157418629392165826065159845679183266715277410279685236211110521308479359), (3380976482351221596363263320861403079131184240223561066719174151571272537255264986769006295589496230705786855136758646441574222228162910598210118170437544, 7905596113021198873620016081424374807026414360193257629234083766771470792696091213220036222530003526741105227066864154707481199618448494439873600851458092), (4029380217118171328856934539417914772420463102071060959963193369753477152289883649426663949141271216868787605279574335919308824280607176403409108673350439, 5650294412701848433332037698055340849390941161661022288699552506476286206303470872507906042038727603012681427778071112179326909120649981972448585553923835), (3394481330446252316029041454835695368163437462374592223776214133373198624809257354147928022384097011523904620774869571256987028852050957695006239261116255, 673388564013077662797665451328820137732720696357472704254996209186624225765896841751210635975756558870231513192208084255601346418864367723430171707761991), (8297076837465667827931460088195667188127763702203061819727117206320812568593999228141754011600396307977539566282016840063710524426206175864189499955291654, 5209319951376565328476074984656589296649757740154227849463085978540952865217442061419512702718289611013441922054627134068629808786052170853735297105069439), (7408750781139676876498079279497232543267316949742873854711785209018069863360050407002944798218118456513455615410225053229628229323769179280242970637098975, 9268315942147581683114856308498028824675036825430851779383699778791924099645787566514941844223520404934229613077384974367420753043038898674571881350008312), (3763070322192859358699559288379051478714826263903691210702438064060069281371577972443393952620431790585998882052031348400101605885460988938034052962535892, 6596312124931041488568777971819346457071194356760227796212353685251408460220624277244155588026371188787412278492809550066395446873919015258116165859111337), (9456467399578713192177485441300675604130657519125034984296652415520104967897131968485689166694947105534278560152675818270484565213970195849556339603047566, 908429398249110578889046322413146397592415049106156676342280737751598831300011336553534728810376690697882311638154624793469668736649168002120308317220607), (3285374756890429736973266959101287595172645357052640520201945382643618005297502028940620540522226233412656990587428454930879264684377934233733750288710767, 2328822418042150416149798861501191276195135152292697165048445017161848819153053133458383382661003997526780737455432951912170448030074373346089623355750829), (1952125997160022433691464471633218048651370008053616404111137588621786092528861834526997243296409840702228803448093140762847527396149122121089383732066474, 6567294304782256626176849472325750335625416078034393246301379152123743008595187459881351443636177881675595086820113167733102264072254470247247505657421149), (8048531996258673030482386551215075865981405539122593043242693796147000303883395895161954896300165416418656564904286194132702644247302493429304189653931447, 454418713895298471932122990893361206252992842774812605456488108951361795024004077919370453543388273294439833540359135110565881365927368358543721396939509), (6442849832081189651780610378700634484141782190895744266616557147635575441440457815503503312822935585934224506886222152583180470904282947021601475665824471, 7962589839054206272978510317514803102688577017586771184466619564119537112089115220809814630243440198221307715904722820403079352131216487387251656630405092), (9157313859025195775533567035331999321995378295851290288655317269258112264280743413156214916597192906190467767163832021955700905097004252518156837099479963, 6871491291754566526702848741550097883789454006440764230331672103004019920166847976474641203913939081232671105421824254933876485141292385495132941377024723), (4345539225307590730792268726299287203822970967699332326895002068788703337808646409340727374347090969794534227536558706143121807613587620379686468931138419, 6870992216179853782569673022472973508605923251870642063100935156925184979601842634454329793875432217403639894951571881809550894497880635415320473331774353), (3610770726691746088052688044583546228105057610743167019495087130106656721249082416846164464027240140667058699182842799303015225386379122022710383740156958, 8300466371565693321266680204405823545697811028885585027325352476372487206927020868077145600293899561130587976332525491711660991344521886336241594904292179), (1095131035702085570104796652545848394057211540039044388148226196788582078450011209526203478685248252121120698817296948897889832020318594798626133763457607, 4537321261347923035510437559400185585042858705187391579338553543440597758631527772806125954425255162537711198309215313452309536854215195272900793003357082), (799562197825255213599035458804171336841049803417226786071573908886515370819066407588112410194283019360987098613389934509236505944885674735039032609970377, 7330149362601248481645771280767362307754602983543308335895096021919730204820895349728815010568735105268416403590395967113314265472388297167416055450138438), (5466382159715811371726261379846114594774449791105554234087295571932414283384855609582849117953449795249351701421791738255874925816147499017701441300658525, 4005858816723811632005724459845786968777252756990039167884573608622673158539100859198529376623151460822486746636588811029226543563205319470006714094258123), (2818592048873601615637226023737222503401747693380977398286296993162374819212393040098399037872308142767673042678451275351213677138138860281296466609826738, 5553083493107181323208530199462737739451919253737143548029985581159756844628252810785139533437660744905303546547500959990620097109306498299704456741704683), (7701260380927259585610376430393927117363003996985911457168980677740860385495001634128549543201062665575919517384810179363684521019050449318638562741232214, 1206207451648074332792732585487237185524930606119482148824745564243171035468533091300039874880085842380266650071780972592281126180204630013441466984819790), (1423565695970345555236463377310277810906124883334763067260948646895640960981374411327547405650178141992625681439960985155605211807164467765255686192046129, 2650256411952793528356437910258428774857777148866684938666926430071058495139763688567647610548117559577975274104990349409450824706113384303302457007486669), (5938439627953971908968452321145198701777137540677247542472628168811974053079568733190971331382953129293145392003871175930313037721264211288747472116778632, 4601176607738670717829013658501945445910096304794095333283286196865575581332140575300535281996300237376143402916485269476647092198720198729276080533281156), (7685031714674567642630532750469454155372661938686739286224893224388057567733367187173520037917182320731407731450918858628153041412677526785738446325051794, 8710373309991568938951497945585371729383329348496443489023441935656986680316614086300602180933069352706310856720747136772209264043019619829303853759989887), (4223713933443443887866943408131329781459022398987049277812676260304970762845800969848643883823180201844055884997700618420601581657523976185055621469762689, 196370186285147846643183906974986556548402156774254714015237147300714437363218320813583598372581607984439966674073435406257415767654759446329460653932593), (4138472681306810838006585874467412198121174841738657617125512581651173984249024960629163462668215507871139909281406453592428007467791261890891300522526041, 3367503680779921786266176768749621832100527464429867802591603286463243513187736745396883406884242769133592582756112174694300974689299685098227863190956096), (8637579731113172769498196733242586321888529712976250435264299207538200690578603982185735160712870315805726226657382419894814130860366173622240557410309099, 5861413807901252043738246035607295267067585916979146477082434998517244002346026780605642713924184744056924221152614675323567685921570787507813534307287688), (3582410717060591717715105115252008249436267824581237598332971417566770788111105092512464544695857286995642695649849893170089754981288072065628587866330987, 8368053624859130530562884791876798403783149327641703297590304759032426056428650056719025865691654213746372711643204652391575030471350361470182255692303672), (6138385431903161702739090318698436131075858414242382227185566593052355358522620790795823635369311218265944450117950811581661849143002073890965998158959525, 8186927170729642180072027453764803931415057731250381790527477719047559899134420930499657563355994565869411767649954215306415688983202351924418767632011655), (1576012212846947339506537505037067194228948091814234846929198234133994711255690848012786786734534406348880902260953846694057041799646020222457596274397051, 2491916687108098496631664430838938945142662463196333237203890033364754234746224034270355794878473248638434683251883993444151185744044032240292533758434845), (6495542538039209538299838769081798991231135003942443710855605287435377216457682615086329265614179451670546674962660235227157254824484959978774322800940241, 5267842572062325027183193540573585289443252544924652116822528990407427092626379117776257064882376284678662480949881944564259260986031306467472271303805294), (2074898476906482501449548886789473751331968993836337310894514418437459651212456425727996278452961517021500035505059709053266794840818257619996356206729864, 3558073295215301656008498670239428462892636509533393981019638607790058489262431292401862013712686446102474023627882568388311818768321114768434391625802897), (7778977431394685886389066406044927787621992782892367919405821348951823442015331330477735050620460442836092615187738214992022542531468147669319806552738088, 851043018790458835984345018307437830836922225196604095325702699283422988687440128488428717257567677370133596867845622322865026265965626884269005361761716), (1241865368745373505491828621468536410959253347478290850549358693845978800428321454988712095358499758537528602331963190720884536254606762826721394269187904, 2041671839138168803006654996271714137526338969063517101241475733012440362313674663495288060233631432999143830430832056122152870777629918576194970479489027), (3985868450641779273853280879475439126178015350163799382130238386358694329029242945390318670589963623116206235168122235516792847373270671773103043374400389, 1309966950079890164189390380472675555249312153217811819324370924095019503562924816968644395762142862138755368444158125336329567004134437147032003660830089), (6849333900583505984488773956069611294607580804928597070461676869588685501657348208808559566369599161731705696217320085865039314296905338848528194989747303, 2365329003049616137222726916393563259280233732458295254985789898873276310773466923527252539346983976854300470924959948913425981444484317329044905991667605), (2632755205906171951166305280857221178403637693999067235831322171820979332659941670097935440497291536077699476994625921725104937586040075006866710438423342, 6490093263623135024725210221015240616725453731635594920968859513664762046191234617042273299784853716352111245362135778475447670955582193169903330761557563), (8987737806562854165556194529702782017902218901422065462402172681181354888822822887655528076505612799368532810971366312961924880604969872704030142530826691, 3008113438490886956517760337096399748777109273114643170748753619131558106059765065191903108375337890855742056405122638381672973559130530834868369029930924), (7089604318639163870759508199511003228494882646195803705916927812835820904355014316568403407463218235732574812685262294429382685295394692891822320721806457, 5496845333458545367526482738141368503483360513875884684740915705828041642208637069226323790999683337387774748487348278472216738147845803550243225021530945), (7822075033407225903777452468367602174573059849384231711597471386388553877371466196778409435201984415487683369260642051832992472719217507254123801961625400, 4246386424545941722038727746278462351224869329610212613188044215725346012396140301207746555020808284493229271463962894998835155588560646299418051301575920), (1887368412196774638148674941814497032391005881827804518125667959013929187908632292934287443879733040159348703284540981166477041480438825814118151438346845, 2008925806128466283950465494312260702686173980610769894644826571179663751268022870659495950150284226024233956786310009396779125761686141525224957467710926), (1737696589563407889976245701676840569918453387164660433723780970427713862678894608543803274591311020330387162144128665455852288254517058728186268945512966, 6799001834273534685078742405688743875791084418019112795665511039169357046249783236514573777843153188800169063643719643526034136981316887492430002288400088), (6728918083650656791133441510075472969432201850670267750840060456503048549960242278135584864198567874123325655114733910192044589122618394957074964754102100, 6410928277923076773111028671091948779932404730828591243536761412171380458478924543367433676001807812386407632763598205888302868850307084599625659625842797), (5762252348084934543075287957811880336257416762501368976282331059213635836274847318511590583139820034772290774841187996767151894083507340116254819529810589, 4493010986852490267474524252467399652035001541212170583205661424367799374015806652478134334605000084332297077439122232979904439236579686717297218264111480), (8639565433931379219025112114059798634173582376999567885849213023444100864291667649023678444944620196060121853981418430202040887275372388381956958162045641, 8247625327052550269728170549628174340945191918500873318965454732428230277342296266689288917712254820149026342223473364152191511138150820649764745550073832), (6318687552328389619656683864433270368410914752871070393806364734725950511763974023905240549523404053648990386266088465841771363937167352158100556505124384, 7167417232374354990970280427810268861836418918388138287491833869868925993360257267314108042081391709514169053424379206163981421338057982449703020266977379), (1559881572853671214558289528417390499591013357902732399947446364590768208386661194913255403195950328963492838829413527460657198123194424722276308838580574, 8019909746697111093661309213326817858438244351200790274786877364130016320552531761591482851422548070050476569167353012863697047649645128227721437697096142), (4235080895876390868495406712567153977859303520263763306881533936610152035603860829126505464314268755916028662546825840354792302810158457880063714313031346, 6583048618052048208207299325354604687813863766597831311495348139563657189109904665712463365904280953280213301857995458074596921140529235128376887683822155), (5826149521987382642619358780216740855100616029235045825060663115604436144190636947410615568398231486799266821105934648516645674966083881126708040761534343, 3499243963189775491743379050943512379148808305089365113414120311475980718769099268758335382739981268641510619716359449153128422224656499172228023620619520), (2231425540787237122356286930110008440544371949457027336518412169211666216585342242848373669926019357729617582287745489972929275792313082590071392365431250, 6027557224922823694495795435190767267045772393633769024729421422714068677967455046273854497365142463989878654351879725661914376314612651382382233925356682), (352142655003220096000894302425047429538661162420048961517991722903978652768994733997974916151069078729583360996057061297167116734674291284765901249603008, 819165413283803860339793340388103940537519925135594105392425970806984411450402214368719424681171826713188968815322946524266721066113159282693861060457071), (7659584802205578888784905726449047492968397662006224029165147848429182746956940129189322305967169209500354850800117748382367834816413509808656101965526080, 870733999881223906459538555042614376143696897380261118808911207084315649296910289452501461521811339574371476267772317387404135275665609613655457735509693), (1524078769004108095163428965493879996835110305433591416119041517857763133745028585853776605982615769379696657853976281095531595903871101588862460402692331, 1031472656328960684630000158606806862730082927172646838489758329856707800314301538684567533513563348435074912415838349478802228438190581640423809461059544), (8535477212134439121071783355319907794363368905316016462628958925910180376025027412884036128500657896705017779765312780288344610593657360215593353099643314, 2530226705384308905194285937506301317464847902130097409053350230337763599754000214789803202441350003703031752637144299465106774421314752520106198468557159), (8409209398763566849317756864849522709897369321393678846331586642967224678558009846384190544770949731025303640806067216196514982998562618353963854759945188, 8930609016696060445241489289920153833656704746760189533995796831260297405532642801433076897769460308565764983021411778015226529444157741743081557811299848), (6487844072654569312743939652548536569626161210154867735037194940382038262272043992149076734381181891648720037958276786172035417914745775227017708421409010, 1962108163861988031794491500935068439120133971706067404130764266181237497109062437313272678135932967393445944674780189241367282621859728302010078735495555), (501984209642842640566545904990019267176380252044116311904626422369866799212391199854964066207131592305499700740781010820524789440586337849349031447312605, 6140381242926291962659383880318778588527444106498989689527810242639132382683371071477234252863506103355154260518839562271306834933892425755802372675292455), (1784787001239858291114920379100093959085746114419034864953631464461194428345378123486176032178615741020389281467797760834560257164184928317947468184300045, 330676002834594840100115763831208954936356939938573486827598011099042332902522750782422361507006435466170339938140547582675961894269069950203674274528514), (2058101367093606905521500733040033697816508848780212666930676548499966352832543751130359231655067036068810820046142783666166621123269689872247861873639107, 1473447920654518231389973122431388989733983736833316507734030658722211239641846446292166156977217600415170675920137458990630108127864790365587973832735919), (711783505132653913587943363222529667730432737505636781188706801749562692197285450603412514649871167706835636231919514443730588724160095796624119621805782, 1847545467145858097474382533434351177546254187255462543826653345951777211232443819429558454435213261837314448173523859380937157541493338582605594136848059), (481278799733754767253657402786402259515751661028576158004772032391383846653593371826795535234446331403584699137216696607268593068099089549139394118232164, 4175744893659751717208161617354794355838504687093853684272644979000559636702819780622863734878798222388571283856954344531571438621063071773059875852550581), (1147861774771200234035831826180745157602244449853332416329220555921307876846403972893199952711116017868665901747923982678232045230734639210395739786168253, 2242349232331656173629825294252895583228659181460227489808437501844412748020921571697451778919991061132291473700462220458628807969414855230368976841943212), (941908658925180669900654553293766370378751877070781721130303041620097678048675193187325325277250960453552158842515106051287362421576764631130750936221406, 4813306722191001508690579319145165042054624250354593144999980423595387635415075943733569009361212132303966082256533101780581859301437411072014054661115847), (4608390421777718977420211849770736915183777229061607114304404930124399415255948426283746893889002345294245372138977774300468494313835733991338337569257330, 5729747374650657818400809678669232680366757154537784284336901951714361823388338626146792749203677377524155961461754377627048542412589521189059526296674870), (6146430666449067898308690265887953955428600992017361719257071007542845817546734908590134590345438077598653576033503179399774998179397028698760348980608211, 3787642520931013021502388858482058550812222333642300396560378416322742734733946247049383516842644052419314174541010174961191286400769611346881448850264923), (1662003723725726427617224350742861155896907301763708827616482041318155633154642060517333841646852875011506755157173537603712078363540719399704615353674351, 7918570846927390722641090458186237665878880168267090837295484830211787858844502364991793712505358915907823623743915646893545874367216595331419456934685905), (2386057455654321456634704614262627951009991358319342073126505446232289775764300217434213214901370677359552089406951095448621727818533498494816803948566031, 4538469678513935894849902317441570372925499465758210768971321624980370266913875656217621638502047830220114618688506012763406114583790054974882957392243948), (4286109387680088773184822163432238850063953450361026379425819754497173840494628318974825300625924647602606586509445954503405171354341283862336576152420891, 4753822629361672046845539984668403459032167035689085898239268957925619257266200380487875097137508876892510119948058802461154249390121735776265504139167766), (5483425581433383070714130128521929780902352317612900495574277390395701193907216776511463100445508440541463674401112281112643081123553910161846779976099857, 8768965040262312235825999475951348364090128684323641311550280384528029076403670073479076518610243992404547539290324135641849587600475364142106903557935536), (9050071327292496843398349356277193465366517480752361490162088383218463969352980226298471831792024519343345252175809316461422206102029744760556716161277220, 3207985372763099561679281272776847023064207657730159968263302486078501794256624338670169870853192220628120758547727051548909322454566018975367876518077591), (6030099957220788335495302877157920482262604405458760958348977148872559836005400933001522365426855136690567625897463538438674822604005099910641404554263832, 8699292682192407789029287277528254358160028497161059210498684796854118874990479646359555657606702696137849981077209864482994023097920172045263274096006898), (7994698206962177845055687834603688961605362456126034397566157316434125739073581796290673207737738558360831135209291149779785700760644654564103781468828247, 5428314238271442702385260853693187214523486710675063228041106780030218607673758484511529560321294806757945280670657032654714409624105098517423175744912682), (6522813909606933276571953348195616568284606530000039532977316336608883011335824358761182116437177720704721422408381597137065708046332218141637881167505498, 2122483782074391119386933986883382015130964842008130903639534167974057839623659441609368813939235164764921058184490042100406207310119017315608800780773158), (3331230134322321843648300782082261407527128701980867834733091857509890405936379633661284671918782577428148117693190985090261312083462837684742937944211130, 7331143537722654847849864341314141859042521035622378389703282396036674077059339493595988665001400735533051829997236199172453843627937156912623686509308158), (236601978356533313499902203380579486948422644353296745550202903267017530818053032113108034043252116269713370144776756205524381570446502967189283787945534, 7590143757198896661202939820689763613661835851224087607185851822272752589527774767528543528278477137029614461196717039977924765952931334065880411187570828), (9083205516671029530027189991824855978075189861894449803318818276322001321646489478418844901674023445322192273952993776459542751043872009284155514379082916, 6964292308829427282900770334228475863671455454795450434065343428853709044885310024343728894651848702882611873545698142591366666497121675806687560890491083), (1436987082079544093741892201887310040575144786536877434716296447125414127439172561394853004948786366120483639587324918079542954775239450762326324067865361, 8146375356370947672925405696061501896982529603015367241494835054681038317160609445701557709761549181413175846452168632204708635084072498454308692771972942), (356217291899714254454508434913030734305936426887806888098043657743771778885906622294420765020290278370683789594710197230491328027872960581866626846198126, 8115398719910925563302902583439058580479849399546195327117744950059255211119563277195486516919544117421004193458585860172266169287638122472131996816508863), (6686722551852367424123561752986859964055345735552078666308034600127891767407772155840087353207968736623767953152505592663151523099770485483887871234254132, 2705297441123241584083336484371635701567530008898742037835906159591846926717810196994059085622997195625873154726353257157933332495463335414199549093320785), (7960066838109432722319508865312419121970698536260731450973828652914726838377311675664084332888850700206872736972679067742934766647297693945487854647770474, 1127064622633115897677114817706571732689944417112451853983025289241404674414958963500167778852068818951363888671557667894954194574178010034620125096195718), (8140298116523689862579890385716503802961011911407533766095439594233143652597087136303037757252028546821240815946041379750341451736497244688176405757157087, 8018835266911613605157757467460756092639835110837051859518389312985110578193024465910868748446764276440060065672717863955108464100906531144837572712869773), (2538544499311980696845188991700616213102142770479448190942858770593096273769568941518408401082103623490150491190101546046077177978625142936051409518207650, 3843765801254389552198245062358964756408381816193002135480340127143440396017329403002182870661136586144162050285375796100307334849338202201721322218525556), (4212863984936341937547832970220829179417957770855779103515022120068887113671404748942109765236261245451134462602331985195005817577883017380499950968286650, 5227092355396787321198771611605397717409281082235529261628754919662165834203147911625405595751169951795006267489725034828291307601456365764774579126454644), (8671300349223936872915832494027599560572586773878721048716079384981618777069041827267348751582017270194709573701088088128791317658652544689751639665342988, 3722302209129339053209839907820363636393079420495450655631174064725787642867616367484321343581655830844052617505805763173332482102635286952177093069589614), (7710327908683054534037509705363001482846423360313445446066719914815810492008189064800884896716441999825064523756470596096799246977858792145313934160966241, 3665514488765831037894746080891920678293271803677740802947908324892895939943238410151131604036363539635727476166268072743159542013053331804527944603673148), (9247835674012211953333117373185959166242544867066697375982083331423888964137355149501649845721586646662907121072242805972038907583341794344398628528786487, 4638081908895158252350283307234190214193128300577873789836256274207188570874725597623551420811011878392741267712833232980052827091319799807099132835326131), (9024262768144206093183487513808696229187041695160355731452476324656232831442708568500648623820659737228952646727511975974663572902740274279127305042982440, 3670453433423126440579208658193636588354896229956494557213449968714850252227064734943312523575797459021770481708895420566844071864384378258127040324020535), (2486820906980854458163860471490666805964417644513426068392185462735617725485239928714256142324899556299810739388491341104194229963362181103260241808275949, 6882137754926530209663701411685040390598035655589434574560779130260284196979460714329495462287003980639389430949925384480403648921078154565654919605228763), (8961353311740899834327639051650063540154550070663479654554557892681732171202530529058253847107292511201453564269596896656834090426039444881518900692236703, 4523054086812878753826554846174024239662610404721524985551173367138811541569989252006073197350976888688238306215407682507714729203601617170685990325605475), (8693606745964966762771489843065764015187010896157043378692231598585856615369467739416612354176278329439229102927268325491428664588687009131420603866923112, 2249981795584239615615699701534057239823773812761910868377859855287386397988553996086778364484174851149750280593175239266453847888675623352020940839739349), (8043724352048792481880542560437546440339181583582133275459027954460738317994417192207897907181892876378671946153231513732600436513318841567376587362648809, 7310236761819485855407413588275738265159350158783690701070440433219131150896789581859244114840231926079077333072143515744501987947873503695290964910345121), (4309441174308679554364587071618697932030579266968621126995248910996855488027514764022129660372138355105840056461519060052238739808565875408632878802543392, 2998240306043622152686232965588174541881092752046158731499396769192023480307789893792316617814747738316166900057102806572498346338226336587286493718289296), (488449015182964500721676458560709517390587837658055806644758226416057760364977088943600570105867252311768932403978615745192544539465422828624588910411671, 5214042886430786941857536241955389024287109316912779717405443763091704060632732498739281227947659154273905207193929305221207610365960700098681705522622901), (4088249364785213321253135585437458143179652268529876853607988548745817456120814812543423023607554701799097163787342264137536600465915532494132137348776547, 1173495876607379302337280830537918793455550927973853606594419772668073017424365588327289414547691696835401912292019424755494030268708312117011184652464646), (8952158598763453521096535738093146057870956569477509351554101183592166148485760712600661253306614173878421946352784184865921577252351226990642861815143461, 1340575843468052966595169438919181377502944273079884886255295545346210546812981106989620980776011706149835441301336305213125903433040407282099843391324086), (5199913388644144351597338943446237123054971540833189119136257854373487255021033015379661632867865967694279467895807078253677941235570949072212435730610869, 7549954119547011681515101294223117116525627826943348122969579335393167614276259599872681782164368597815211482389518969730029624687821970725047011531139434), (1052308023744767875863447307795798789503062153232576687806383558782934385845669404258381638627968903984395310614113720440376767936250417146792749106647592, 5602525975925742297924657991985099781679912139487510509056869852095756235535526903400521470400854277035251201322507866718002529294197996441560492388776357), (4461721073334016315804582902402803137406983306190645247959191557189639185209092160797044190754615304874666116958266060726804372421449072805229197129771692, 8935770855805057883553467203074344270529781218632554626937638963101924747308013756322309877374475383525609494073956197255340499494824710634478015134846611), (3317194845050119326750104526860107513951783271571036452036851150451019066766270151660180290696612175261272904727017320911540833497338615178810898711886560, 7971567606107352839975922921474135734167676392620073873046290844179439741984071396591619239686398672025184561935997621683082428940091435179807379991042115), (5893153501501563350921058908362193044558243130018680448972924371448307671371235512123061331981827652598822282849312869606401231088913300519163350316561376, 7851634122116659836209152794849366770334438348999607734493048427237647090425446162055777555146312114741639148186029630187259004197628469688758315881531258), (1779216599070370023159788356912546092134765883051549819766778929245229165000042304059038590185882834980156633040505986772512824626680450948526182350168067, 7245261745897705184561210514164438190766788203513590846472398552279766961285237372950386812282987084222539002905189691299452464947963681497281813080659363), (4668941500822692809227606597574292648353482906731178427992664562643577858646567206889758446837082308537809434200400127820511660877856158021275952349280559, 8582368428075610168747661225760743106555292116769243893984589443453636874536333664392430199850747474904164060001617210686271620342641331795514933202288607), (3332451717804162659159191658497738881760177287133658472390465646675629851808092620178469843579217900895086597994713891975423843371550043804128030971925682, 204072715196999296960655253218714401015637244097396344681786358779240421703238795647239059959380336346814406909743311968797642782384190374916696487133298), (9360040582818984044661001719727886965493873189281209996769327582761488099895151133381893056633173539894702947154187540417425945678196609622741112759332625, 6362377207836699021612916162580527638095453066265700269740631318489193041957049679671413910934902275339824652276877560140781852488908708083283482390912481), (2670096736294007235368405308188012904369684448804554294600960224640015075237215147909607563097362289613781605552741504035793499724714402302917966718793480, 174610447065549108266977161234446427891988465359408536236020683515368486229515747150129935484643560641588332057124207481785042956590483221122573865538143), (8584733050705735500164183532950178257761912316647750886022369104689356714292487369799191446147539948982310476448720558235489103710514821930094920547940725, 8515881623728561327720720213059759622554560182557747636474884128377216662832660050224820130004453043231587094283047923888321585380148890046653858803040546), (1586071020639296192048087857123603911616365868135933363248625186822051452284925006050074908403824287067636545538218859273831665862853599398333349916712464, 8929096428229489705906932365822874306234090300132461211898825482800448871343737588208736432934623579456825198960621320150177832269314880786505376913143851), (5304997973285011552368685368538593513871991773572006415401460274461957969509475206396424073553392122410366736113774960412696938201318167413010159502619987, 1971464079371625110328508452454183812620719331876954036959792941387606562363616920044152389672171845162696852854369263267533428561924942040323871903557778), (386765728386292083401502713482722949073582268186108637619604703195120868724779759825803487374013819365495011735512860410490863729051784894347520184245324, 5072263988465557431910077690164230533774251025007329425585135742239588972368770854128852531793728048785375550039352337811128460779332562872425433397104425), (7370475066042039771139398550833648721625908579735583044129377622932486626677450824294548533751777499033686733532782418733237207103155190400417675522974279, 5537045057171627907592456506103121838867564190695393570472181184953772334516737680729928820040897209599304991576682883407943032558327908753279681110325738), (8976702185448718735387462692036444730809191549037907536327174485458741238575112744366146497743566042272824454352468568941597956809626671149854857718594250, 550218715381870940019590793787009709492643936378957166220477062398456987672083411919153492910845353499409953562065820788484013953635298486472521994157914), (2197275229758974862283797164048600525822355827259142336128233580137385220201329117694300866164530752280482432743899081363544945093957036200874683043275604, 3678082252565729839855751660179277087329567016240574149374826593539019408529942646454956285025186413202490612583117331520641722268136948364056643657599762), (5580181737099637254746090005878373007100801317798017913606073436987591846320601732501658233817251338263828190629666823135401269616510678234195949777899966, 7275085308597183920911971770715319768193189741952753413811365275735835418351183704698014336649394052689000552473160060759736639269022756736240011526994369), (5893920273680182567322820215189805072331748198948610041615957515373215083093225351365382544699426977981181678428067070423820024825081674920167658230460177, 4626273092367849543297439537841777380844763469623516210908252985809291085381915729141998930675934153334509502698049998695505155966345226530755883212368741), (5225885920410748611019701167104582890161097901502931272494854356762743694659655298577412199169224283871656651598984833728259387768148007702008644365940331, 1951901453011015203131603016302498126176911196642287992377986970700020151841924487117216575513832907434882899699001950389215239067556834673928970141267703), (9461289881520900818668739158310718101631991901326335689399647447320473838563778250651375746298418949720534385547970013097666444732483172988139618656880839, 7781050095871507362676298168544596499268375836081963212811040372581566410619722427942460588340439923635507786415043221751905101058935880993839077874055341), (7108230024729135229866786008626308524712057487251832943234586108106428200330206291985810605900688188187184529952172794618582086054670590744063999867452956, 6884845186141168552263111230367086131675606535195252350511687531138349809923592488692588786531522647952315351574660993151562108002494009719512379857277327), (7535434544798027154530316125661028008874650857663078876918199177049741676895693976943108696863002431884090616033210407959817495977800550086806290496181537, 1617309846587552413000866187329201217044725959435186278706493856270129522594705667584236235654504288916899405622146773390009696661094452274816120621481227), (7651833249782077570765380368199191012788716219056626434242118086177079561606871140051483112385070713371101686579949268345613135346806564569606863154960753, 6034580920051956154927163442807128576932234924476724808441259196418079494264506920141351127715018661361082627623735572771125260612239920494203519234528926), (3763622779647687893136920174739240220158029347804296903146283330120676703193038188867363810636849845743780498146482094724923849457425813657210499998977844, 7568257944671254052066213541885708382325548115655184859909915717009088323869488148574530435857396321108275775457564361166550865889755014684728750768123288), (3720416110584960443900411029719862063883841129114752846271622037651407944871843260880367042622345983234405652898934652687034677118442291929853273756909344, 4553043468371941211892864571954981432718829293760491858469370018367170930853787515994012457189414934409349605951098997543486548556869813155437724498755487), (7859617489664887925687793264725324747729527344828700057294700894682651426505791717196834664814985341404026438252085948196436426998605465546791258964526957, 1992451364560210769244619669262616317516285416397419563864015029488128829578571855731987020847400282064197997776174738560664939481658855914792462966198681), (1301364819969882407915908749713279232979690418741691437361121162344487314547005143114381381931059405415168484537511227947170385585226920318415565365037489, 8158772761268704715980408459484665186968771142717342382426812368883541476324360163682879175395666293428046844896609190888831018373337612091423192391976471), (9029239719083730740930985741508241151449019377018223032525477178512802779776435041567871939481142671589883864838175560734925707086603396830026610275527352, 561714813352531865750875638609490815937710069262256079231796639021975531206398950650897188188975966491543716362235261124579881605462896401642760950771146), (5730621160026504952305365893985142634300824700681061874567616760166573727185877328045933876046308190012974024411135022425429910895583417010852454586743218, 9393084008795189829037899078940833305852655897977523071914596972599871740202997090848633839268435266419458242595099912564378592405413939190153545033076176), (6097762005896775506581228592379194604034229061913312351639243604237484426067835489916739632564559764740605517156463018597947066806013133655827222632734259, 740994831641597877435822817428573335558884972901531167526490216929882060553546102910866461018559142379992032559492033749755226154304003849459034292254859), (102661464833296267620301052405767197371781535193352566590021799286739552291296936072610959581923190690263423285248087794550622042932073987913997334662749, 9183052895474841240192721773976713945447272410943232753883240314651251528650107723685917362260302031488229808369962805639679345912126883805144849820043278), (9451372579278092853486397767246944026952167847243556880222109497737026238175156973435030748572698380322211475982004818945983860324436082387140062902436354, 9390795573804002284848280705868148942031042018632436799055040245958665003409168362559055723701798943812846017851117523724691523459935213116999905085654900), (7365579844686042112502818974111462496138454270274478581615160956824398968854175423627258042274534547205457096190775351675097969354639533376785673412164572, 636220585090758421949812605833713517362655790760759694242609869856424874977061618559932866561891850787962477788674562069532060458526875838544236345851405), (90276069985529325270808313870833662930752875115977468093408325354941907072316116869011779781655519577171915220392102281917890788089450769870134076536543, 8739633350471742005337038935439748829893749677425691259351795265271879390930686462971764181048393924392326332814689146009557824185503098113484594628633051), (6527208644752342414533918609737745212622551256505042326356110571566004944041680218897033961056537801304257531453564269507923020188435750764501680390371644, 8039335932793882725705162781211365068263398084555694684308062351904158611972406277020378086030512205331290246648902225508650027121293068588713865298484493), (454630634446479368318767797792310821810670363060541412219312506784998343922140609618172544980722114549353594420152673194858382505832267041565728890501072, 3020678223901832286602144783548896808687624423288796023674803203926627569422271498590145393993041411040499517621148355955927484794408033256604989613951706), (5709704851967582423118156888274918418791123859577392108973364297852553664282846043898355414053176984065953748526562010426953058641391486479787336944724756, 7348496114727265409366488704612735832473710222409503550060509235689094398325317648260407133500613820473368223077835906752029188597547062372205246811388367), (8567714959421560693068382771672666720458722237664011141675368008895004718030466635351006797236690693338220183679312718068044741914041644857898224367310054, 3563761969028957022665296390307989681602015074596102765459073637735532031184685859357542358336825716983262943566314136452955973099087658884562781499779556), (5979718410113376066529345089894251454288473114922638783771192617742674343307227714149646746759483037218624986585139860098264051815420746875325750795595812, 4077437478361047748112582259289353715957591392279984320852445907780687796072624032120894013759817075789680758562544614342962005787263409702066893058263019), (7501924650468451352873180856425614726128543301789142175556778170354259252075856344739743850578546773802509943547046861400211742789709369662081258271206764, 8695064314058893578809531462467801217231749615560603146568436212367570712269404249365433186529653368666732554390318320056760460913727743318724074265069598), (702665514546225601427574705393581736068356145440103171422856835530863881997148814190916017626886823965091877775595696839082752403383883034505858068572566, 6010505472977372987785749629301065238571784893184875128490539637989052092628120714968954094753469538359300067255652540800383959989968651426372972587446903), (8833809279915893378030921443261469626312871640004213702631100405072909977652463088148917400316390334835311254758173003211253068109507385203981498752566414, 5487985832188406328211928809357031755986861433068291319466873472391486670960183776517980545550122817808256065567154122082146758971706449549819284939864342), (4802947006728944620010955306892945598783838383597102711425545123156393363880954112644937224898475950942369767153772478803838223556444359342976736223085737, 1234158821541781722102990913893673544022507006421228976942044913649294479846589091678854439665999863309071875307864744256062060725892212525511591323397299), (820052518069585164694319296046580639203859890174445648698892450302607884664969319089918971654316335739714628497786775877039284907842297239391835665851396, 2067436771178304026916177037878583297142841277232906366514339682216271917688975911476449823610769065245798414291543112810648799201034007941471022339247695), (3215961763755502161398183060237030571489191137098425014737111252965065930578227503853854288741956675613995179315492124940539621727280009550297663152372929, 7711303107689105680583659168347541081968849182266831298878597526356251973869935949241486242596410573777222727286293883649438074123985083538652806571251601), (7357175329875682768922600425509045721399512824275446934953917655397135118085300136805351760307972500806010547405265445490609486547214467628362623653813656, 802434400167114108269611249938496769562094798076002015544861269551383618826325654420388938414413970928818790263482074464871489995852747764281372749116313), (4716692821341775369088434621335743491506347389606015994128835154281050560950308630863725798671887663070876397009697263247189961182395886786337370939856270, 2435846478465484495143742559747400089688994781719850111945883561496225542510407419703474170109946792440499829846387629178538589097947397093218980594739846), (396129784921904538754633917028250750577566688831887153127876843746571212982126842304459156677412538410484778069621276128831276536020023509749484580866475, 6617413034110102391990095131808419362506205339450739895069346089268774835129176743454652078195367904630147089563112199248211754903584397463593196661266470), (4342999129026653675673553542694959933294150365847884951325066420535568111152590243033760122901270094996591931106371368386560588740004587939860760573496312, 1288721229955683382552512570394646211299907856162983373157251347377592000373420746434406412415900114860872757068672847289560898152136595081085089127559093), (6712542467457185666112260832213567710869238605294841402002257370757679066270003158693051748841036685388202079905447880997655520634894853092502563311471858, 781272799139541427905663054237434184980406311587878675661813950439160700568243356567857965436805383810586715320417028483695727074206210523775155373018448), (9299631384462180877823267388989784243629266187092745022875386294661630087674855070829488108326376470575069403775629382708600144246850311106841606324029940, 4017735400413817244842584282513722795419960224619123934455754221654762653123749488964805422599447514260397249911306834674995937204042789441129153999251939), (607015852892972641434805681066963204249564031162024189747424554754413997719774754457404433923347899777105513205337114143951569650462451754693335916144339, 23555107246499569348187199395507294001473738704121261757661163041581852067248951411288659184583819794473510772422330394997035354922225308178057977727861), (2859904909559233355911032258356504876295489583639811147058204494251744695001366326430235872430362392356890696538855234450925257810899113612816514917169543, 1424633878204230390723706200837899624536960887698874735416315371952129140132833492330628986113176864940116150067391260128366471317130040305014991721618559), (7335796304812638951484926907426904417431195233758139184148535460693957337624331677450978903558546102629169026732159100640955449834465366668071718373025307, 9113562567754196890836360799697929939696437314452107752391815580326216471721726756355104520207738932025306300045571530914914173850462429491598268802060432), (4049411863236167163865347583496973973319746916513495550884016841463990294328186380861226146824968004985341928687656811582315396898530385590393462138768707, 6239699945436558367282407165811445654472554487451834850884999857678851956420110804975558225520365399695901293448655806283260327692034930413600361326332118), (1832790391712230621737176852538567400318684582567451393073685227700217455670903909131721517636210486774829449570541768987485864310894804404379839438527654, 8239043256526553692428240949518818854058716098755659225760882372411879396425932135420351136675472384353139371830143327856830236932629292671566387460274768), (6756809818637085949159684162579462241343467580055453545251530131458980779370082369333567784479046217594612166040168443481614159665924306433527283753105348, 6882842951852474129700379725457874960152350970875663422153662406485182811214596967573028919309537342782485777311592814468174207264450921504558297177057960), (3514351469598481385358325686837221670217624104208977667354553196526860011446532668359861614741596665677362544613569875471230076144992786713619070074319337, 5009833606676937791196205492274315787605431368500971769775036301947717730736300624486983219283930797863671263829312141563070424203013559210301796867214177), (7892838708266698730358832871879518713664208513083966090134049680667095750217980641392163325153213948702012689469931747708500841006969336383776700382173379, 3652452430022524220387077262776249922425023570016646774849044079970052990683919925377695060467739252880017828626950035158503099494847279945525981615080804), (2889234756138490623732654173828159158708420516787685873171786640889218304116659773864465406947523222214621060589753413700713191700351006740819960794161963, 4979851805225581458525064508364310821396356800082230800160663253745019461014739512296718952532540299576537962927526748696535068359777666141866915628059825), (9399662150561986881972902201094786660462792564519526420532748166288571721240483482799822420506749358927888671396731630177989479212190642591556879879447508, 2590018198319828650139897529619039171066890671469435385839482268502374066387949711680280114333361992122055888688315406507666887742059250570455075910821438), (656138316195862323734736726258285304751143120974052104646725120204018081102027467105276369469557458029697458942845996936866526982184917903193999284631616, 3616782853854666906786303870879005470593168233185257878036641356725292560567015829100767154901249812553607143963702282271688147715985630814648306966318518), (7150701627087628334074296115801248661297148092155799305650815659920917369789959227021670881461296282752486832861272773628467202841874605139945709614550852, 7948553717024166384099686286955811733710428995234403564009531197499791774518325159484426838166183860065449295463631417687643747869442413710193850825178892), (5028812700113764433072380233683995206551291208652419985774108363499731101707445099414681868965437307477561891416648853808614197222641106805986388646415899, 5645815803072596283516734284528048891755324317112035702501293366418607275260579641254579177779746338147966662912355467904711516916856048932771316757700847), (1166339282852731046592641456350536959082813233601426652720589607163696294966894880912007536746767687432988180127999297889755055708188305457099695964801371, 5860383704861105507947128936316922941578164684087651468531370638710072688727706201200942405384865188391223485566076248925938139919975965466889952442923448), (5596574591049847884642394761169444143596685759960367690138620825154049243357147713360866433896962804982329898481109850203003568287076795680551171261809470, 6306514430646202005784961774209094845882824961586520360784531682110503516454462104043643592136544993778659745620634146188697843992467131186675370421417990), (5583409462286748600285297937381291470911965451125995690530016180805241922332480991946369363936778147272520899828158237861847389122230192391741563078420304, 5801383808255634988382974097872776279165867646898675733060279450722013412377689611798498349033562175754686975619529400744444658188926592406623119036342700), (8943175357960087413492427887918638658816890011789622344208552327280497720673711206397271353553736413252462820525330559197250669796441257151425689604030785, 1648335569626744769451720877169171574790709678046820111127878948038912538226160423734122927955502987988585765825141013400366628985459151024981982154054603), (6658045063118771138078921392460366568502149735428111701651175231630701600399722150474382923143173728650216637658446341494278389179986845195628285233494497, 6387369494656050335003102579733977602665949779083504855078770431759766477457441374909094715933022895008649141131654901464297435018167275030345789389487586), (4984163716926941754738991468225992374577827188811322148653662641776042521787381426343763204504526786790533987942502429526018291944836956140506273473711768, 6751611109368599061571220648761198516992880183251037540910082763406230339368705865255441515155746744238319832190366791708964203902714706176522184404546603), (5594020594241478664916277412373530407285610799540618187157377741911134931619903985521112497508332627800008563950115330405679849191957397786428926452764232, 3663799211692985942507926073375688875404376787957736167447507869140251218393028397139095404065575787166523664252624776401885411224856165037020582230859696), (2687987464797920231454768279257384638050941411162384967153109374327320972888036721547646311322293659967143469354693400731000932573922991690865255757408833, 5829178164649740760533429648936732243677273795501602329361133433434340790478896074255956616709580401383129147159374256394309540999066186051143078436711205), (7213914158940734657443784268935244898820745796567760561025067547761637617092462940637749295963919240680746717069448908471602846240732615183668999674058762, 4164898333642434085927791282569711123918606762225971721514660241018195373114888201920851773912813609087871922818622897713918910883396730943706715767747368), (5569588236324798983030353711684087521045707142662585931071862278399774462360587522991309605238938165341974903004422134332025735903360515115606470969904755, 151028611067982889634555739641250664849231988133545407281027945266320625999643808343033937736995040731675463501648132684418262895036773378498915590673161), (391675350896648433863099344412109339714747815667185985339449619313571852690648332687108006583345679863044337865528445803646471154466613156276547145087651, 2387402536641400373659735047724235657936970964464761566027486278347336057165029119640691724805769940413015359438705971298147753301433738204164659349364294), (2205709241033572141598750886952254872242087780462814285093560343787727786640749178659136349846046799006258471523262249974717890523575337954743084617392560, 617922375401910769668591011524207569491076026802969347928180918855852958979279109270648016097072314959077737928530382628245474786019557249175586890377084), (5497399527044672011633935900592208627828702492141695753643677882957528138607594873061047605995681272239354844766281627697086227549214104853453574067701751, 5454039808358949620926380011056128070410509327591336984970751603756686721679839066804747977501664799474918014692249123806113732266040999278564231436885744), (3232462755437263804524179932517169702471657652900899296624774364069988438367405333297923511753133110442262328748412542574411894589479519155740087622088803, 4110314710627099152367847055538315514379360393421142836941517208977229232460506385971847633717694773384648559261868921039272856223892434510150101795740883), (2226957529376604096038426642598349943716277388897529304344975215178063298091634899293486151772406174217356456505919170674382748576683432597436363077209599, 928944388714102829560490484520022420116423203875614718427466575918077857129426973679768445787505667642603043227562439728507823664276547829820931531627888), (8473436631839655663465611093759014902142574174079817279089979583215960168904237948198476212658830697823072490284966369403060813606058157645973137550697262, 2842132866345166495080735047504167521211840354346663116450342503049311697445679554435872784642634530559977971809955219872815034282492714136307915596443548), (3824858313314160930016638522887957265731016421649231247208097874961981708805124060644092366795203003537978324985679231697533088313106891198715687296399919, 5479544895745530223317963750215647075440494078972139819313337515618107252744973581482260875976883629827408436298540953144988701681789167287161720898004723), (3799231199961165216339237728329886923945329387925414937314346202104710383336036866528568120594875920219028518850313416335608565492208537063050685617649254, 6600484981098443727537798959651519177739123977489620084123332096888735554715859356938728329301595566938461229579482386009407076340608204363944621387682159), (2011705161025019373571326726360952060642050027299163152309602840322412233500007939382306319174013911118903919323304756821754361238190546400212010508088664, 7952046749894536844407528604987283250533934215013150113626249017813529698408658814035345031573100137349909568189629857080815707962339499215260866801609206), (5395734031583461892973463338824132109811371986861059328380122290962968725787027664981833857781427722028138487980247334620777273239798739607513048602867282, 8989105923486108278912797658526637357778131860504018538682282132530678423201869580269001799174748084583198171152248697633710351472863370450947718190861887), (543387360056788933371123659378496507804715755709814856204756358933532644144502036404070981420491720416978999546022980475288573477384895446436518560504042, 8759041192754695050039391133033854889432129417146467976641846938964204854833693665788647599159184720973624438513378297385603508989816718308041631247634564), (6832753213033074862423673024898165981615488843950398026973698778156991314618159606621883449331983769056638564500176890393878779743627433817166545939593591, 8561363330223830219665962522345726251035240190934840649119898938301895073293703283180398441664471095889626756190527461840270544903576152093537991745233819), (6087098315816378410147238157658386651962388298831204934435483128159282354015031968431314712261011840972432270741680508219292284832324520972620981823111895, 4893464920609851588604549383715243587815926591269387390541677127591692261704808207985941284771620861580964816786790402962617873950828228905741600899005000), (5474779758740450713200132323193719751000786861195739272932747640307047773792287600854444393117010049498960815633759776541135333353431089848046114798958378, 3975064861241624784068998721908515053969437658955272728141522497355485068215240062381543827169821673959876546037784003182118889116521982372561583280839298), (6714697745820889821520144714390503460930304661712671502615606438905288509639658617161190661106094907470026798457561615305470456866694716733187925309980139, 1994470849094488879802694903566024641430308867611351419854231813116499001572673049606197166137900282952141804923884183741891795179332389549578349548780462), (2694928891468237857695914535148557852489761297820753069894271585075025202408227988473410921092631231187135868444119036009185412564298566326432115940062729, 8508225235488285792495345334059648653617705166729914684682633840369250158637248978567609190391119460861192299339450409695243463003462407606688420349460070), (7633648275608661181624592811266680504516072384184113699365799825048177034876059676734351612554620919640501022050679652638649824602985862826535763638631741, 8417675520399685454110686125244653222906774557825839565570072644675871834354963879472351990111818645912060979318016250289986586897845322457068113658067063), (1172790216134941151581641045193484826366171808168830312186191438096750199742570492241307119131094420007632356391681268016528371681241864570967453815202733, 7660650890350716303911095691396004202622546260512515457141902179456861704077983786457049434537663264200030705409950839601166974689368650529666373793217815), (7926205950864615795534168307766659502654914571421944630129943321033752385544317627631407858073149564437791696787472252285278498975786398688554521478994565, 759567301324107143813137956777604694126640737015605273331397855105940294885670473706844498835570003872452983353912227511455869301586804704546597382144481), (2879640356024171306718943679864596264277465036304922346265009526868079488857501233411421146885361706987943857796106761354509986942801769161994053440426387, 5188495077415851678397688499659606806431791728812147391713202654304957531595178981984034067837586406395919681998935166473568425931741960099762211004583118), (4747049898638229555377374256246357235979304889623649030027217719971850840756665160911138691318706250305779075850345881150487758389523877383948225443017993, 5147439208367332675163626618960332475663610755615351521368140417703850550062961293452956106515541775056168804564303351191195990743651662976496676687694369), (6652536460299754409869791803856947600698820144832186589312958004113232911658824819429156214453556447527268084578185430129484719572226134298454549899520434, 8958238719492105329019168087490857548300249740160563774073832062826072524151676012083049731775853612384809362252717012170653584994310597766138583534034916), (2177822647808589601881194609606552401295850893053013897040038211408069597502116360609288667446418412277393430780339554892117620873728206144637394241229632, 4705336054672176525533924575454003903236091699951893972475121399003017894479780238928023525858860577557319357812501728726240985716054762993201962363367434), (517372779403407160219715169300884237409951083101172578047801569435431362095157206265370470350074653182122732145538133463172198391506408504921531254894800, 8241923906237970065004140830951714099390252209125513790551827331525420539083182146914190498046226262172590314806430269812163538830654234634920002408984630), (191540515179518040057210674258142806146096637618913969904432168699528964125781727654859016768023776945019198780217354466168194123191373175493126377216907, 477871693611751181543989617887543727700128114866096836174770704089039134230486992046894875297845448655761908491203684084715524761086738595012533747657923), (561352548796187241810845944628282539024062924736204006769530098791053031817033035945401524976455932130769479250560578970389939105589428327506637191298895, 4890270790641344031407601390436720429150113766360039429876909448767292522499027755361858994943081128002840540181593844252883037052938868700620083476443838), (6601657505237545014639964919456282235072448174437181073452902667943321560271332169980225517400163164372984503908575270797520818266217021815400265090184606, 5512106960657406495796869452434756193052776911117241744445771955224122450059290110544137794848583001345716684303261499182325558210069169000427797017339738), (5405147053590199906267148395735118613336414351018530735722720040827727097972920486594543311426345392349086385549839048566084707843112026243349939299024319, 8002769171861885178396463644984886400156672146077952032015400134129488015068209859100426058398177350596683257408001283985805200067612699332474467674680473), (6697219294676538369600190561051536551200802849475300417346938525942877694585071102972050747762506408872812616907886663538725965035893639948098517281699107, 4264453205762791425759087098542100978295589303749352940878408790131102992049463145753330677529440546449802160982522379660906512593991508766161744141762197), (9067912308373050627706755466306176198094458282165857662530046587211061425982589162739214052430234487825412734501874033356323521552777855899079989661462880, 7016472566014270602188623441746330303647882560961379783294186639916573881062877982777005181798334745275710506940676537452535289304763418648146105619474415), (4346870412521505185891951079060048697471265629222762972741874808938733672291627532024630774358183511551475921933022591014969867436447511411590872802195000, 3334316856949910844732387203755890507932125879762514357944667600393727742804560752263443905356167755656540586543916596789959062183315292517427905266415992), (8308089262199373464984371306055350144844283616686160423641070708956956653178101326963883063309578461861915427383315006239822281216646316876730624190024651, 4274017100823496048323152446573197490041024290994938568019290774440648728190153413861398283337183784833712828566103197798028229634180071648287252778245445), (7198319673558231935729586790935574131548526053778718815649777229221430683303498069408857941615004080713867284218385219324376934624764968835753436744350809, 3669298783619181330901618965995167311660502490447749514631526082232712912624342302912640384293528279357625525290984840977073283082796747379425497661295862), (534790943676452586550668735647196259574055469914817773874627430703253150084805317781760364408438746082793211488761595311609882527586651011358154609480600, 838944858970730485376141336424073855283625872492082245197034104289577183419820396552972640979483431616064236719013555439822271337762625723005650119186609), (1575800862818998014280222557310191689453130920405332690869200512795696331715618377816665306816389746580098148649320421623623893486622140696373734577127319, 8486921868517105738014766807418256836912326493248915129387345015430571853804000879755500890333617210998945474221658917032533852018524848602644230824256799), (2136001150892561630330242126590154244058433369002908338579215911656527826124779159704287478468958555669646474273075699128040732423430554609689914299840178, 1182755407102440837613905085880077744732732899499917461495406997510652386190076052736967598690784969052598295330839520753602327677143262821884697657619349), (2525207036323039221257556511742973405060948929362848499928432416802792336611142200369643255949438199561604420755600168837489834838844870747569665036257723, 7415400527314157558476460526351487957911059069928610882776808541966220446874149122463474406086692581712209555969541480180653029202110037482312588482441161), (5960560514876825357560025410485420552108771484736859021751882944197088005126637484133796221979011305853031771616655376240296966829850418321911824474870050, 554154189469023347449478958217052729935042963370152396186111719978824028999631484874831458665337019150749092642139036335885228219429233409483918997954897), (8678534350628540461029525816915060876238509725840742987414010043662704587321705506385477520087065708922704381222356230190905402291507107618792466152903017, 6361812358049765050022855736917163434602933031065263099938475948184481560355018886195232309329976609064531748803527967602712852923075925483332103270433733), (816795745324505977857035391854017309202434060256637702374212725231730513635122550478995595568687619563222148764206453763926504736646797952540336859251915, 9112580217366441422299281073702897196632509330464603342594305392931984736736414793122617261691503084308213629301465666796386968143270529891557639801395238), (7206862696390761007504286633873133698463592733159325465992517101970572911406350195731054229737770816334537111299660288172906458192476808242761369429208979, 6079808799056917977119494411383676220765195723904415727259401555394700288600047959536210313991123342196566976411917220549888801363586782715943631564844186), (2866542492466939937310577736140216831539477499202943737233401622016388480503041536848159029438556989113443973099843789147813112890878980000906015963301520, 6005867654051456952749765574405639259963088704979327905796238525911219193001517541013267942746935026852416419803718015089207184938284465206529634657349907), (4634323065762529412330095597839517864517951163647002499418132136212823518841088594404455599561030794634051723845361877423304205196255695871494928456299661, 1937417822207801365976981181314895070035676426208740049915464524614928522478828871313576391991125950683515524064147786701498185539348724184269276680535061), (2091784577415836718035585981629640335842443810332504474343902351685574049359045820303845678030710833932691885094347745047631425682741332411947141571350170, 5261605713980099940225975728376351425562463082375691381360662004211085515185965344645096892774661627921013230574067010147344564790542580291157005515998647), (1783708544017216267612743383915723171100809090287122502116529318007901788949154718442345019440128775416710741738867818702239292351495214292349729061653283, 1664709140995267732270136066266391755720970012011444988994690068439754249570829448009053215277335527604153538889636217612179923864142909203603503434532699), (2626618642984778278189428203391363851107764417835667874969064334210116982318244236314811262701924330926761330203819023060980307609868084034420068072409911, 8509640477338475092172667241774505772359752050580289828593047443268445555986637604033748359187732635981378597494261161227242762624757625512402624014103965), (198087587305667482784444088350018082424510144340275565426172682117498176079780401403565099235056197004972238783265007648714466026247078747839468508775271, 2910286801633056634762908869224995574226331916971267980352624320196630725584890841807241751917959344102248036014376468501332208724114970289391061204422169), (1479169496794182179409169790654142659167574696773254599443393208677746766744966579414189036866940942920726824079817652591553757828118177228641597317694710, 8533825773525988193773633439761918814376354186274860776950167335073239574463606160891459511537910824687669988808960892875837295204196280651240297998810137), (932897221249047103675515708089642868350218197339682592477965616786012758665990241817654920684189656065991020658482660493162274338657607133450723574497903, 6813046077654741386102328994721391143316281188410789631427695345205077626882101134754160717708346920983017704203641704851731883748701610862842777097425057), (1319465155123770856685595428807814063056344112401851086374463226250486099498358238308395244352367207517766025662090101041156262441260708398722465885819406, 7482704918584302315559287754681190426165283522922798321434959791317510050822965951152023083480212456626057169862140337686529422991488015303680268303399003), (7021633570942521690602022009141290912547807261145068678528147871557436730953815060953222742846872745777109224613012277381105475318149883628581151460618076, 5711707363228041613189243850179421286914564622750934355808864778212105716358402952360990558384916487723068332280083428050253346226930852949021488419952308), (7564715902931241420901196019039394921520181530625676147510524882850830303905732221197918789206946090202201482282990490777593840906870583872559432736121028, 8034308735664917033516607335772057390759322593604175050525408748818397545947061121057792777809404743352245469812717325459234596057029712853818463987898459)])

数学符号表达

初始化变量
- $m$ ：消息转换为整数。
- $p$ ：一个 $n\text{bit}$ 位的质数。
- $e$ ：随机整数，满足 $1 \leq e < p$ 。
- $t$ ：随机整数，表示多项式的项数（ $1 \leq t < n\text{bit}$ ）。
构建多项式
- 系数向量 $C = [c_0, c_1, \ldots, c_{t-1}]$ ，其中 $c_{t-1} = m^e \mod p$ ，其余 $c_i$ 是在 $[0, p-1]$ 范围内随机选择的。
- 多项式 $f(x) = c_0 \cdot x^{t-1} + c_1 \cdot x^{t-2} + \ldots + c_{t-2} \cdot x + c_{t-1}$ 。
生成多项式值点
- 随机选择 $t$ 个 $x$ 值 $a_i$ ，每个 $a_i$ 都在 $[1, p-1]$ 范围内。
- 对于每个 $a_i$ ，计算 $f(a_i)$ 。

加密过程输出为 $(e, p, \text{PT})$ ，其中 $\text{PT}$ 是点 $(a_i, f(a_i))$ 的列表。

恢复flag

加密方案通过一个随机生成的多项式隐藏消息。恢复出 flag 需要从多项式的值点 (a_i, f(a_i)) 中恢复原始多项式 $f(x)$ ，提取类似 RSA 的解密最后的系数 $c_{t-1}$ ，这实质上是 $m^e \mod p$ 。恢复多项式可以使用拉格朗日插值法或者其他多项式插值方法

使用拉格朗日插值：
- 对于多项式 $f(x)$ 由其在 $t$ 个点的值完全确定，若 $t$ 等于多项式的次数加一，可以使用拉格朗日插值公式恢复多项式：
$f(x) = \sum_{i=0}^{t-1} f(a_i) \cdot l_i(x)$

其中 $l_i(x)$ 是拉格朗日基多项式：

$l_i(x) = \prod_{j \neq i} \frac{x - a_j}{a_i - a_j}$
从多项式中提取 $m$ ：
- 提取系数 $c_{t-1}$ ，并尝试解决 $m^e \equiv c_{t-1} \pmod{p}$ 来获取 $m$
求 $m$ ：
- 使用扩展欧几里得算法或模逆求解 $m$ 。如果 $e$ 和 $p-1$ 互质，可以计算 $e$ 的模逆。然而题目这里并不互质，且 $phi$ 不被 $e$ 整除，所以需要先找到 $t = \gcd(e, p-1)$ ，然后计算 $d = e / t$ 的模逆。RSA 解密的数学表达由 $m = c^d \mod p$ 变为 $m^t = c \mod p$ 。接着用新计算出的 $d$ 计算 $m^t$ ，再求出模 $p$ 的 $t$ 次根，即可得到 $m$

Exploit

SageMath's Code

#!/usr/bin/env sage

from sage.all import *

e, p, PT = enc


def recover_message(e, p, PT):
    # 拉格朗日插值重建多项式 f(x)
    R = PolynomialRing(GF(p), 'x')
    x = R.gen()
    
    # PT 是点集 (a, f(a))
    lagrange_poly = sum((y * prod((x - aj) / (ai - aj) for aj, _ in PT if aj != ai) for ai, y in PT))
    
    # 拉格朗日多项式可能需要通过 simplify 或者 expand 来转换为标准形式
    f = R(lagrange_poly)  # 确保多项式在正确的环中
    
    # 获取多项式最后一个系数，即 c_{t-1}
    coeffs = f.coefficients()
    if len(coeffs) == 0:
        raise ValueError("No coefficients in the polynomial. Something went wrong.")
    
    print(f'f: {f}')
    c_t_minus_1 = coeffs[-1]  # 不太对, 输出多项式后手动选择
    # 输出后密文为
    c_t_minus_1 = 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466
    
    print("c_{t-1}:", c_t_minus_1)
    # 解决 m^e ≡ c_{t-1} (mod p)
    # 这里我们尝试寻找 m 的 e-th 根 | 但 e 和 p-1 不互质 | 见下面的解决方案
    m = power_mod(c_t_minus_1, inverse_mod(e, p-1), p)
    
    # 将 m 转换回字节字符串
    flag = long_to_bytes(m)
    return flag

flag = recover_message(e, p, PT)
print("Recovered flag:", flag)

# 解决不互素 m^e ≡ c_{t-1} (mod p)
from Crypto.Util.number import long_to_bytes
e = 3316473234742974510609176519968107496789324827839883341690084725836178910956015867823194881383215644380418162164089588828798132617649547462723383625707014
p = 9486915681801496583557174944405629563403346572353787092582704754226121096049954529719556720667960706741084895049852989479773192757968901195529919070579679
c = 7578451683223886721897751965012512970186814199061886859082385728532294810974986601048390882041773215459258245487361965408708218417206386123135513829067466

phi = (p - 1)

# check phi是e的整数倍 
print(f'[?] check {phi / e}')  # 2.8605434177540494 | 并非整数倍
t = GCD(e, phi)  # 2
print(f'[+] e / t = {e / t}')
# print(GCD(e // t, phi))  # 1
d = inverse_mod(e // t, phi)
m = pow(c, d, p)
# 有限域开方 | 求二次剩余
ans = Mod(m, p).nth_root(2, all=True)
for i in ans:
    print(long_to_bytes(int(i)))

Output

[?] check 4743457840900748291778587472202814781701673286176893546291352377113060548024977264859778360333980353370542447524926494739886596378984450597764959535289839/1658236617371487255304588259984053748394662413919941670845042362918089455478007933911597440691607822190209081082044794414399066308824773731361691812853507
[+] e / t = 1658236617371487255304588259984053748394662413919941670845042362918089455478007933911597440691607822190209081082044794414399066308824773731361691812853507
b'CCTF{SSS_iZ_4n_3fF!ciEn7_5ecr3T_ShArIn9_alGorItHm!}'
b'\xb5#\x13\xf1\xe9\xf9)n\'XVU\xc3g4\x95\x94&X\xeb\xa90F~\xdc\xcd9W\xde\x9c\x90\x8d\xf5hn\xdc\x92|+\xcf0\x04\x82\xa6\x0f?3"\xeft\x0f=\x8b\x84\xe9\x8b\xf7\x07\xc5\xaa\xe5\xb0\x8ab'
"""

LOV3 -> OV3