糖醋小鸡块的blog
0%

2024-VNCTF-wp-crypto

发表于 更新于 分类于 Valine：

运气还不错，做出了所有crypto方向的题目，在这里记录一下题解。

image-20240217200300703

SignAhead

题目描述：

1
试试伪造token和md5签名！

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from hashlib import md5
from secret import flag
from secrets import token_bytes


ROUNDS = 100

successful_forge = 0

for i in range(ROUNDS):
    print(f'Round {i}')

    key = token_bytes(32)

    msg = token_bytes(64)

    sign = md5(key + msg).hexdigest()

    print('msg:', msg.hex())
    print('sign:', sign)

    print('FORGE ME!!!!')
    
    newmsg = bytes.fromhex(input('msg: '))
    newsign = input('sign: ').strip()

    assert msg != newmsg

    if md5(key + newmsg).hexdigest() == newsign:
        print('GREAT JOB')
        successful_forge += 1
    else:
        print('you failed!')

if successful_forge == ROUNDS:
    print('Here is your reward:', flag)
else:
    print('try harder next time !')

看得出来是很经典的md5哈希长度扩展攻击，直接随便找了个脚本来用就能出。详细原理及代码可以参考：

MD5哈希碰撞之哈希长度拓展攻击 - 知乎 (zhihu.com)

因为赛前的确只是听说，没仔细了解过原理，所以先直接当次脚本小子。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import math
from typing import Any, Dict, List
from pwn import *
from Crypto.Util.number import *

rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                  5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
                  4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                  6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]

constants = [int(abs(math.sin(i + 1)) * 2 ** 32) & 0xFFFFFFFF for i in range(64)]

functions = 16 * [lambda b, c, d: (b & c) | (~b & d)] + \
            16 * [lambda b, c, d: (d & b) | (~d & c)] + \
            16 * [lambda b, c, d: b ^ c ^ d] + \
            16 * [lambda b, c, d: c ^ (b | ~d)]

index_functions = 16 * [lambda i: i] + \
                  16 * [lambda i: (5 * i + 1) % 16] + \
                  16 * [lambda i: (3 * i + 5) % 16] + \
                  16 * [lambda i: (7 * i) % 16]


def get_init_values(A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> List[int]:
    return [A, B, C, D]


def left_rotate(x, amount):
    x &= 0xFFFFFFFF
    return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF


def padding_message(msg: bytes) -> bytes:
    """
    在MD5算法中，首先需要对输入信息进行填充，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。
    因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。
    填充的方法如下：
        1) 在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。
        2) 在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。
    经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
    """
    orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
    msg += bytes([0x80])
    while len(msg) % 64 != 56:
        msg += bytes([0x00])
    msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
    return msg


def md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> int:
    message = padding_message(message)
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def md5_to_hex(digest: int) -> str:
    raw = digest.to_bytes(16, byteorder = 'little')
    return '{:032x}'.format(int.from_bytes(raw, byteorder = 'big'))


def get_md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> str:
    return md5_to_hex(md5(message, A, B, C, D))


def md5_attack(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe,
               D: int = 0x10325476) -> int:
    hash_pieces = get_init_values(A, B, C, D)[:]
    for chunk_ofst in range(0, len(message), 64):
        a, b, c, d = hash_pieces
        chunk = message[chunk_ofst:chunk_ofst + 64]
        for i in range(64):
            f = functions[i](b, c, d)
            g = index_functions[i](i)
            to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
            new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
            a, b, c, d = d, new_b, b, c
        for i, val in enumerate([a, b, c, d]):
            hash_pieces[i] += val
            hash_pieces[i] &= 0xFFFFFFFF
    
    return sum(x << (32 * i) for i, x in enumerate(hash_pieces))


def get_init_values_from_hash_str(real_hash: str) -> List[int]:
    """
    
    Args:
        real_hash: 真实的hash结算结果

    Returns: 哈希初始化值[A, B, C, D]

    """
    str_list: List[str] = [real_hash[i * 8:(i + 1) * 8] for i in range(4)]
    # 先按照小端字节序将十六进制字符串转换成整数，然后按照大端字节序重新读取这个数字
    return [int.from_bytes(int('0x' + s, 16).to_bytes(4, byteorder = 'little'), byteorder = 'big') for s in str_list]


def get_md5_attack_materials(origin_msg: bytes, key_len: int, real_hash: str, append_data: bytes) -> Dict[str, Any]:
    """
    
    Args:
        origin_msg: 原始的消息字节流
        key_len: 原始密钥（盐）的长度
        real_hash: 计算出的真实的hash值
        append_data: 需要添加的攻击数据

    Returns: 发起攻击需要的物料信息
        {
            'attack_fake_msg': bytes([...]),
            'attack_hash_value': str(a1b2c3d4...)
        }

    """
    init_values = get_init_values_from_hash_str(real_hash)
    # print(['{:08x}'.format(x) for x in init_values])
    # 只知道key的长度，不知道key的具体内容时，任意填充key的内容
    fake_key: bytes = bytes([0xff for _ in range(key_len)])
    # 计算出加了append_data后的真实填充数据
    finally_padded_attack_data = padding_message(padding_message(fake_key + origin_msg) + append_data)
    # 攻击者提前计算添加了攻击数据的哈希
    attack_hash_value = md5_to_hex(md5_attack(finally_padded_attack_data[len(padding_message(fake_key + origin_msg)):],
                                              A = init_values[0],
                                              B = init_values[1],
                                              C = init_values[2],
                                              D = init_values[3]))
    fake_padding_data = padding_message(fake_key + origin_msg)[len(fake_key + origin_msg):]
    attack_fake_msg = origin_msg + fake_padding_data + append_data
    return {'attack_fake_msg': attack_fake_msg, 'attack_hash_value': attack_hash_value}

sh = remote("manqiu.top",20445)
for Rounds in range(100):
    sh.recvuntil(b"Round")

    sh.recvuntil(b"msg:")
    # 服务端根据正常的数据预先计算出来的哈希值
    msg = long_to_bytes(int(sh.recvline().strip().decode(),16))
    attack_data: bytes = b"Tiffany"
    sh.recvuntil(b"sign:")
    h = sh.recvline().strip().decode()
    md5_value = h
    
    # 预备发起攻击，先计算构造碰撞相关的参数
    attack_materials = get_md5_attack_materials(msg, 32, md5_value, attack_data)
    newmsg = attack_materials['attack_fake_msg']
    h = attack_materials['attack_hash_value']
    sh.sendline(newmsg.hex().encode())
    sh.sendline(h.encode())

sh.recvline()
sh.recvline()
print(sh.recvline())

#VNCTF{append_key_instead_of_message#6603db4e}



basiclog

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import signal
import os
import sys
import random
flag = "************************"

def timeout(*args):
    sys.exit(0)


q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2

signal.signal(signal.SIGALRM, timeout)
signal.alarm(1800)

x = random.getrandbits(48)
y = pow(g, pow(g, x, q), p)
print(y)

try:
	_x = int(input('> '))
	if x == _x:
		print(flag)
	else:
		print("Error...")
except:
	exit(0)

题目要求在30min内解一个DLP，并发送给靶机从而拿到flag。具体来说要解的是下面式子的x：

可以检验出g是一个q阶元素，所以最外层的指数上有模一个q来加快运算。

由于x只有48bit，所以可以想到是用bsgs。那还是用bsgs的思路先把x拆一波：

其中有：

然后把a和b的两部分分开：

也就最终得到：

所以爆破a建立左侧字典，然后爆破b来查字典即可。不过考虑到30min可能比较紧张，所以采取了一些优化：

  • 用gmpy2的powmod来计算模幂
  • g^at可以看作多个g^t累乘，所以不用多次计算大的模幂

这样优化一下后，发现30min的时间并不是特别紧张，运气好就能跑出来，我也就一次成功了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import random
from gmpy2 import *
from pwn import *
from tqdm import *

q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2

sh = remote("manqiu.top",21130)
c = int(sh.recvline().strip().decode())

dic = {}
t = 2**24
t1 = 1
gt = powmod(g,t,q)
for a in trange(2**24):
    dic[powmod(g,t1,p)] = a
    t1 *= gt
    t1 %= q

for b in trange(2**24):
    inv = invert(powmod(g,b,q),q)
    if(powmod(c,inv,p) in dic.keys()):
        x = dic[powmod(c,inv,p)]*t + b
        sh.sendline(str(x).encode())
        print(sh.recvline())
        print(sh.recvline())
        print(sh.recvline())
        print(sh.recvline())
        exit()

#VNCTF{BSGS_1s_a_BaSIc_AlGOrIThM_and_NeeD_S0mE_OPTIm1ZAT1ON}

后面和zima师傅交流了一下，可以知道一个事实：既然字典不会变，所以完全可以打完字典再去交互拿数据，时间就绰绰有余了。



basiccry

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
import random 
from Crypto.Util.number import *
flag = b'********************************'
m = bytes_to_long(flag)

rr = matrix(ZZ,[random_vector(ZZ,256,0,2) for _ in range(256)])
mm = matrix(GF(2),[list(bin(m)[2:].rjust(256,'0'))]*256)
cc = mm+rr
ii = vector(ZZ,input("Undoubtedly, this is a backdoor left for you: ").split(","))
dd = rr*ii

print(cc)
print(dd)

连接上靶机后，题目生成一个ZZ上的256x256的随机01矩阵rr，并用flag的二进制串生成长为256的GF(2)上的向量mm。之后可以自行输入一个ZZ上的长为256的向量ii，然后靶机会返回：

  • cc=mm+rr
  • dd=rr*ii

相当于要在已知ii、cc、dd的情况下求出mm来。

而刚才特意念了一遍每个向量究竟是ZZ上的，还是模2上的。其目的就在于要发现这样一个事实：虽然rr仅由01组成，但他是ZZ上的，而由于ii也在ZZ上，所以dd也在ZZ上。所以可以直接令ii为一个超递增序列，然后用dd的第一个值就能解出rr的第一行，就可以得到mm了。

exp：

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

def gen_list(length):
    pack = [1]
    for i in range(length-1):
        temp = sum(pack) + 1
        pack.append(temp)
    return pack

length = 256
pack = gen_list(length)

if(0):
    sh = remote("manqiu.top",21724)
    sh.recvuntil(b"Undoubtedly, this is a backdoor left for you: ")
    sh.sendline(str(pack)[1:-1].encode())
    print(sh.recvline())
    for i in range(length-1):
        sh.recvline()
    print(sh.recvline())

plus1 = [0,0,1,0,1,1,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,1,1,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,0,1,1,0,1,1,1,0,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,0,1,1,1,0,1,0,1,0,1,1,0,0,0,1,1,1,0]
sum1 = 93712906916124172189611184615071012407406264290121211003290014222822299910750

T = []
for i in range(length):
    if(sum1 < pack[length-i-1]):
        T.append(0)
    else:
        sum1 -= pack[length-i-1]
        T.append(1)
T = vector(GF(2),T[::-1])
plus1 = vector(GF(2),plus1)
m = list(plus1-T)
for i in range(len(m)):
    m[i] = str(m[i])
print(long_to_bytes(int("".join(m),2)))


#VNCTF{H4__1ngw__ght_simp0__4nt!}



crypto_sign_in_5

题目描述：

1
This challenge will be the last one in the crypto_sign_in series. It's just a coin game.We believe that you can solve it, so good luck!

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from secret import flag

flagbin = bin(int.from_bytes(flag.split(b'VNCTF{')[1][:-1],'little'))[2:].rjust(34 * 8,"0")
q = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
n,m = 77,32
F = GF(q)
V = VectorSpace(F,n)
D = DiscreteGaussianDistributionIntegerSampler(2**64)
lwe = LWE(n=n, q=q, D=D)

def t055_4_c01n(m,n,lwe,coin):
    if coin == 1: return list(zip(*samples(m=m, n=n, lwe=lwe)))
    else: return list(zip(*[[V.random_element(),(F.random_element())] for _ in range(m)]))

enc01n = []

for coinb in flagbin:
    c01n = t055_4_c01n(m,n,lwe,int(coinb))
    enc01n.append(c01n)

f=open(r"./out","wb")
f.write(str(enc01n).encode())
f.close()

out足足有30多M所以没办法放在这里，有兴趣的师傅可以找我要。

具体来说，这是一个Decision-LWE问题，把flag去掉头尾后转为二进制串，并根据当前bit具体是1还是0，来选择生成一个LWE样本或是一个随机样本。要做的事情就是判断出每个样本究竟是LWE样本还是随机样本从而还原flag的每个bit。

用以下语句可以打印出来调的这个LWE的私钥s：

1
print(lwe._LWE__s)

可以发现私钥也是在模q下随便取的，所以不存在私钥是短向量的漏洞。因此着眼点就只有想办法利用e都是64bit数量级的这一事实。

只给一组样本的话，的确应该是没有办法判定这个困难问题的。所以想到的是多取几组数据来一起规约，如果能规约出符合要求的短向量的话，说明取的这几组都是LWE样本，也就都对应flag中的1。但是实测了一下，至少要四组正确数据才够，这就只有1/16的机会成功(当然，由于每个字符均可见，所以最高bit肯定是0，可以不取这些数据，来增大取到1对应的数据的概率)

然后普通LWE的造格思路还是挺明确的，造的格子如下：

其中，a的下标(x,y,z)的含义是第x组样本中的矩阵A的y行z列；b下标(x,y)的含义是第x组样本的第y个值。这个格有的线性关系是：

然后由于s并不是一个较小的值，所以需要对1和e做配平处理才行。造格的测试脚本是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples

q = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
n,m = 77,32*4
F = GF(q)
V = VectorSpace(F,n)
D = DiscreteGaussianDistributionIntegerSampler(2**64)
lwe = LWE(n=n, q=q, D=D)
t = list(zip(*samples(m=m, n=n, lwe=lwe)))

def solve_LWE(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [identity_matrix(n+1),(matrix(ZZ,A).T).stack(-vector(ZZ,b))],
            [matrix.zero(m, n+1),identity_matrix(m)*p]
        ]
        )
    Q = diagonal_matrix([1]*n + [p] + [p//2^esz]*m)
    L *= Q
    L = L.LLL()
    L /= Q
    for i in L:
        if(i[n] == 1):
            s = vector(GF(p),i[:n])
            return s


s = solve_LWE(t[0],t[1],m,n,q,64)
print(lwe._LWE__s)
print(s)

跑起来可以发现，由于维度不小，所以十几分钟才能跑完一组(看maple博客发现把矩阵上下换个顺序就只需要六分多钟，不清楚是为什么，还是LLL理解得不够)，而由于我们本身就是随机取的四组样本，本来就只有1/16的概率都是LWE样本，所以还需要跑多组拼一下手气才能出结果，所以这个时间没法接受。还有一个严峻的问题是out文件实在太大，直接粘到jupyter里会卡死，然后又没有找到让Arch里的sage10.2读文件的办法，所以只能用本机的9.3来读文件，也就只能用9.3来做LLL，这就又会慢很多。

然后在maple的博客里找到了一种叫做primal attack的LWE造格的降维技巧：

TSG CTF 2023 WriteUps | 廢文集中區 (maple3142.net)

大概看了一下思路，发现这样造格之所以可以降维，是因为把格中需要规约出s那一部分去掉了，就变成仅仅规约出e然后再计算得到s，这样还有一个好处是直接避免了s本身数量级不小带来的规约困难。生成四组LWE的数据并且拼到一起，发现由于这个降维硬生生降了77维，所以即使是用9.3的LLL，也能在一分钟多一点就规约出私钥。

所以现在的任务就很简单，随机取out里的四组样本并规约，虽然一定能得到一个向量，但是只有四组样本都是LWE样本的时候，才会得到正确的私钥s的短向量。也就是说，如果某两次随机取的四组样本，其得到的向量相同，那么就可以断定两个事实：

  • 得到的这个向量是正确私钥s
  • 这两次取到的样本都是LWE样本，在flag里也就都是1

有了s后，就可以对每个样本计算：

然后检查向量e中的数值是否位于2^64之内就可以判断该样本是不是LWE样本了，也就可以判断该bit是0还是1从而得到flag。

exp：

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

with open(r"D:\题\2024\VNCTF 2024\sign_in_5\out","r") as f:
    temp = f.read()
out = ast.literal_eval(temp)

if(0):
    for i in range(16):
        w,x,y,z = randrange(0,34*8-1),randrange(0,34*8-1),randrange(0,34*8-1),randrange(0,34*8-1)
        A = [out[w][0],out[x][0],out[y][0],out[z][0]]
        B = [out[w][1],out[x][1],out[y][1],out[z][1]]

        def solve_LWE(public_key,p,d,n):
            errsz = 64
            A, T = public_key
            L = block_matrix(
                [
                    [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
                    [matrix.zero(d - n, n).augment(matrix.identity(d - n) * p), 0],
                    [matrix(ZZ, T), 1],
                ]
            )
            # for row in L:
            #     print("".join(["*" if x else " " for x in row]))
            bounds = [2**errsz] * d + [1]
            K = p**2
            Q = diagonal_matrix([K // x for x in bounds])
            L *= Q
            L = L.LLL()
            L /= Q
            err = vector(F, next(v[-1] * v for v in L if abs(v[-1]) == 1)[:-1])
            private_key = matrix(F, A).solve_right(vector(F, T) - err)
            print(private_key)


        q = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
        n,m = 77,32*4
        F = GF(q)
        V = VectorSpace(F,n)
        t = [A[0]+A[1]+A[2]+A[3],B[0]+B[1]+B[2]+B[3]]
        print(w,x,y,z)
        solve_LWE(t,q,m,n)

#140 71 47 38
#(6083834021475335823567742758933693611200764070417372403448, 4566359739347146259000248085687536225050661289753942379883, 5140084698212546616928962519978960958151532144124467390108, 3213100908819453745514676249812506308283223978934112109369, 4513460395501737424224195589573835296813757052452274949023, 2465021575910495604641861126885224008737671019424350880749, 4686280207140936462945451329422808759734897183546413348370, 2894642368563034408352945598025387588651994814070169093577, 1797920039438635873205221650527638888862692991400404867597, 1995451041629650469062449379306390749306628332054790355160, 1496259789765879442009505862846410391042272941735930646789, 4281723246418158931313375486823574814307947783193719906078, 2865797257902484299464256062690350663243227661212176240105, 2257429823298349527900373553599416016234113575223272600000, 4565967021648505424321165254910510944654290567948481442769, 4047521573788473684416151029035954151983858369668435016302, 2402026219608709074767488823322533980796028754885334823529, 4846202500389756789726871514561820402406895168767892056284, 4002842354714907870069482728903144869534756107379097438554, 2930075288567783998751605107933834249216488586954550253367, 540213814686136482197549432837595803042120599951527463304, 4026976235711976231413989024511359800924707763084340499485, 328947225588765752907432280369424578628138990673091139628, 248651792592328026373442684027219854952001218589366644666, 3745671327332784859781121744269959089185480746601729905096, 5441534553818364652711000056615931308026598308993319505926, 1848939381332648799446998628822269626638872978252321324130, 2415306867409431096322504397108111604114776098428990292496, 3593603666041492237924417675999030725918574118359318463850, 5464712878509886681641419654762416890108754278827333923849, 1447155323597156111597890696751122281134900914723437183085, 882201639514135772027310589952737533410885816783672485162, 4184779989223626059564408112028579950731267227945450219952, 5353988367466099287243478824441826370321351430837351758014, 3150947196817608517248047967231431423661445190917154394060, 2453948533540870197355607847121071648186824130787565582526, 5116759774826369407193068866376928576813521296078874661219, 5133449393060998653462888411818342123310520360904796105165, 3625606257240243668325920566344968077667452672727209555779, 4411494409772523210012448361844045008985063012176317662703, 1099968388709816804469906841357256033036474253010597841757, 2261060056632377251100608517403067809152448207960579613030, 394769211664654548458581078470204359561177816687538186893, 1141752650156677754797914655361413955851715086457928117498, 1343340630874933289175866976678770322279233377681489371447, 3404072708309202557513425913792951886144478172109130232937, 3578401269055296980843644133047177574441735122413159784406, 623896315881622971753416056296752475798836585545687028533, 6273285482202595235996665391651217591942811682582717932941, 1262993935923029233140264799444952608761518049948007274381, 4280689594861934321611447640047696504661540637657192572784, 1945402853811583177359359675470111282915614793401510224269, 2740771104526695458853229085774671602194248386044638942411, 1237686487142251049979208718533069233280200826831703910445, 1949422073032071232061954272133182339963985645270640558311, 5717002233703373796631557441485415049384045985691832377321, 3420287446018035851190699700441550244699705262517534938401, 5674817320578506858997642720340953779620156823493583944698, 5727958402496586122827239222955155899242098509617010812210, 1363766616410535566753748779173414393887896186541216102487, 2022170681706917700011359173984145892730258545550864150963, 2189082463827105787808971574476684010247341822823417964747, 1025109114274698712218028456780283343973232210863861618797, 1964502126347801011599206640360152569512884203488767340398, 5129307406885723570172407401817872782573182109883338902822, 332688815199971876917731331992708803848814941341322088531, 4981500170538142268227893404311216913232356480580702937318, 889945207709279193316822408630428415664056207218323136722, 2277450611954959517246153409683019504554854576106067384738, 3375543737035886922143626629308660522619838043673895105017, 3680523808279157005143351950828171997718304325128262484219, 6196451435472884414559871006977923824209976975620578099346, 322597173578283285049022478572932456872999197846183175136, 4170132166713231824611540017314409428179807536361462459933, 5031571130868805964685360291246248951497587972714798887652, 3867434567034846216674716885412887414432188555647648388885, 218648389511481570063454008207406519205791436458874972660)
#86 105 16 0
#(5114583822240110842413496797301006821782507703746395307380, 5844407379931174468679273484139776533624446366432563004075, 5333533466009351307774129017246950787609550435509747266860, 587204139877255983915944487585804414954394295673624883969, 4645569427735592424185456245690168647816253334206191614775, 2225770257692453630765611251333504790926325365590144097117, 5079260924513247699755134790680149714630184836071581279758, 5438440613682790269938976204873043254018297818854393559028, 5097108213439035669479003550434928190604967030545191762985, 773865315473799762836083478150880411225639643793923386321, 1482271694756463867217890247941751829614228975732265502276, 4077772443187503570398971625945498208226870504943936113144, 697104406539983874152099639665679309794429962099625162043, 2597654110148380384582379676922607568679966864616376999113, 1837267337179991973588000904351885681401371569810996066886, 2798267024485055542767270695615427987681614832347438689521, 6062263884882582596603140567442252273364374140878291620674, 3551500508850833299099578233168544605354821069710309724155, 3886987933786538394998889665857520687517674588672498953412, 2724099032025001647155983168477436602116273774825286531766, 2602467287587787001938604917602385263068435295306511718472, 582095607389631970434336671711871805696273491534068642589, 361964471627560175973596037797547589671969426258705141812, 1118846131394740267036687877105917399795899029320251254082, 2572116979143392097416814690898813338860027526314680003383, 4423211396367088713927604137681837258540498780451066016193, 6006470345580920361068802337290786766848143572864947248639, 4572263424450796825681792491184975874106158239828011070281, 1992243165024161494461566528650365455222700265787855578150, 2009015813555881104932999273373874156385611054921395134403, 3190857152302134340678710512447143350985235242171566792920, 838184496226440640257461392863584783156808323912598721556, 1978747844046437213194825686796664057947497298703770031803, 3209378220522795530624395227442051104096827359262486540433, 4678244015345735497521818073733192397316390495869383714116, 4152680848054282513702303928314701385235904109123119584487, 4773165195371156869278412055536901159125039874089827968796, 4679830049589420419127354368404140613017898050088808217381, 4135376751594849576299174378161982859021086041657134866455, 3782825941572463158082519335927896138520089863837291228205, 2237198911783285913314846125736337950866523949210410330748, 2754232529356813954814880532498303712531682867678081954710, 587120306886213151922564207244870879488038059061970270589, 359697530615108307822765564172787353100839085743328809248, 3472288007559277740586998457663607333708533389244472388089, 1551469002490603966766455294938040120954636465980631402245, 4247113952053104076119528246650153083306072450679695083069, 2305799810255199391357387726864936715649063887105995374683, 1738124570426618818375516962135339405019762100439823824233, 3886283611951426066726781537622859162326928822578348459432, 2554505161171235633774993119000638199696684982614799115975, 2561642653010325399136966322709537674502620545889618776212, 5846977724147182401108371004123093346864390482103617531902, 378848654378090800503236720419328257367630078195500232043, 1413316694294785217437209754944159183525507741527209638410, 2598415673398047732168837672881310695046349612425031752365, 1268360976087952594866205611051897631944468395783109511377, 566541568157597726856413053968586801463070079265338259952, 5815443870000543537075891188585804503971621099625226623577, 2028973208281644510144420361804540059779407560127396860713, 6054880309296081211840549111415535790277106267516100156294, 3119950198062613889520974152263777707543003015571906337018, 3904759498449081621974912039310988182870701186830661166241, 5784641946608748859555912785982972852508894623795658962178, 3098105435854144223980225089953112746082838645112464454781, 2429351476926734996027352250105046861325800502852009816762, 3404839648879533789471814381277179311404020756091849008753, 6056661938796482890322880478436430252536943646525114160047, 5276934667546404687745653362845284482894255323834527197563, 3645372452747959446998565432636521567760523663421715230087, 3044916391944397116936128073425943832365623904207835470777, 33835006459087824826246025202470661199874980459775981304, 5681217695394840109431791527040752012116596192124637981539, 133913656461827606525350283116384963991550236488242852160, 2771884709076235658907244445580043276515942141381355213167, 5401442096322221781864419574070229177683440173677132791014, 4591288618393414104342457023421990422221305595936762551178)
#4 1 20 198
#(6222317551517701633454517495353610175072379419360284760483, 5200129689554314538858675872924467072443893909457958011080, 2009799813027977992299402348281501973227435457689884008305, 1255199378958373275986210996439995171827453954506456226853, 3258396624786344293914735081912859146275947986918719100261, 4454196874529842088524053384368874010739522821685557809690, 5875218158700924822420179692228980603995511917805349169725, 1350073035033404494850107514861273782134782726657192754074, 5439542484373354834814072651054778956605928843922793101014, 2498056464817802802630363479573160299813120349212892286625, 1203427231402121583070247051446760407215890343704964876954, 1959079683559194688476771092890078904593620920187681055917, 5138906741402647216463393233851199099326400781486297973711, 2555578448866721672453609455014519148099434498488560558871, 24721666697762026353959362243657539858239638613200271516, 669051008588103647415827055046152938424958635890059452376, 5487138003650239330594765186433734061525870926763188651311, 831410340090372529981581998439876009891010026960607929030, 2363662803618293838283746453707110351601096899951803492352, 2264062760560186210291692721657447472725787027389537106196, 3282802740827286904051370026040332965341650981590539231578, 6063451103235622859977989971745684399798433532691290979010, 571189626397437784552074197424013906007963112338117333030, 515006449619701538664573315628800781001345805676990628740, 2752093810032966613819450091023253308573616179669846346505, 5248425778200576056847436905441965819547379908800744590877, 1631314906253246788047306197825073069912486535061966931001, 6123490875157938649717686148828876731855752856946686287307, 325978392357925412216759337229910011949463338409441506782, 3449091821011363409547305940540786818175682245739641724971, 4385074035200607176740189739567057696395292335546243264188, 4318495547625671824466258404567152978805624631894853454421, 2452490448593944139347172998924058745416836833485527046104, 5250793942577828640459040441821117138328180967389198249460, 2774305839285122138968803431080140143781196593383979379856, 2652661951657260880995997771681145389446456808571415531644, 5837553205388017180940781345454247631681383835864307258682, 1344426844691737869989021571188302520764023414083825923577, 3447006049723868579692537098638375497089355874142415921606, 3726265245688948032764949368697683873501348599569064597809, 2528476847323412990383468283210543604690644140812855928686, 5844282876076562553764743628459614575237345785357681087445, 1772382669057193516587725089637774242800332001012839419768, 2498883401373338812755268563635793225090666490370313626518, 3501372665385071979784946707953941237468333980663012105552, 4973518474075137299590720867550964662575180013346317002202, 4253735816369161802978753466958868323739467052456755871699, 2132904566622100793084542247896578377426987145830556426203, 5492936412823241297341334825717282194885051769133346315217, 4822744492880482494117406023421573760796026225034668334091, 4264205286256235435932274697385576581198684110831049321075, 3210483577371966660504016694291224996011069912333279727838, 2917999658517385833849486756550254300995495350610550278511, 5201790822960286706599767681013457559987725063511460188205, 2240393461346951925393116282447179626085780197531702898431, 4885969557239030529250379286874449891179153050422090607171, 4752281660267418208969874976240144550165569887294686907165, 752580276667260317838573259684948189875729146639519425807, 413252171282525816845929329870426165577774494070883448386, 2428614152230749727839752701058193979240522917209297694110, 791359301619336749243357658505275956120025288355384327030, 1065149343870654272103312355807204061984423557734550975054, 1828946170230921890158237516908719681853001802564461621923, 3522283791140235289133990014142065027964179578660683795003, 3172043875973813872301065081039939422498827898323690494623, 3851681453770885975508743069704494975548947348601826973991, 1847301196538151829595830831514742776946594578523646111182, 3545556255634531894897898987213959389047994864372993740720, 3763369022133048479314762867375132324759607225022944846685, 3919990160504542183733857182132618452695706783626647312182, 2588661454699164705188651028269953108763585174516046372310, 495261345166747359332123767863194475621395586572186909481, 1459085019640701074016349213292284883519570702790565220338, 4135337256589509708480119235996362531492936799112203057211, 3309795870547019909464469792837544428071295592631712821401, 6176747611190419298213111146200140116883763246893179760429, 6119934992929935542065536047229541419089658113013443856441)
#9 10 93 62
#(1807793105576180924772034582510321797676838930216754065447, 1605630885678894510794827191730915328327477523473097609898, 6117619997534335053964013058256109345928324789397189453404, 5342947317212918044793300090397738968226550912549762785316, 5234787137863920623839953035091418928324009887214999185476, 1690854955718741873745190674591455740696876465095608288648, 3353263944551736604919380481284089104735009512631720475999, 3501929601633124467133239301771115577842911656562840775249, 2933427630921255120521546485483258739721536957383696558824, 2247341309229256696821290851368353273561651415188475666779, 6167208606788849409407701441764183092054945798399864623386, 1646934330999789560414034766272336506281700891634274602152, 2856155672438042174461062570485981655155669766271203836340, 6171257317850045387106402935793183800159823454983369410462, 3488323392905233408843046921782378630959405935854773824117, 2964705621045548539137490236147291204013129058128219959306, 2945152472095616371258416947817649432995336154399860272925, 3182413132816293326634721187397490612420517660474401995197, 3074620179018053708075298660420949569903117234516290123181, 4631368960883902389337583988159060659351649586917616591266, 3431022620703339587189465416637073521513786325691223007183, 92818709009128499897233069697854634522186526289180169242, 5049464446747830939705878813318247321239072557214111021986, 5493649314183713959085404065928445066028377346683985186037, 581947638923675556441544054767175625968084925613207928293, 5122320341944568068616161494828478815078641764421103410247, 2392463766190615365468887589916995941266126358431945806834, 2370624198332825462958383626738843685419502158551783576756, 5110843872401852375119689938902346294996191485008470067317, 1556219445903067968581392031609067283592409194581847133959, 4038369421580511970547379352303828415552112905107463932238, 5880098856641405173599306916351270342627970713785090553496, 1760418563865911039728426598252984659098838083881742185925, 3365833907879657773369440646968805774275344610013108545086, 473934034005517359768969091357843099642850788869884381963, 3181515101797253728629569823054552198177583024961922343734, 1319865512776619980038194662225571543526163351544320967768, 4376650855327357347994112109657792654134458873842480337407, 1239945813569744114387719485027582079831174228264136532643, 3502961689714988367079178130854469396410638826319685519667, 4837693458125439393166878422243116812522856723779066137892, 2266550799240241020936821108740081345503673833795674471664, 6060943026114287265931427521846389947036641655807229112130, 2001101588012692283744442819810363179990610207890375733806, 5816213844418337992909923037872203578601997330587946818343, 5874234766444677664740420267328932006851405975078980840635, 4850135240080864338421310984308240480509399170424870441058, 6040690489891224694169419604946764354238468413708344385900, 3617848737268993886970953144275709296588378491123901535944, 3493864645155902177364319646348828302763804897246280772041, 435121088389753010301957182724891043921036952296349971131, 4194546870991220398791085176301753233716525049229461482235, 4391278173460640343990593179526409216097771943429025427430, 5997269873360554244015854762373143826263432820076707836220, 4667180976535135027412355031467893380969013754429554250292, 4997001716790295870731999257134286876976868105687282456684, 4050515242443821644392234193388075326164245520380287079695, 2616924589773880376250266881654345847691627197067590842463, 2928089837302896784344983638048603773633301407396098112186, 942860621066404127098282148758898737054835303052305467622, 1609138241427194036125750716186338640977640845649810057369, 576298179944940911229274757885117081585041439019548059799, 3536411687045892758987681963045060340477420197400118281027, 2600152123655405915830076269004977291670864888675140408206, 932966976283851469483658975814642080940127880089687774773, 3435608706267120533099377047517604755557301793755273899682, 3032183960080368259552858442230037786482784832104759045560, 5621807748888691032230290777006582724882964903122605902039, 32400843809142388010816878731880658810796370863476748145, 196551366411603315762332859039916677969696191178276885283, 4528245845036734368523423431535702035324366844399710034054, 908998280861117742288656899951722090007998345982382101666, 4095997545964294835205259265166946952524832394332118915602, 6254321909728428586779961813696078676126790382683588479925, 2217038887737813108462073259248048018227516940121186493575, 264888712460112175102191569550346195091355089582827445458, 174436109520476098392929210282630147468453720840050306192)   
#121 148 13 156
#(613342273242036261606833016088319123132463277984910497463, 4076650513326143955491088167137912178627075597221450789684, 2549329906726812935530524509341909119364264617786599824635, 535825522006396518527259832351330338193381413950360697402, 1609872304355460970010960140887318263622234725519166702406, 4595648789779280064119910463215267170990700939562132539856, 6202941719906820763530582781492236402841826474765381162280, 146383509309656787207823188501734527824176111154201047305, 25465872034667643064463909501005010953305593087213127158, 5013485259639758680882777067036463419496758042789385275137, 1777422319247882636219090680426283447165722916857107812190, 4959421098066179466799808560075065301437350592274808503820, 5723391070377102449743744081625157290937426760607048647001, 5579167484101457150344070851692559997547063390029102558581, 2123271456411769395820302754063016393550466129156442328858, 572058681829484719437875549021975496708981376651445779146, 1996754083172275118297200314213966122004207462974545461480, 649415622894973498105884989211940045248578796902502764848, 5343837733439620532064693899882946579011468824877590399514, 4536734106153254802558272688809162548812447820425538913213, 5330631409834614101978921134450800123996327668689271752562, 3479983000539044724588779352660845278735195980776395027810, 3819253260295783049342002965120739671341459503288137480575, 4203827071561779747450292829144913726210324604507524236546, 2491286714418962202580023309790386099266344551250969556718, 1284159714630186695529322535424527510357589893722000356110, 5945223614993453619096411961460130943025519769351880807493, 4853551820393706768019940098023131816582202306119169299946, 612130553158171949998733188220755133455097622737437555843, 2069818290572633490441459927726787913447295145871681294648, 1721604262696206995101427365487774084172530684313841766129, 941992114362349379667188584785492090202787936696274882240, 820918862506577184430380412598414630041014584836402707073, 2207995725975508564021969157015055383801820064184897666133, 2603675124173872645273641656213158346794031794544252313064, 1152474642143941579481586830337369451253957814755827106091, 3137106011714933777398359233072786179282925280355476692226, 2407629898411598025375194659733233259982658121473567407429, 3659895586541780443981349844632992233738047374694648636006, 2310837293084147067530609507749051065944151673853921223406, 1640871947615472637216990217553991774883479690302348099722, 4830535708422702613923767099370434529889347525347902777213, 5019741735770970782480381041696380223642687390664704650310, 991969565874178227134453184707552154182572077243789543260, 4909785842087840030235943197623687650876171812056534150439, 3773768837236098163715986177993051361236507942750746831148, 397534731486562148071305497381758192970358672378750915563, 2796675043111656256467778670859459278093029377191272188741, 4167266993961025070805032689385675908547671929406921232596, 346647451942475485693015925869687421701930054004916260574, 586360956467414830855168453803543785818551269847562030989, 3588946199702605057506260970541185925556239035692289638912, 2796604217410149817200479231285250748317498451864055700999, 3485472841164546323016317722882932534865109132447165398110, 5314728761364377662914045078695354454771116896662907057928, 5521801509166850292893781523688616981445396600629548416897, 67447221478386207363391806711173495736430653080107109699, 1898784416069477798532280168280942817663210516125108589121, 4200901541382254360983657360195133471550622021724160631587, 5460951264207299348884719125155894296120852903988927811022, 2418976951418330350640044927403501277655615571198829532052, 3691405202544890951334673062283622185746825271560023431647, 4744699962160201987084598064817319585281592830197760470519, 1865343841649655849266964014370456784574472476885160920227, 4506368784364659407517685533581197632681345304635168961930, 3646407247384584510081202388574488073494387419945213959476, 349552518504785289958278502765037520722049405385328745854, 2864650519996879527078243770452413201226591274415075877322, 986152544517790120157595798843105909729407704517235470569, 2016533672424827908649317477614551994772180969976718862723, 2893772817238631212619926691197835869131378430346292726699, 3771965446904261763835807766932528368204887116209948717194, 5609332408378363868262390400372472969609701270556855514940, 3193437145789347465294366134791949966776680837982066048790, 2193208047726349886809630566059761684256220792081704391394, 2406583171012025048019478267451943324775008158368449793220, 2116191831529534802481963230213833718182407681577238467477)
#163 111 74 108
#(613342273242036261606833016088319123132463277984910497463, 4076650513326143955491088167137912178627075597221450789684, 2549329906726812935530524509341909119364264617786599824635, 535825522006396518527259832351330338193381413950360697402, 1609872304355460970010960140887318263622234725519166702406, 4595648789779280064119910463215267170990700939562132539856, 6202941719906820763530582781492236402841826474765381162280, 146383509309656787207823188501734527824176111154201047305, 25465872034667643064463909501005010953305593087213127158, 5013485259639758680882777067036463419496758042789385275137, 1777422319247882636219090680426283447165722916857107812190, 4959421098066179466799808560075065301437350592274808503820, 5723391070377102449743744081625157290937426760607048647001, 5579167484101457150344070851692559997547063390029102558581, 2123271456411769395820302754063016393550466129156442328858, 572058681829484719437875549021975496708981376651445779146, 1996754083172275118297200314213966122004207462974545461480, 649415622894973498105884989211940045248578796902502764848, 5343837733439620532064693899882946579011468824877590399514, 4536734106153254802558272688809162548812447820425538913213, 5330631409834614101978921134450800123996327668689271752562, 3479983000539044724588779352660845278735195980776395027810, 3819253260295783049342002965120739671341459503288137480575, 4203827071561779747450292829144913726210324604507524236546, 2491286714418962202580023309790386099266344551250969556718, 1284159714630186695529322535424527510357589893722000356110, 5945223614993453619096411961460130943025519769351880807493, 4853551820393706768019940098023131816582202306119169299946, 612130553158171949998733188220755133455097622737437555843, 2069818290572633490441459927726787913447295145871681294648, 1721604262696206995101427365487774084172530684313841766129, 941992114362349379667188584785492090202787936696274882240, 820918862506577184430380412598414630041014584836402707073, 2207995725975508564021969157015055383801820064184897666133, 2603675124173872645273641656213158346794031794544252313064, 1152474642143941579481586830337369451253957814755827106091, 3137106011714933777398359233072786179282925280355476692226, 2407629898411598025375194659733233259982658121473567407429, 3659895586541780443981349844632992233738047374694648636006, 2310837293084147067530609507749051065944151673853921223406, 1640871947615472637216990217553991774883479690302348099722, 4830535708422702613923767099370434529889347525347902777213, 5019741735770970782480381041696380223642687390664704650310, 991969565874178227134453184707552154182572077243789543260, 4909785842087840030235943197623687650876171812056534150439, 3773768837236098163715986177993051361236507942750746831148, 397534731486562148071305497381758192970358672378750915563, 2796675043111656256467778670859459278093029377191272188741, 4167266993961025070805032689385675908547671929406921232596, 346647451942475485693015925869687421701930054004916260574, 586360956467414830855168453803543785818551269847562030989, 3588946199702605057506260970541185925556239035692289638912, 2796604217410149817200479231285250748317498451864055700999, 3485472841164546323016317722882932534865109132447165398110, 5314728761364377662914045078695354454771116896662907057928, 5521801509166850292893781523688616981445396600629548416897, 67447221478386207363391806711173495736430653080107109699, 1898784416069477798532280168280942817663210516125108589121, 4200901541382254360983657360195133471550622021724160631587, 5460951264207299348884719125155894296120852903988927811022, 2418976951418330350640044927403501277655615571198829532052, 3691405202544890951334673062283622185746825271560023431647, 4744699962160201987084598064817319585281592830197760470519, 1865343841649655849266964014370456784574472476885160920227, 4506368784364659407517685533581197632681345304635168961930, 3646407247384584510081202388574488073494387419945213959476, 349552518504785289958278502765037520722049405385328745854, 2864650519996879527078243770452413201226591274415075877322, 986152544517790120157595798843105909729407704517235470569, 2016533672424827908649317477614551994772180969976718862723, 2893772817238631212619926691197835869131378430346292726699, 3771965446904261763835807766932528368204887116209948717194, 5609332408378363868262390400372472969609701270556855514940, 3193437145789347465294366134791949966776680837982066048790, 2193208047726349886809630566059761684256220792081704391394, 2406583171012025048019478267451943324775008158368449793220, 2116191831529534802481963230213833718182407681577238467477)
#same
s = (613342273242036261606833016088319123132463277984910497463, 4076650513326143955491088167137912178627075597221450789684, 2549329906726812935530524509341909119364264617786599824635, 535825522006396518527259832351330338193381413950360697402, 1609872304355460970010960140887318263622234725519166702406, 4595648789779280064119910463215267170990700939562132539856, 6202941719906820763530582781492236402841826474765381162280, 146383509309656787207823188501734527824176111154201047305, 25465872034667643064463909501005010953305593087213127158, 5013485259639758680882777067036463419496758042789385275137, 1777422319247882636219090680426283447165722916857107812190, 4959421098066179466799808560075065301437350592274808503820, 5723391070377102449743744081625157290937426760607048647001, 5579167484101457150344070851692559997547063390029102558581, 2123271456411769395820302754063016393550466129156442328858, 572058681829484719437875549021975496708981376651445779146, 1996754083172275118297200314213966122004207462974545461480, 649415622894973498105884989211940045248578796902502764848, 5343837733439620532064693899882946579011468824877590399514, 4536734106153254802558272688809162548812447820425538913213, 5330631409834614101978921134450800123996327668689271752562, 3479983000539044724588779352660845278735195980776395027810, 3819253260295783049342002965120739671341459503288137480575, 4203827071561779747450292829144913726210324604507524236546, 2491286714418962202580023309790386099266344551250969556718, 1284159714630186695529322535424527510357589893722000356110, 5945223614993453619096411961460130943025519769351880807493, 4853551820393706768019940098023131816582202306119169299946, 612130553158171949998733188220755133455097622737437555843, 2069818290572633490441459927726787913447295145871681294648, 1721604262696206995101427365487774084172530684313841766129, 941992114362349379667188584785492090202787936696274882240, 820918862506577184430380412598414630041014584836402707073, 2207995725975508564021969157015055383801820064184897666133, 2603675124173872645273641656213158346794031794544252313064, 1152474642143941579481586830337369451253957814755827106091, 3137106011714933777398359233072786179282925280355476692226, 2407629898411598025375194659733233259982658121473567407429, 3659895586541780443981349844632992233738047374694648636006, 2310837293084147067530609507749051065944151673853921223406, 1640871947615472637216990217553991774883479690302348099722, 4830535708422702613923767099370434529889347525347902777213, 5019741735770970782480381041696380223642687390664704650310, 991969565874178227134453184707552154182572077243789543260, 4909785842087840030235943197623687650876171812056534150439, 3773768837236098163715986177993051361236507942750746831148, 397534731486562148071305497381758192970358672378750915563, 2796675043111656256467778670859459278093029377191272188741, 4167266993961025070805032689385675908547671929406921232596, 346647451942475485693015925869687421701930054004916260574, 586360956467414830855168453803543785818551269847562030989, 3588946199702605057506260970541185925556239035692289638912, 2796604217410149817200479231285250748317498451864055700999, 3485472841164546323016317722882932534865109132447165398110, 5314728761364377662914045078695354454771116896662907057928, 5521801509166850292893781523688616981445396600629548416897, 67447221478386207363391806711173495736430653080107109699, 1898784416069477798532280168280942817663210516125108589121, 4200901541382254360983657360195133471550622021724160631587, 5460951264207299348884719125155894296120852903988927811022, 2418976951418330350640044927403501277655615571198829532052, 3691405202544890951334673062283622185746825271560023431647, 4744699962160201987084598064817319585281592830197760470519, 1865343841649655849266964014370456784574472476885160920227, 4506368784364659407517685533581197632681345304635168961930, 3646407247384584510081202388574488073494387419945213959476, 349552518504785289958278502765037520722049405385328745854, 2864650519996879527078243770452413201226591274415075877322, 986152544517790120157595798843105909729407704517235470569, 2016533672424827908649317477614551994772180969976718862723, 2893772817238631212619926691197835869131378430346292726699, 3771965446904261763835807766932528368204887116209948717194, 5609332408378363868262390400372472969609701270556855514940, 3193437145789347465294366134791949966776680837982066048790, 2193208047726349886809630566059761684256220792081704391394, 2406583171012025048019478267451943324775008158368449793220, 2116191831529534802481963230213833718182407681577238467477)

flag = ""
for i in range(34*8):
    a = Matrix(F,out[i][0])
    b = vector(F,out[i][1])
    s = vector(F,s)
    e = a*s-b

    final = []
    for j in e:
        if(j > q//2):
            final.append(q-j)
        else:
            final.append(j)
    if(final[0] < 2^70):
        flag += '1'
    else:
        flag += '0'
print(long_to_bytes(int(flag,2))[::-1])

#VNCTF{__w1sh_z1m@_c4n_s!gnin_thI5_y4@r__}