from hashlib import sha256

from Crypto.Util.number import inverse, getPrime

from tqdm import tqdm

'''

import itertools

def small_roots(f, bounds, m=1, d=None):

    if not d:

        d = f.degree()

    R = f.base_ring()

    N = R.cardinality()

    f /= f.coefficients().pop(0)

    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())

    for i in range(m + 1):

        base = N ^ (m - i) * f ^ i

        for shifts in itertools.product(range(d), repeat=f.nvariables()):

            g = base * prod(map(power, f.variables(), shifts))

            G.append(g)

    B, monomials = G.coefficient_matrix()

    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]

    for i, factor in enumerate(factors):

        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)

    for i, factor in enumerate(factors):

        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))

    for h in filter(None, B * monomials):

        H.append(h)

        I = H.ideal()

        if I.dimension() == -1:

            H.pop()

        elif I.dimension() == 0:

            roots = []

            for root in I.variety(ring=ZZ):

                root = tuple(R(root[var]) for var in f.variables())

                roots.append(root)

            return roots

    return []

from Crypto.Util.number import long_to_bytes

a = 68823589009570846705623113091430161477799561031575612135516351257937127579444

b = 76549169049080319489163980188997771079750670038002598167961495813084486794567

c = 99215492498952976642031024510129092308042391285395704888838178561670205468882

p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

Fp=Zmod(p)

x_=[664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507,269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352]

PR.<t> = PolynomialRing(Fp)

f = a*t*t+b*t+c

PR.<k0, k1> = PolynomialRing(Fp)

s = f(x_[0]*2^64 + k0)-x_[1]*2^64-k1

roots = small_roots(s, (2^146,2^146),m=3,d=6) 

x=12256129447040382014545559694380637404973427806615255879415755813326872746484293878302279841562237263671079585622657761243463788893311797799201976142603511

s=f(x0)-x

s.roots()

'''

class my_LCG:

    def __init__(self):

        self.a = 68823589009570846705623113091430161477799561031575612135516351257937127579444

        self.b = 76549169049080319489163980188997771079750670038002598167961495813084486794567

        self.c = 99215492498952976642031024510129092308042391285395704888838178561670205468882

        self.p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

        self.seed = 93161902675685857786932571331038018595140621249413834179036444009740278201203

    def next(self):

        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p

        return self.seed >> 64

    def output(self):

        print("a =", self.a)

        print("b =", self.b)

        print("c =", self.c)

        print("p =", self.p)

seed = 93161902675685857786932571331038018595140621249413834179036444009740278201203

cipher = [104612880565354761070267231258959974017713136013091552542621012009434344223091,

          75867315122609665862412321569592448016548595925558860261941234225747875658355,

          106901597652387441116797426235259979167755542628252028460970918870852084813985,

          22282265919236743389726915885827434932651977730848876965702592028838506934802,

          113663688553403244683128957504190135685760214545373190153400188368329624810824,

          16387987427743919688629484112748920627537972533590712542304182257404148095432,

          42660781848852863873070244368035358673436082124276647936063403560054320824947,

          31162780219880567100421404229662317404195331726681121575505050872412728752846,

          4387263209760294127327273998365291139136756172378440265726369942465661809226,

          9486548512905762310741629559650376499881990751841396019470492813536817972788,

          48175096956218645396129797881617184816956038092368660196837813749510220209020,

          44832999096333655680734980423005605365074861714291594434259782779054037518357,

          91949111038768792853022977677056688517414191501656202462769670180011454736134,

          84362160451115508526234487916725793664590119636637539810168371139175756722218,

          37991151261861388606427583658548923882501719664397171054526120281654768250027,

          76502569176155441262877857713986290804857527394931115027371407239085302418015,

          69004590108972326779999503375035935629144187797049165946644383062664912505793,

          4882509736578426220928083701456224217596136409513934115208162112269124095036,

          43923135793747042362291047632803354256532285967402459802384563909906286571537,

          60099118217689452210082521471087211926434931778809056323284225098458442535387,

          41772186654628607473153061053630877342481864865985327695842922897386493117840,

          79556569085671906788310296380605892417410665990711208999213184300355584627493,

          113368724525353223298893326950045576507359981373213697703045622403941359594816,

          59568498228965811827206375159844085215141410061444029744235874177744506595963,

          5813871055160958965491186951684884799390692165774935048726620511285107065171,

          101481471612354001038968281423076176339698400003836978206153754002016784653117,

          96713934756979037100616702408060142461624534046186352589457317850269578096978,

          50360544372106359495068645870868114000049436655822775857718387298804448386259,

          74343018392522018803983491192044402773734077434586754153316411931268932053849,

          85064649783728020457864819723803995069342386266325766064354175704654032312470,

          35444692928369969109775411420972206587166544062593932622816977149910920025593,

          88364976585873094910882074779610461514853793492269703066264952338524869329015,

          57171789241051208558861663926443006215165105080980300229007074324952708746414,

          53398702677161874182117493992247921340773468735882139055903326524685751323223,

          22084022599630141597766375557874162908749682780683228274573161676243137075985,

          67811375554342446963928136891489894009025011339123405492350978811178609371520,

          54279152372926754185972096972067394007518618911313269898203907795172124806761,

          71337965908378379886587542454943435140109212437982933800558803691194797247858,

          91631795365993438211094618411930046881699597378889861280702841447103987549686,

          55725715889928044127700572038972949057067144434626788557169321659022938298621,

          68379770126152524442093415542514227284857840135092144556912468864495685413179,

          40664875356285535027116296315063139118439996515430069978781752466656941376294]

lcg = my_LCG()

print(lcg.next())

print(lcg.next())

import string

table = string.printable

for i in cipher:

    x=lcg.next()

    for j in table:

        tmp = int(sha256(j.encode()).hexdigest(), 16)

        if (pow(tmp, 3, seed) ^ (x >> 192) )== i:

            print(j, end='')

            break