import os
from Crypto.Util.number import *
import hashlib
from secret import flag

assert hashlib.sha256(flag).hexdigest() == "1b6208006b19ceddc493a8fe1342c1c7bba1800b2a66b9da4cd819f8440f331f"
assert len(flag) == 40


class LFSR:
    def __init__(self, n, key, mask):
        self.state = key
        self.mask = mask
        self.n = n
        self.state = [int(b) for b in bin(self.state)[2:].zfill(n)]
        self.mask_bits = [int(b) for b in bin(self.mask)[2:].zfill(n)]

    def update(self):
        s = sum([self.state[i] * self.mask_bits[i] for i in range(self.n)]) & 1
        self.state = self.state[1:] + [s]

    def __call__(self):
        self.update()
        b = self.state[-1]
        return b


class LCG:
    def __init__(self, seed):
        self.seed = seed
        self.a = 47026247687942121848144207491837523525
        self.b = 117397592171526113268558934119004209487
        self.m = 2**128

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


def f(alist, seed):
    R = LCG(seed)
    l = len(alist)
    res = 0
    for _ in range(30):
        index = R.next() % l
        res ^= alist[index]
        res &= alist[(index + 1) % l]
        res |= alist[(index - 1) % l]
    return res


def pad(m):
    return m * 25 + os.urandom(2000 - len(m) * 25)


XOR = lambda s1, s2: bytes([x1 ^ x2 for x1, x2 in zip(s1, s2)])


seed = getRandomRange(1, 2**128)
R = LCG(seed)
bit = 64
t = 8
mask = [R.next() for _ in range(t)]
seed = [getRandomNBitInteger(bit) for _ in range(t)]
lfsr = [LFSR(bit, seed[i], mask[i]) for i in range(t)]
output = 0
for i in range(2000 * 8):
    output <<= 1
    output += f([lfsr[i]() for i in range(t)], seed)
flag = pad(flag)
print(f"mask = {mask[-4:]}")
print(f"enc = {XOR(flag, long_to_bytes(output))}")
print(f"hint = {flag[-100:]}")
"""
mask = [14220691401612821285, 6144765487634854340, 15963296602901011718, 11570958398098493701]
enc = b'\xfa\xb2G\xb0\xccYU\x16\t\xbe)\xdc\x19\x1f\x16x\x98D\xdf+\x95\x0b\xeeL\xca\x07[\x1fM\x04T\xd3V\x11\x19\xe3\x8a\x8f\\\xfflda\x7f/B\xae\x85E!\xc4\x17M\xd7\xd3\x9e\xbc\xb2\xfc\x97\xe1W\x83\xdd\xdcR\xcfh\xd0\xd4D\xc5\x949M\xa1\xff\xe1\x9fd\x89\xa85\xff\x85{;:\x9e\x91G\x11o\xc4%\xe9\xb2\x1e\x8e\x9as\xbb<\xbb8z\xae\x15\xac\xea"x:\x81\xe7\xda\xd1\x8fv\xd7\x92\x85\x953AH\xd7CAkBU-\x97\xce\xe0\x11\xbe\xa7\xc6\x7f\x1d\xedgL\xc7B\xfa\x82P\xf1\xeb\xd6#B\xdd\xce=\xae\xaf\x92}A\xed\x99\xec\xa3k\xff|r\xec9d\xa3\x17\x92\xd2\r[o*\x8e\x95\x1b\xecj\xf8\xb2WF\x01\x05ia^\x7f\xa1n\xab\x12\x84\xddo\xd5\x82\xdeJ\xde\xaeX\x83\xd4\xaa\xc3\xbb:\x92\xce\x15\x85f\x06F\xc5\x04\x0c>\xa7\xca^\xf0\x01\x1dG\x12\xbc|\xa5_\x8c\xa3\xb6\x8dj$\xd1\xbet\x8c\x05\x0f\xcc\x01\xf4\n\xeb\xcdb(+\xcf\xc8\x99\x9b\xd0\x0c1\x9c\xa0s\xf3\x93/\xabU{;jbC\xd4\xfa\x92\x83\xcd\x8cb8\xb4\x80\xed\x0600~\x1f\xa8\x1a8\xc42\xd4\xdb\x07+\xa1M\xf6 E\xb1+\xa2R\x81\x91\xd8\xb4\x15&\xbc\xa0\xbd\x87<\xb5\x8d\x9f\x9e\xb1\xb6\xea\xf2\x99w|C^\xa3\xc36BZ\xe1\xe6R|\x18\x9f\xcd\xc3`\x86\n\x13^\x95\x82\xc0P\x11l\x0fY\xd3\x9a\xcc\xef\xd9\x8d]\xa1"}\x89\xd1\x98\t\xc8\xa9/\x1f\xcb\xae\xe9\x936\xd8\x9d\x8d\xed\xb6\xe7d\xe4\xd2\x12\x84\x0cx\x15\xa0K\xc6\t\x1a\x10\xcc\x92\xf3\x95r\xe1\x89\xec\x0eE\x8f\xf9i\x1b\x0b\xa3\xc0I\x99\x81\x05[\x86\xba\xbd\xd9\x16^\x86\xd9\xbc\x86\xe1{\xcd6j\x93\x9d\xe2\xf2\x121<7x\xb1\xb6j\x8cG+\xf2\x0e6\x02Y\xe1\xc8\xa1\x14=Y\xaaUMJ\xec$\xda\xe4N\xd5\xe1i\x03\xe5\xd0w\xb9\xdf|A\xb0\xe4\xa9\xcao\x06[\xc1\x1e~\x1c\x9dx\x97\xbcVoD\xfd\x80\x1b\x96\x1e=\xb7\xf8)\xbe\xbaQ\xbb]\x17\x86\xd18\x18?\x0e\x03\x1f-\xf5\xe0\xe0\xa1\xfbBB$\x0f\xa6\x84O5\x962\xb0\xf1\xb8K\x0c\x83\x15p_\xde\xe6\x05\xb0\xff\x8f\xd2\x7f\xba\xea\x80V\xda\r2j\xd0G\x95?\x18G\xf6\xb5\xc05\xa6\xed\xcd%)\x0f!\xf2\x95\xd7L\x17PX\x07:\x8c\xbb_4\xc9\xef\rw\xda\xdf1\xa5\x805{\x0c\xe0s\x15\xc0/\x83?\xb48\xc1\x0c\xdaW\xddJ\x8d\x8e\x9f\xacx\x11\xf5H\x91\x8b\xec\xcc\xa7\xee\x81\xdf\xdfuBV\x98\xcd}\xcf\xa2\xe5\xf8\xac\xa3\xff\x1d\x90;\xe3\x1dQ\xe4\xaaI\xb0\x9f\xc4\x1d^\xca\x91\xdb\xaf\xfc\xa0\xaa\xc7\x8d\xaa\xe0\xd3\x98\x9c\xba\x9a\xc2\xfb\x96}\xf5\xf3F\xc1\x0e\x9d\xe9i@L\x82\x9c\x9a{\xf0\xe7\xc0yb\x1f,\x92\x81\xa0\x96\xe7\x16o`\x1fQ\xf5\x7f[\x18n\x83]\xdd\xb1Zl\t\xf3\x8f\xd3)J\xaaW\x87\xbf~\x0c\xddX\xad\x10\xfe}DW[\x15\x9a\x81Z\xf0\x9b#\xcd\xc5\xbb\x9c\xad\x86\xc5\xa9,\'-\x0c\xf5w\xd1\x93\xdc\xacKT\xa1\x85\xf6lF\x92l2PI\xdb\xcd\x16\x9a\x1f\xd4\x1d0\n\xb7\x14 \x95\xc7{\'B\xa0\xb8:\xb6\xbe\xc0\xf8\x8a\xe8<O\xaf\xc9FI\xfb\xfd\xf6\xf3v\xac\xea\xd6\xb4spk\xe1\xaa\xe3(\xaa\xd3q\xe5\xca\x9c\xc0R\xb8\xddk6P\xe71\xc2\x8dH\x9b\x0c\x85\xf6z\x1c\x88V\x88\xd2N}\x8a:\x1d/%j\x10\x82j\x141\x01\x9a\xbbr\xa1\x9c8\xb0\xea\xd5\xb67\xef\xc2\x171\xe8!p\x93\x05\x18\x9e\xb3\x07@\x1cY\x9f\xb9\x13\xf3~5\x9d\x10\xa2q\xf9\xf0)%\xbcZ8*\x86\xe4\x12D<\xd3c\x94s\xe4\xc1yr\x02\xc06a\xea\xc7\xc0\xc0\xa1\x8d\x05"] \x127X\xf5\x9bn~\xf6\x85\x93\xf1W\xbc\x94%\xc0\rt\xee6C\xa2\xd6\xf3\xcc\t\xc5\xe8\x8cV,\xb2A;\x9e\xd3\x9c\x1c\xc4\xffE\xec\x15\xb0E\xfb\x18\xab8;\xfa\x00\x84\xf5=\xf6\xd2\tu/\xc1\x8aW\xbb{\xdc\x98\x9e\xecS\xdcOPKq/\x9c\x86\x15h\x0b\x00\xea\x94\xe5\xb4\xe5ip4\x8e8{`\x81\xd9\xee\x19`9\xbf47\x1f\xb5\x05\xe6\xc7\xb9I\x1bM^\xd9\x83\x00\xb4\x0b3\\~\x04;\x1d\xf8\xe0}q\xf4\x94\xad/@b\xde@\xd0\xb7bR\xb84\x9a3\x0f\xba\x90\xd0\x8e\xa0\x022 \xca\xe2\x89\x07qE+#~\xfb<\x90O\x04\xbc\xdb\x7f\t<$\x87\xcf\xc8\xe5\xb7\\\x81\x07\xae\xc7\x84\xbb\xdbV\x17\xc5\xfb\x1a\xe0L\xe9A\xbcy\xc8\xc5\xf7\r>a\x9c\xbc\xad\x18,\xf8\x8ch\xf7\xd6\xb0\xc0\x1e\xbb}\xffr\xae\xcf\xae!\xc7\\\xc6\xd8\xbf\x81\xef\x04\xd9awf\xda\'vh\xeb\xd5\xac\x1c\xe5)PJ\x9f\x02\x1f\xba\x03\xc0\x073\xb8K\xe6A\xc8t\xabjA\xbd\xff\x9e\x81\xfa@\x86H\xa8\xb8\xf5\xbb\xc4\xb9\xe8\x9f \x14\xbcL\x08r\xca\xc8\xfe\xf6k\x18;\xdf\xd6)#\x02X&\x0e|\x03\x85H\xc4\x0c\x81G\x04P\x05h\xaeI*\xd0\x88&|\xf8\x02>\xe1I\x80cF z\xf0yL\x10%\xd1\xa7Wb\x064\xf8\x05[eBwp\x15\xa4c`\x8aL\xba\xb4\xd1\x9c\xce\xd4\xb8\xd0\x18\xf3?b^,\xed\xb8_\x8fp\xa07\xbb\xba \x08\x9c\xf1\xac\x03\xe8\xd5\x05\x83\xf1\xbb\x1c\xcd\x9aF\xc7\x10\xa8\xd9\xdf\x05\xee\xca<\xf4)\x82\xa7\xe8C9\x0c~6\x8e{\xf3\x80\x0c\xbe\x13 \xf6\xfa\x7f\xec\x08\x929\x92\xcd\xd4GT\xbde\xda\x9fSk\xf6\r\x00W\r}\x99(IG\xd5\x0c\xd0\xdcj{r|\x81\t\x9f\x8f\x1f\x0ee^\xcb*<\xbb\x993\x8f\x07\xc2\xa1`\xe2W>\x84c\x00\xa7a\xe2\xdb\xbd\xe2\xb7\x87/2ugj:[\xdd\xa8\x8c\xcc\xe5\xde\xbd\xe39UW\xcc\x9b\xc7\xbb\x88H\xdb N\xeb\xa8xo\x84)\xc2\xa0$\xfe\x90T\xb9rxNDT\x13\xb7\x97\x81^g\xbdU\x89\xfd\x89r\x03U\xf7\x07\xe2gd\x0e\xe5O\xb6,\xcf\xb5+\x00\xca\x93@\rK\xfe=\xca\xbb\x12\x83\x9a)\xfd\xda\xd1\xa95\x9eyw\xaa\xb8^`2wWF\xf3\x7f\xb0b\x83\xa4\'@%f\x8f\xa5J\x1frA\xfb\xb6p\xaf\xe1\x8d\xba\xb2\xff\x9a\xeb\x14%\x10\x89,\xc6\xa2>\xf9m\xb2T\xee\xb4\x98\x04\xde\xf3%o\xd7\x80P\x08\xc2\x00^a\xa3\xe4\xadZ\x90\xad\xc6\xb2\xbd\x04^\x13^\x82\x12\x14\x96\xce+0/\x92U\xfc\xf6A[\xdd\xc3\x8cr\xa8l\x1a\x95\x03Wm\xdeD!\\\xc9\x98\xd3\xea\x90\x8bR\xfe\xf2\x10+\xe1\x8f\xde\x18\xe1\xbb\x0bh\x1c\x0e\xdb\x1ea\xc6\\?\xd2\x8b\xc4c\x84\x7f\x9a_\xe2\xd2\xc84\xaej\x85\x10\x10\xc7d,8\x0b\x89^\x18\x8f\xd6G\xa1p\x83n\xb7^\x14\xcd\x18\x8b\xe6\x9d\x00s\xcb\x02\xc1\xee<\xa2F\xb4\xa99]+\x0b\x1a\xed\xdae\xe3\xd3\x82\x19\x02\x80k-\xc8\xa7\x9c\x9d\x92\xc8\xefr\'\xfds\x9a\xa5\xe8\xd4\tS\xb0\xa0\xbd*\xfc=\xf6\xd4e\xb3\x80\x8c\x0e\xb9_]\xd6\xc2d\xa6\x19\xd5\x90\x0b\x9e3\xb3\xf1\xee\xb0w\xce\xa3&\xd0\xae\xaa+C\x05\xb2 \xf5\xccf\x90\x1d\xb3$\xe5\xbc\x07\xe0\xb4\xc8\xb6~\x00\x9e\x84Z\xf9\xb7\xe1\xdaB=i\x9d\x19\xa4oJ,\xe7\xe4 \'#f\x91vB\xf8\xe2\x0e9\x84\xe7\xf1\xde\xd0+\xa2\x11\x96.\xfd\x8c\xba[jEAM<\x03\x12U\x84\xab{2\x81H\x066\x01\\\x96\x99\xfa\x19\xd0\xb2\xe5\xf9\xb6,+\x97)\xb7h\xd2@\xda\x89_\xd6S\x8f@%q\xb5$\xc7\x89\xb7\xe2\xf8\xb1\xa5\xc8|\x83\xce\xe7\x88\xb8\xb1\xdd\xa5J\xcar\xcd\x8f\xfe\t\x85\xd0\xb4FC#(\x85-\xf6fm5\xecUWE \xd4\x0b}\xc0\x9d\x1c\x14\x83\xfc^5\ng\x7f\x13\xfe{[\x8b\xbc?\xc2+\xfb\xa8O\x8b\xf6e\x91vG\xffd\xdf\x0c\x84Ig&\x1b\xbb\xcb\x84;\x94\x13\\\xcc\x178\xa1\xbd\x08.'
hint = b'\x93+\xc6\\$s\x16Sp\xf24\x91wPg<BS=\x9e\xe4\xce\xdb\xa3N\xe6\xe1/\x17\xfa`9\x8f\xe33\x92\x80\xa6@\xd6P\xb0\xdb\x8eJmD\xf1\x10Y^c4\xd0\x86N\x8an0\xf4\xe3\x8b\xbd\xdff\xb6%H\xd3\x85\xf3`\xbc\n\x02\xa21_\x82U\xa7\t,\xaf\x9e\x9cn\x88\x92\xadi\xab\x19@Wa\xe6\x1e\xf9\x9e'
"""