Foreword

First ever CTF. Managed to solve a few challenges and learnt a ton!

Challenges

Baby

The message is encrypted using the textbook RSA algorithm, and to decrypt the message we need to retrieve the values of the two primes p and q.

We know the value of $r \times p - s \times q$, let the value be a. We have this observation that $r > s$, and $a < 0$, hence $p < q$. Let $q = p + b$, we have:

$$ r \times p - s \times q = a $$ $$ \Leftrightarrow r \times p - s \times (p + b) = a $$ $$ \Leftrightarrow r \times p - s \times p - s \times b = a $$ $$ \Leftrightarrow (r - s) \times p - s \times b = a $$ $$ \Leftrightarrow (r - s) \times p = s \times b + a $$

Hence, $s \times b + a$ is divisible to $r - s$. Finding b is a linear congruence problem and the algorithm for solving this can be found on StackOverflow. The snippet that I used is in the commented out code. The value of b underneath is the value calculated from the function. b has a restriction to be 1024 bits so we can use the particular solution, as any of the other solutions in the general solution set is 4096 bits long.

Having the value of b, we can retrieve the value of p by doing simple division. divmod is used here since it can handle division with big integers. q is derived from $q = p + b$. From p and q, we can figure out the inverse of e, d, and use this to retrieve the flag.

Solution implementation:

 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


from Crypto.Util.number import getPrime, long_to_bytes
import math 
FLAG = b'<REDACTED>'

e = 0x10001

c = 8755361716037050593786802368740593505819541985087751465246316611208654712808851039985566950771569219005474679214890773248679686452291791926024778938667161954201119658253063645930886986362437085401598314742279109631478572452731396671691672092589080935682736804089015740009401298581639291193682963105747576715867254889247753788661315475189523656612126700002888122729034598825641796362628516626027115516263101484541445062801096777586863144812446160024700491104414848804200440962708078212109059521089126401730984744470907608297401873174614500873021527030728187991640911253978614160956515292658729861625177800745954684779
# r * p - s * q = -34384571636542682732993801408238567193071079747335767504994340801608381182708103244757509021281874449800069281009810023907313154391464668542796187787092864913072601227852655851070468919417844230689008922504112542853587185699616544272977753830325804164014338601030700848859059311067280180340700746209053062443574270773642918163909645688335979566572624221870500744676835269869601108253139361167400301626751736498534338162228764111438600887057835670459016374249012923832476577336962810182684197767760519515721734005603313785840044947657687083840236225406435252382559823958066573244309719575485706011861244028446996920249519039258733914177844818916938491744948605478385399858626470926733928838196963004350577779862247581837961536832869640531493345914188439519605065799034864280428993112773164769200946009507688445375319097127445639570984261253620532620742924894113105707671949166533244311479026914960105181835442456417671355468402543233569770391833669600663695797387468169339523234585262610811933566181920470444240902853887724615316068488136323539979229581225786468457662315990029857258798124732280829662164932213109363870409335054243794586400741357324161913978437694775195815062757093213325952057171001722380372888748256174953952360070118846290246140793770694204401164960742113068366766928707670654861609748340943116513275092360152185494867472310293656556031756417497249251872489238008435654320326489069126549344443700948553988405022863350434081213995337512472150109078421242823877306926652997021828653860169896336216359386864067959578257760
r = 936281797755031261848169861788419286242500155122743234286943102853441400861252708389579924384747328538959760271792565686537791395731078897913727180911468908585976003090733895007958447959094383445975201070786043510921764921108055952715166472860417830673976831707347242236348495245218675030438657044803590841511241481934488468486944285639180440843969944429852785215880499136631346605823164121032336218990671202212953326203467124685189344280256775009299633701974115736573067349919745244858804283455071851912194286160784172943301316083821185405338610368688605358644365423958890024208974121167171384473118059281816494356755844809173265412809337423995268268663119244396063406978295035815869788202375167281450339517979957331467143500209528727150295191004885385839900735810500718557821053671052959432831767663810090095379231750412744076404163742435544440795801122979274805554706606583599755007872912935576369508808550677885164226933064726817359773399072956113665969905205606138989373281554161008535232454798115570092928010969726174633824544610380764744958638537085759378694993737437724201369828812993239842742165386297807164278219508640684529837977445571884153238673179892479261196341148157129952993380440229458239746064451443526116917519
s = 834939575457003657728171346390813480312906155291642219227936205156714217262322467739149680558607905413429343953514849176130680023475055635457415545359365246681638783469216604913252838569701559353464582588062109434066644004845623203772527840551656611501677400844706770270825409839625738792427657150026307314821780392251524458037197655903343177131336842583042394801173673131588262961636245185030505564613639234805815677902379543111678201103954034310087231196210755934978052370451876638256180762443170329319207101581789208664345386093469896758682416555125087939413443536267912794750486701814941395277218714280572422080584205069255289731982911845911942205319661268893590368592905932152208108183590473584581786595300724772852979382943318977777850080673301763071986653891789753006523321672813311922284194072995019342531330632536316816984745914614649167801364562670569095961614178729268507876040470655722687777049415470890053491272405716858536141212596151075134173517337948569646361076821140748265156759845142133374048339524320025708823936755215461004080494169096216330198356553864601197456450193436851885342802515269136267023694614035998000939158575602883575921465198767978819627846523739073812562683002815460930245515210169007766320597
a = -34384571636542682732993801408238567193071079747335767504994340801608381182708103244757509021281874449800069281009810023907313154391464668542796187787092864913072601227852655851070468919417844230689008922504112542853587185699616544272977753830325804164014338601030700848859059311067280180340700746209053062443574270773642918163909645688335979566572624221870500744676835269869601108253139361167400301626751736498534338162228764111438600887057835670459016374249012923832476577336962810182684197767760519515721734005603313785840044947657687083840236225406435252382559823958066573244309719575485706011861244028446996920249519039258733914177844818916938491744948605478385399858626470926733928838196963004350577779862247581837961536832869640531493345914188439519605065799034864280428993112773164769200946009507688445375319097127445639570984261253620532620742924894113105707671949166533244311479026914960105181835442456417671355468402543233569770391833669600663695797387468169339523234585262610811933566181920470444240902853887724615316068488136323539979229581225786468457662315990029857258798124732280829662164932213109363870409335054243794586400741357324161913978437694775195815062757093213325952057171001722380372888748256174953952360070118846290246140793770694204401164960742113068366766928707670654861609748340943116513275092360152185494867472310293656556031756417497249251872489238008435654320326489069126549344443700948553988405022863350434081213995337512472150109078421242823877306926652997021828653860169896336216359386864067959578257760

def solve_linear_congruence(a, b, m):
    """ Describe all solutions to ax = b  (mod m), or raise ValueError. """
    g = math.gcd(a, m)
    if b % g:
        raise ValueError("No solutions")
    a, b, m = a//g, b//g, m//g
    return pow(a, -1, m) * b % m, m

def print_solutions(a, b, m):
    print(f"Solving the congruence: {a}x = {b}  (mod {m})")
    try:
        x, mx = solve_linear_congruence(a, b, m)
    except ValueError:
        print("No solutions")
    else:
        print(f"Particular solution: x = {x}")
        print(f"General solution: x = {x}  (mod {mx})")

print_solutions(s, -a, r - s)

b = 53872156327831313573612457094695305592813307075643379367917194772979357714350706372000599875743412278282638751876190175242162578225426559802421432405068832506446438193946196627968051674623226565092558220729567237157232969728793061014392712671241356180801753712498857325602047258911557199854318271760434999282

p = divmod(b * s + a, r - s)
p = p[0]
q = p + b 

def decrypt(data):
    d = pow(e, -1, (p-1)*(q-1))
    m = pow(data, d, p*q)
    return long_to_bytes(m)

print(decrypt(c))

Block

This is essentially a reverse engineering challenge. We have to derive a way to unscramble the scrambling done by the encryption scheme. Encryption is done in rounds, hence let m be the original message, c is the ciphertext. The scrambling in one round is given by

$$c = f(g(h(k(m))))$$

, where f, g, h, k are the four functions used for scrambling. To derive the original message, we have to find the inverse of each function, that is to find f', g', h', k'. m can be derived by

$$m = k'(h'(g'(f'(c))))$$

The sub, rotate, transpose and swap function can either be trivially done (the case with sub) or we can use some dummy values from 0 to 15 and see what is their position after the scrambling. Reversing is simply done by looking at the end pattern and derive a way to order them back. For functions that include other functions, the operation is still the same, reverse every function down to the smallest unit of it, then do the bigger function in reverse.

Writing this is very tedious and does not hold much value, as most of the work is done simply by observing the pattern after applying the function and try to reverse it. I will instead condense the technique used for those 4 functions in the analysis of the 1st and 2nd function, xor and add.

To reverse xor, we first should inspect which element are xor-ed with which. We can do this very easily by creating a dummy matrix containing integers from 1 to 16. We then print out the pair of i, j with the position of the element it got xor-ed with.

1
2
3
4
5
6


test = [i for i in range(1, 17)]
mat = [[test[i * 4 + j] for j in range(4)] for i in range(4)]

for i in range(4):
    for j in range(4):
        print(mat[i][j], mat[(i + 2) % 4][(j + 1) % 4])

From the output, we can derive how the original matrix is transformed after this function. The easiest way to do this is to write down the changing of every element in the order of the original loop (since the element in some position is changed, and the changed value is used for some later operations). We will have this matrix, where the integers 1...16 represent the 1st to the 16th element in the flattened out mat, ^ is the xor symbol.

The original matrix M

1
2
3
4


1       2       3       4
5       6       7       8
9       10      11      12
13      14      15      16 

is transformed into

1
2
3
4


1^10        2^11        3^12        4^9
5^14        6^15        7^16        8^13
9^2^11      10^3^12     11^4^9      12^1^10     
13^6^15     14^7^16     15^8^13     16^5^14

Hence, to solve this, we xor the 9th (in the flattened matrix) with the 2nd (in the flattened matrix). The way to calculate the element to be xor-ed is the same as the formula used in the original function. We solve in the order of 2, 3, 0, 1 row (0-indexed) in the matrix.

For the add function, again, we can retrieve the element that correspond to a position i, j in the matrix by doing the same thing as the operation above. The &0xFF operation is a modulo operation. It takes the value of every entry modulo 256.

Hence, the original matrix M is transformed into this matrix (mod 256)

1
2
3
4


1 + 1 * 2               2 + 2 * 2               3 + 3 * 2                   4 + 4 * 2
5 + 14 * 2              6 + 15 * 2              7 + 16 * 2                  8 + 13 * 2
9 + 11 * 2              10 + 12 * 2             11 + (9 + 11 * 2) * 2       12 + (10 + 12 * 2) * 2
13 + (8 + 13 * 2) * 2   14 + (5 + 14 * 2) * 2   15 + (6 + 15 * 2) * 2       16 + (7 + 16 * 2) * 2

We know that the value in the matrix before the modulo is in the range of 0 to 255, which is indeed the range of value after doing the modulo 256 operation. Hence to retrieve the original values in matrix M, we need to find the positive value which belongs in the general solution set of the congruence.

For example, to retrieve the element at index 13 (in the flattened out matrix), we can do:

Note that the 8, 13 here refers to index in the flattened out original matrix, not the literal value 8 and 13!

$$ a = 13 + (8 + 13 \times 2) \times 2 \mod 256 $$ $$ b = 8 + 13 \times 2 \mod 256 $$ $$ \Rightarrow 2 \times b - a = 13 \mod 256 $$

Hence we can take the result of

$$2 \times b - a$$

and find a positive value that is congruent to the value of

$$2 \times b - a$$

, and that should be the value for 13

The first row is special as its value got tripled. To retrieve the original value is basically solving the linear congruence $3x = a \mod 256$. We obviously do know the value of a, and $0 < x < 256$, hence it’s very easy to derive the only solution to the congruence equation.

After we get the reversed (inversed) version of all the functions, the only work left is to apply those function in order and run for 30 rounds to retrieve the orginal message.

Solution Implementation:

  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


from Crypto.Util.Padding import unpad
import random 

SUB_KEY = [
    0x11,0x79,0x76,0x8b,0xb8,0x40,0x02,0xec,0x52,0xb5,0x78,0x36,0xf7,0x19,0x55,0x62,
    0xaa,0x9a,0x34,0xbb,0xa4,0xfc,0x73,0x26,0x4b,0x21,0x60,0xd2,0x9e,0x10,0x67,0x2c,
    0x32,0x17,0x87,0x1d,0x7e,0x57,0xd1,0x48,0x3c,0x1b,0x3f,0x37,0x1c,0x93,0x16,0x24,
    0x13,0xe1,0x1f,0x91,0xb3,0x81,0x1e,0x3d,0x5b,0x6c,0xb9,0xf2,0x83,0x4c,0xd5,0x5a,
    0xd0,0xe7,0xca,0xed,0x29,0x90,0x6f,0x8f,0xe4,0x2f,0xab,0xbe,0xfe,0x07,0x71,0x6b,
    0x59,0xa3,0x8a,0x5e,0xd7,0x30,0x2a,0xa0,0xac,0xbd,0xd4,0x08,0x4f,0x06,0x31,0x72,
    0x0d,0x9f,0xad,0x0b,0x23,0x80,0xe6,0xda,0x75,0xa8,0x18,0xe2,0x04,0xeb,0x8e,0x15,
    0x64,0x00,0x2b,0x03,0xa1,0x5d,0xb4,0xb1,0xf0,0x97,0xe3,0xe8,0xb0,0x05,0x86,0x38,
    0x56,0xef,0xfa,0x43,0x94,0xcb,0xb6,0x69,0x5f,0xc7,0x27,0x7c,0x44,0x8d,0xf3,0xc8,
    0x99,0xc2,0xbc,0x82,0x65,0xdb,0xaf,0x51,0x20,0x7f,0xc3,0x53,0xf4,0x33,0x4d,0x50,
    0xee,0xc5,0x12,0x63,0x9b,0x7b,0x39,0x45,0xa9,0x2d,0x54,0xdc,0xdf,0xd6,0xfd,0xa7,
    0x5c,0x0c,0xe9,0xb2,0xa2,0xc1,0x49,0x77,0xae,0xea,0x58,0x6d,0xce,0x88,0xf8,0x96,
    0xde,0x1a,0x0f,0x89,0xd3,0x7a,0x46,0x22,0xc6,0xf9,0xd9,0x84,0x2e,0x6a,0xc9,0x95,
    0xa5,0xdd,0xe0,0x74,0x25,0xb7,0xfb,0xbf,0x9c,0x4a,0x92,0x0e,0x09,0x9d,0xf6,0x70,
    0x61,0x66,0xc0,0xcf,0x35,0x98,0xf5,0x68,0x8c,0xd8,0x01,0x3e,0xba,0x6e,0x41,0xf1,
    0xa6,0x85,0x3a,0x7d,0xff,0x0a,0x14,0xe5,0x47,0xcd,0x28,0x3b,0xcc,0x4e,0xc4,0x42
]

ciphertext = "1333087ba678a43ecc697247e2dde06e1d78cb20d8d9326e7c4b01674a46647674afc1e7edd930828e40af60b998b4500361e3a2a685c5515babe4e9ff1fe882"
ciphertext = bytes.fromhex(ciphertext)

# test = random.sample(range(1, 255), 16)
test = list(range(1, 17))

mat = [[test[i * 4 + j] for j in range(4)] for i in range(4)]

def reverse_xor(block):
    order = [2, 3, 0, 1]
    for i in order:
        for j in range(4):
            block[i][j] ^= block[(i + 2) % 4][(j + 1) % 4]

def reverse_add(block):
    res = [[0 for i in range(4)] for j in range(4)]

    # Solve for third row
    res[2][2] = (block[2][2] - 2 * block[2][0])
    res[2][3] = (block[2][3] - 2 * block[2][1])
    res[2][0] = (block[2][0] - res[2][2] * 2)
    res[2][1] = (block[2][1] - res[2][3] * 2)

    # Solve for fourth row
    res[3][0] = (block[3][0] - 2 * block[1][3])
    res[3][1] = (block[3][1] - 2 * block[1][0])
    res[3][2] = (block[3][2] - 2 * block[1][1])
    res[3][3] = (block[3][3] - 2 * block[1][2])
    
    # Solve for second row
    res[1][0] = (block[1][0] - 2 * res[3][1])
    res[1][1] = (block[1][1] - 2 * res[3][2])
    res[1][2] = (block[1][2] - 2 * res[3][3])
    res[1][3] = (block[1][3] - 2 * res[3][0])

    for i in range(1, 4):
        for j in range(4):
            res[i][j] &= 0xFF

    # Solve for first row
    for i in range(4):
        c = 0
        while True:
            if (256 * c + block[0][i]) % 3 == 0:
                res[0][i] = int((256 * c + block[0][i]) / 3)
                break
            c += 1

    for i in range(4):
        for j in range(4):
            block[i][j] = res[i][j]

def reverse_sub(block):
    for i in range(4):
        for j in range(4):
            block[i][j] = SUB_KEY.index(block[i][j])

def reverse_rotate(row):
    row[0], row[1], row[2], row[3] = row[1], row[2], row[3], row[0]

def reverse_transpose(block):
    copyBlock = [[block[i][j] for j in range(4)] for i in range(4)]

    for i in range(4):
        for j in range(4):
            block[i][j] = copyBlock[j][i]

def reverse_swap(block):
    s = 0 
    for i in range(4):
        for j in range(4):
            s += block[i][j]

    if (s % 2): reverse_transpose(block)

    for i in range(3):
        block[i][0], block[i][1], block[i][2], block[i][3] = block[i][2], block[i][0], block[i][1], block[i][3]

    reverse_rotate(block[3]); reverse_rotate(block[3]); reverse_rotate(block[3])
    reverse_rotate(block[2])
    reverse_rotate(block[1]); reverse_rotate(block[1]); reverse_rotate(block[1])
    reverse_rotate(block[0]); reverse_rotate(block[0])

    block[0], block[1], block[2], block[3] = block[3], block[2], block[0], block[1]

def reverse_round(block):
    reverse_xor(block)
    reverse_swap(block)
    reverse_add(block)
    reverse_sub(block)

def decryptBlock(block):
    mat = [[block[i * 4 + j] for j in range(4)] for i in range(4)]
    for _ in range(30):
        reverse_round(mat)
    return [mat[i][j] for i in range(4) for j in range(4)]

def decrypt(ciphertext):
    ciphertext = list(ciphertext)
    enc = []
    for i in range(0, len(ciphertext), 16):
        enc += decryptBlock(ciphertext[i : i + 16])
    return unpad(bytes(enc), 16)

print(decrypt(ciphertext))

Cube

I managed to solve this after the CTF has ended. I decided to put it here since the team did spend quite a bit of time in this challenge without any progress. The challenge is solved using Fermat’s little theorem, or more precisely this equality

$$ n^{3^{2^{100}}} \mod p = n^{(3^{2^{100}} \mod (p-1))} \mod p $$

Plugging this, we should be able to retrieve the prime p, hence the flag.

Data Degeneration

This is a relatively simple challenge. The data in the data.txt is generated by doing samples on three normal distributions of unknown mean and standard deviation of 1.

We can plot all the values in the data.txt on a graph and observe the trend in the values. I sort them in ascending order so I can have a better visualisation of the value in the graph. The script for plotting is the commented out code in the solve.py file. Running the code gave us this graph.

We can clearly see the three groups of values on the graph, which most likely corresponds to the three different mean values used to sample them. Since the standard deviation is 1, the difference in consecutive sorted values in each group should not be greater than 1. The groups are more than 1 value apart, hence we can use this information to sort out the values in three groups, then calculate the mean value. Submitting the three mean values calculated should give us the flag.

Solution Implementation:

 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


import matplotlib.pyplot as plt
import numpy as np 

file1 = open('data.txt', 'r')
lines = file1.readlines()

arr = lines[0].split(", ")
num_arr = []

for i in arr:
	num_arr.append(float(i))

num_arr = sorted(num_arr)
index = [i for i in range(800)]
num_arr = np.array(num_arr)
# plt.scatter(index, num_arr)
# plt.show()

batch = [list() for i in range(3)]

current = num_arr[0]
batch_no = 0
for num in num_arr:
	if (num - current) >= 1:
		batch_no += 1 
	batch[batch_no].append(num)
	current = num 

for i in range(3):
	print(np.mean(batch[i]))

Equation

The task in here is straightforward, solve the two equations to get the value of m1 and m2. There is straightforward and nicer solution (kudos to Connor579 on the GreyCTF Discord) in the nicer_solve.sage file. Unfortunately, I did not know how to use Sage properly, as I do not find good answers from Google answering my queries about “solving the system of polynomials using Sagemath”, so I try to come up with a different solution to this. Solution to Equations-2 can be found in jontay999 writeup at this link or in the nicer_solve2.sage (kudos to joseph on the GreyCTF Discord).

My approach is to start from the smallest guest possible (numerically), since the smallest printable ASCII character is !, my base guess is a flag containing all !. I can find the length of the flag by keep adding more ! until the length of the result of both the equations matches the length of the given result. Doing this, I can find the possible length range of the flag, then later I can modify this “dummy” flag to different values of flag length to see if there is any result.

To determine if we are close to the targets (the values of the two equations) or not, we have a verify-flag function. The function first calculates the values of the 1st and 2nd equation with the flag specified in the parameter. Then, it matches from the most to least significant digits the number of characters that are matching from the targets and the two results calculated earlier. The more characters matched, the closer we are in getting the actual flag. The result is returned in the form of <1ST EQUATION RESULT>, <2ND EQUATION RESULT>. This is simply because the highest power in the 2nd equation is 5, which is lower than that of the 1st equation, which is 7. This means that the 2nd equation will be less sensitive to the result of the 1st equation, hence it is used just for tie-breaking, and mainly the result are compared using the 1st equation result.

To retrieve the flag, we do it with an intuition of “after each guess, the result should be improving and not worsening”. This is based on the fact that the value of m1 and m2 should be strictly increasing, as there is no smaller string (in terms of ASCII value) than a string populated with all !. Both the equations’ values are increasing as m1 and m2 increases. Hence, we need to adjust the values of m1 and m2 to increase if the values in the equations are smaller than the target, and decrease if the values in the equations are greater. I can do the implementation in this way, but due to the unreasonable fear of weird rounding errors when Python deals with huge number (which is not true), I stray away from this approach and instead uses a more roundabout way (but still somewhat based on that intuition).

Solution Implementation:

 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


from Crypto.Util.number import bytes_to_long

FLAG = b'grey{!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!}'

n = len(FLAG)
print(n)
m1 = bytes_to_long(FLAG[:n//2])
m2 = bytes_to_long(FLAG[n//2:])


a = "6561821624691895712873377320063570390939946639950635657527777521426768466359662578427758969698096016398495828220393137128357364447572051249538433588995498109880402036738005670285022506692856341252251274655224436746803335217986355992318039808507702082316654369455481303417210113572142828110728548334885189082445291316883426955606971188107523623884530298462454231862166009036435034774889739219596825015869438262395817426235839741851623674273735589636463917543863676226839118150365571855933"
b = "168725889275386139859700168943249101327257707329805276301218500736697949839905039567802183739628415354469703740912207864678244970740311284556651190183619972501596417428866492657881943832362353527907371181900970981198570814739390259973631366272137756472209930619950549930165174231791691947733834860756308354192163106517240627845889335379340460495043"

def verify_flag(flag):
    m1 = bytes_to_long(flag[:n//2])
    m2 = bytes_to_long(flag[n//2:])
    temp = str(13 * m2 ** 2 + m1 * m2 + 5 * m1 ** 7)
    count_a = 0
    for i in range(len(a)):
        if a[i] == temp[i]:
            count_a += 1
        else:
            break 
    
    count_b = 0
    for i in range(len(a)):
        if a[i] == temp[i]:
            count_b += 1
        else:
            break 
    return count_a, count_b

def solve_flag(flag, index, record):
    if index == n - 1:
        return [flag]

    candidate_max_flags = []
    candidate_max_count = (0, 0)

    for i in range(33, 127):
        possible_flag_prefix = flag[:index] + str(chr(i)).encode() + flag[index + 1:]
        count = verify_flag(possible_flag_prefix)
        if count > record:
            possible_flags = solve_flag(possible_flag_prefix, index + 1, count)
            if possible_flags:
                for possible_flag in possible_flags:
                    count = verify_flag(possible_flag)
                    if count > candidate_max_count:
                        candidate_max_flags = [possible_flag]
                        candidate_max_count = count
                    elif count == candidate_max_count: 
                        candidate_max_flags.append(possible_flag)
    
    return candidate_max_flags


print(solve_flag(FLAG, 5, verify_flag(FLAG)))
# 13 * m2 ** 2 + m1 * m2 + 5 * m1 ** 7 == 6561821624691895712873377320063570390939946639950635657527777521426768466359662578427758969698096016398495828220393137128357364447572051249538433588995498109880402036738005670285022506692856341252251274655224436746803335217986355992318039808507702082316654369455481303417210113572142828110728548334885189082445291316883426955606971188107523623884530298462454231862166009036435034774889739219596825015869438262395817426235839741851623674273735589636463917543863676226839118150365571855933
# 7 * m2 ** 3 + m1 ** 5 == 168725889275386139859700168943249101327257707329805276301218500736697949839905039567802183739628415354469703740912207864678244970740311284556651190183619972501596417428866492657881943832362353527907371181900970981198570814739390259973631366272137756472209930619950549930165174231791691947733834860756308354192163106517240627845889335379340460495043

We implement the guess function in somewhat “recursive” manner, guessing the characters at every index in the flag. The value of the flag we will be working on is the value passed from another call to the solve function earlier, containing the flag prefix. To narrow down the search space, the flag prefix should “improve” the guess, that is to improve the count metric. If count is not greater than the record from the earlier call, we are straying away from the correct flag, hence we should not use the prefix. If it is greater than the record, we use that prefix for the flag parameter in next call of the solve function, guessing the character at the next index of the flag string.

If there are results (possible_flag) being returned from the function call, we can run the evaluation function verify_flag again to get the guesses with the highest value. Then the possible flags are returned for the parent functions to use and evaluate against all the results from the other functions which use a different prefix.

The result from the function should be the flag, but we need to adjust the flag length to the three values as we do not really know the length of the flag itself. The correct length for the flag is 59, and running the script with that length should give us the flag.

This approach unfortunately does not work with the second challenge due to the nature of congruence function, we cannot really derive a relation between the increase/decrease of m1 and m2 and the result of the congruence equation.

Firmware

This is a digital forsensics challenge. We are tasked to find the file which load the firmware when a device is booting up. At first, I tried using autopsy to find things that are useful but after hours of trying to work it the u-boot format (you can see in the 3 files with the prefix of vol2-C) there is no way to retrieve anything useful from the three files extracted by autopsy. Doing strings does not really work (you can see in the strings.txt), and it only shows messages of what seems like log messages of a device booting up.

Hence, I encountered another approach to this, using binwalk. By doing binwalk -e firmware.img (automatically extract known file types), I managed to extract out what seems like a Linux file system (you can see in the folder _firmware.img.extracted).

I don’t really know what file to find from the hint given in the challenge, so I use a brute force approach to get the flag. Using grep -r grey ., which basically search for the string grey in the content of all the files extracted, we should be able to retrieve the flag.

Flappy-js

This is a RE challenge in the web category. We have to reverse the logic of the game or find the function which produce the flag for us. Upon inspecting the page using Sources in the Chrome Developer Tools, we see that there is JS files in the js and build sub-directory. This does not contain anything useful to retrieve the flag, most of it is the source code to power the game. However, looking at the build folder shows something very promising to the flag.

However, the script is flattened out so we can do some beautifying for the sake of better analysis. Beautifying the script there using the Javascript beautifier

Scrolling through the code, we can see that this is some sort of configuration file for the game itself. After scrolling we can notice an interesting function named genFlag - which should be related to the generation of the flag itself. The portion of the code that contains the genFlag function is in the picture above.

To get the flag, we can open up the Console using Chrome Developer Tools, copied the definition of the function, then run it to retrieve the flag.

Ghost

This is quite a tricky challenge, as I thought initially this challenge is about finding out what’s the encoding scheme behind all the messages. Using dcode, we can easily identify the encoding used in the visible text. However the messages’ content are mostly gibberish and do not contain any clues to the actual flag.

There are no signs of any hidden alternative data streams (ADS) or anything hidden in the file. Hence, the file’s actual message is hidden using steganography. Bolding the entire file shows some very peculiar trends.

The message is hidden using white space steganography. The . in Sublime means that there’s a space, --- (the long dash) means that there’s a tab character.

From researching on how to solve this, I encounter one video from John Hammond on Youtube. Modifying the Python script in the video and set the value of a space to 0, a tab character for 1 should give us a binary message that we can plug into Cyberchef and use the Magic function there to retrieve the flag.

Solution Helper Implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


import re

file = open('ghost')
c = [x[:-1] for x in file.readlines()]
file.close()
flag = []

for line in c:
	num = re.findall(r"(\s+)", line)
	if num:
		num = ''.join(num).replace(' ', '0').replace('\t', '1')
		print(num)


print(''.join(flag))

ImageUpload

This challenge is about inspecting a network dump from a Wireshark dump file. Opening Wireshark to analyse the dump.pcap file, we can filter out the http protocol (as image uploading is essentially a POST request to an endpoint).

Inspecting the POST request, we should see the content of the flag in the Textual data recorded in the payload.

Logical Computers

Aliencaocao from Hwa Chong has an awesome, and in my opinion, more “intended” solution. You can check out his writeup at this link. My solution does not really involve the Math like his, but it is based on an intuition that I have doing a bit of work in AI/ML in general.

We can see that the network consists of two linear layers, and have a step activation function in between. This, combined with the fact that there’s only one flag to any challenge in the CTF, suggest that for the classifier to output a 1 (which is the condition to get the flag), we have to guess correctly the character in each position of the flag. This may seem very obvious, but it is the key observation to establish to solve the challenge. The network’s parameters are loaded from the model.pth file.

The tensorize function converts any character in the string into a 8-bit format. That, combined with the fact that the model requires the input size dimension to be 160. We can very easily verify this by typing in a random character like “A”, and an error of RuntimeError: Error(s) in loading state_dict for NeuralNetwork: size mismatch for layer1.weight: copying a param with shape torch.Size([1280, 160]) from checkpoint, the shape in current model is torch.Size([1280, 8]) should come up. This suggests that the length of the flag is 160 / 8 = 20 chars long. Hence, we can easily have a dummy flag of grey{~~~~~~~~~~~~~~}. This dummy value can be whatever we want, as long as it is 20 characters long.

We noticed that there is a step_activation function at the end before outputting, and this obviously destroys much of the information from the Linear layer earlier (as it converts any value greater than 0 to 1 and values smaller than 0 to 0), hence in the solution we can remove that to retain more information in our search.

From the observation earlier, we have to guess correctly the characters of every position in the flag string. My evaluation (or intuition here) is that for each index in between the two {} sign, the closer we are to the real ASCII value of the character of the flag in that index, the closer to 0 the value after layer2 of the network becomes. We can easily verify this by modifying the ~ to any ASCII character just after the { in the flag to see. In general, the closer we are (in terms of ASCII values of the characters), the higher the value after the layer2 Linear layer. Note that closer here means that every character in other positions (the ones we are not guessing currently) are not modified. This is crucial as it ensures that the comparison makes sense, we can’t really compare strings that are different from each other in different positions. For the comparison to make sense, every other character should stay constant aside from the character we are guessing.

Hence, my approach is that, for each index in the flag, we iterate through all printable ASCII characters (33 - 128), plug the guess at that position into the model. The character that yield the highest value after plugging into the model should be the flag character at that specific position. We do that for every character index in the flag.

Solution Implementation:

 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


import torch

def tensorize(s : str) -> torch.Tensor:
  return torch.Tensor([(1 if (ch >> i) & 1 == 1 else -1) for ch in list(map(ord, s)) for i in range(8)])

class NeuralNetwork(torch.nn.Module):
  def __init__(self, in_dimension, mid_dimension, out_dimension=1):
    super(NeuralNetwork, self).__init__()
    self.layer1 = torch.nn.Linear(in_dimension, mid_dimension)
    self.layer2 = torch.nn.Linear(mid_dimension, out_dimension)

  def step_activation(self, x : torch.Tensor) -> torch.Tensor:
    x[x <= 0] = -1
    x[x >  0] = 1
    return x

  def forward(self, x : torch.Tensor) -> int:
    x = self.layer1(x)
    x = self.step_activation(x)
    x = self.layer2(x)
    return int(x)

flag = "grey{~~~~~~~~~~~~~~}"
in_data = tensorize(flag)
in_dim	= len(in_data)

model = NeuralNetwork(in_dim, 1280)
model.load_state_dict(torch.load("model.pth"))

def get_flag(flag):
  best_score = model(tensorize(flag))
  best_candidate = flag
  for i in range(5, len(flag) - 1):
    for j in range(33, 127):
      temp = best_candidate[:i] + str(chr(j)) + best_candidate[i + 1:]
      score = model(tensorize(temp))
      if score > best_score:
        best_score = score 
        best_candidate = temp
  return best_candidate

print(get_flag(flag))

Memory Game (Part 1)

This challenge is about finding where the image assets are stored. We can extract the original structure of the apk file by using apktool d memory-game.apk. We get the data that is in the sub-directories assets, original, res and smali of this folder.

It is more likely that the picture is stored in the assets folder. We can manually search all the folders to check the content of each image there to see if it contains the flag. Or there is a nicer solution which involves a bit of guessing - we guess that the name of the file containing the flag should be in the form of flag., so we can use find to find the location of the file. Opening that location should give us the content of the flag.

Parcel

Using file to analyse the file, we do know that this should be an executable but it is packed using a packer we did not know yet.

Inspecting the file using strings, we can easily see the UPX! which indicates that the file is packed using UPX.

Hence, we can unpack the file using the command upx-ucl -d parcel, then do chmod +x parcel to make the file executable. Interacting with the binary, we can see that it requires us to provide the value of the address of the three functions

Using gdb, we can find the address of the functions by using disas <FUNCTION>

Permutation

We are provided with three files, main.py, out.txt and perm.py. out.txt is the result of running main.py, perm.py is used as the permutation library used for this challenge.

The main.py encrypt the FLAG using xor with the secret generated from the digest of shake_256 method using the value from the key. Hence, to decrypt the ciphertext, we need to retrieve the key.

The key is generated at the A ** b call, and we are provided the value of the generator g, A and B. To get the value of the key, we need to figure out the value of b.

To derive the way to retrieve the key, we should first take a look at the perm.py file and see how the Perm class operates.

First, upon initialization, there is a check to see if the arr used is valid or not. The valid check is simply to check if the array is indeed an array of consecutive integers starting from 0 or not. The multiplication operation is done by first checking whether the size of the two arr inside the two Perm object are of equal sizes. Then, for every i in the other list, we append to the res the value of its internal array at position i. This achieves the “permutation”, as the validity check from earlier ensures that the integers are consecutive, and the size checking ensures that the mapping from the original to the modified array is one-to-one.

We don’t really know for sure at this point how the pow function works, hence we can test this functionality on a smaller set to see if there is any pattern. We will create a test.py script to test some of our observations. Note that some of the tests here can be skipped if you understand what’s going on in the implementation of pow. When I did this challenge, I have zero clue what the bit shifting is doing so I did these tests to confirm some of my hypothesis which leads to me solving the problem.

First, we want to test whether the equality g ^ n = g * g ... * g (n times) holds. Of course we can’t really “prove” this with code, but let’s test some of the values and see if it holds. This indeed is true.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def first_test(g, n):
    res = g
    for i in range(n - 1):
        res *= g 
    print(str(res) == str(g ** n))

first_test(g, 3) # Returns True
first_test(g, 329394) # Returns True
# You can plug in the g given in the out.txt
# and this should hold for any n

Hence, what the pow function really does is just a convoluted (but very efficient! way) of powering, but it is still similar to powering using the standard way of doing g * g * g .... Knowing this, we can look at the code again to verify, and it does work in that way 😄

Second, we need to check if g ** (a + b) = g ** a * g ** b holds. We can easily proof this, simply by expanding the three powers, of the form g ** n into the g * g * ... * g * g form.

Third, we want to see if this is cyclic. Cyclic means that the value is repeated after some n times of multiplying. This is useful, since if this is true we do not really have to figure out the exact value of b, we can find a smaller value to replace it.

1
2
3
4
5


def third_test(g, n):
    for i in range(1, n):
        print(g ** i)

third_test(g, 20)

The result indeed confirms this is cyclic, as it repeats after a certain number of cycles. In the picture, the cycle is 12, as after 13 (4 + 1) times multiplying itself, the original array becomes itself again. This property holds for any array in the cycle set, like the value of the 2nd array is found at the 6th index again.

Test script

 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


import perm 
import random 

arr = [i for i in range(12)]
random.shuffle(arr)

g = perm.Perm(arr)

# FIRST TEST
def first_test(g, n):
    res = g
    for i in range(n - 1):
        res *= g 
    print(str(res) == str(g ** n))

first_test(g, 3) # Returns True
# first_test(g, 329394) # Returns True

## THIRD TEST
def third_test(g, n):
    for i in range(1, n):
        print(g ** i)

third_test(g, 20)

# THIRD, ADDITIONAL TEST
# VERIFY IF g ^ n = g ^ (n + cycle)
def find_cycle_naive(g):
    cycle = 2 
    while True:
        if (str(g ** cycle) == str(g)):
            return cycle 
        cycle += 1

cycle = find_cycle_naive(g) - 1
print(str(g ** 2 * g ** cycle) == str(g ** 2))
print()

# FOURTH TEST
g = [9, 7, 2, 1, 3, 6, 5, 4, 0, 8]
g = perm.Perm(g)
cycle = find_cycle_naive(g) - 1
print("Cycle:", cycle)

for i in range(cycle + 1):
    print(g ** i)

Fourth, upon a closer look, we can see the value in a cycle of the first index, the sequence 7, 6, 10, 0 is repeated. This seemingly is the case for values in other indexes as well. Since we know that there is a cyclic property in the powering of the array here, and there is seemingly a sequence in each indexes as well, should there be a relation between the two? To see this trend clearer, we can use a smaller example of array of length 8 to see.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


# FOURTH TEST
def find_cycle_naive(g):
    cycle = 2 
    while True:
        if (str(g ** cycle) == str(g)):
            return cycle 
        cycle += 1

g = [9, 7, 2, 1, 3, 6, 5, 4, 0, 8]
g = perm.Perm(g)
cycle = find_cycle_naive(g) - 1
print("Cycle:", cycle)

for i in range(cycle):
    print(g ** i)

Everything is much clearer now, we can see the sequence 0, 9, 8 repeating in the 1st index. Another peculiar thing that we can see is that the sequence 0, 9, 8 does appear again, but starting a bit differently in the last (8, 0, 9) and next to last index (9, 8, 0). The length of the sequence is 3, and the length of other sequences are 4, 1, 2. It is suprising that the LCM (Least Common Multiple) of 3, 4, 2, 1 is 12. Interesting.

We can test this on different ordering of the original array, and even different length as well, and the result will still be that the cycle is dependent on the least common multiple of the length of all the sequence in every index of the array. Hence, a better, smarter way to find the cycle of the array can be written.

We notice that, just after the original array is repeated (last array in the cycle). It takes 11 multiplications to get there. If we check out the position of the elements in the cycle, for example at the 1st index, we can see that the 8 is actually the final element in the sequence 0, 9, 8. Similarly, for index number 2, 3 is the last element in its sequence of 1, 7, 4, 3. 11 divides 3 has a remainder of 2, and 11 divides 4 has a remainder of 3. It seems like the remainder of the index of an array in the cycle, divided by the length of the repeating sequence at any index i of the arrays should give the exact position in the repeating sequence of the i-th number in the array. We can easily verify this by writing our own function to find out the cycle a bit “smarter” now. For the sake of length I decided not to include that here, as this is already implemented in the actual solution.

And it seems like the reverse is true, if we know the position of the array ith element in the repeating sequence, we can derive the index of the array in the cycle using Chinese Remainder Theorem. This can be tested using the makeChain method in the solve.py file, which returns the repeating sequence in every index of the array. We get the index of the array in the cycle by first find the length of each “chain’ (repeating sequence), then find the “remainder” by finding the index of each element in its “chain”. Finally, we apply the Chinese Remainder Theorem to retrieve the result.

Using all these observations, we can finally use this to find out b. Finding out b is the same as finding the position of B in the cycle, given the generator g. After retrieving b, we can get the original S that is used to generate the key by doing A ** b. A simple xor with the given key should be enough to get the flag.

Solution Implementation:

  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


from sage import *
from hashlib import shake_256

class Perm():
    def __init__(self, arr):
        self.internal = arr
        self.n = len(arr)

    def valid(self, arr):
        x = sorted(arr)
        n = len(arr)
        for i in range(n):
            if (x[i] != i):
                return False
        return True

    def __str__(self):
        return ",".join(map(str, self.internal))

    def __mul__(self, other):
        res = [self.internal[i] for i in other.internal]
        return Perm(res)

    def __pow__(self, a):
        res = Perm([i for i in range(self.n)])
        g = Perm(self.internal)
        while (a > 0):
            if (a & 1): res = res * g
            g = g * g
            a //= 2
        return res

def xor(a : bytes, b : bytes) -> bytes:
    return bytes([ x ^^ y for x, y in zip(a, b)])

g = [4848,653,2856,3641,3271,4609,4387,2211,3537,2415,2049,2571,2877,3588,2002,4488,2086,2795,2880,4000,1341,838,520,478,696,2390,1380,1132,2871,3056,4990,3631,2442,4366,2814,1976,4565,4884,135,2271,3913,1517,4100,2716,3432,2066,1558,4407,1019,3135,4228,195,3936,2569,502,2678,4320,4633,1387,764,3032,1257,1427,24,4286,2425,185,4097,4410,3776,451,4,2205,1216,1839,2789,1609,1332,2843,78,546,1920,3239,1753,2148,558,1648,2269,1561,3591,457,65,38,3030,993,2031,710,680,1253,2578,1898,3923,4039,2777,4161,4456,2944,3238,2067,1174,3993,1245,3721,4680,1311,1375,2234,1964,1572,4174,308,2176,2668,2085,505,2206,3045,3251,4979,3701,5,2162,4489,39,2953,3689,1087,2863,4480,1096,3790,1758,2594,180,233,2546,3333,935,358,243,4421,4652,1414,4482,821,3082,2835,456,2781,1356,3111,1709,1419,2025,1885,1507,4777,1514,424,4079,475,759,938,403,878,1259,2343,1944,3438,1191,1603,1542,618,4836,4462,1887,212,4354,2454,3854,3426,392,3074,3874,2810,2555,3623,4664,1792,1698,3370,1344,455,4058,2386,3038,3585,2217,44,3189,4426,3066,2667,1260,3043,2527,2240,570,4268,2700,4898,892,780,1448,4367,1399,1858,2682,4697,1009,3804,1050,777,204,2839,1351,1919,630,4781,2729,3860,1755,2169,3690,784,3429,2963,3311,1287,4758,4903,2439,1266,3656,2165,1282,3624,834,4033,4812,472,126,2930,3725,4155,3136,4972,156,3629,875,1295,3279,2657,1827,1357,2506,4104,3997,4578,1943,3493,3740,2647,2150,2247,3555,3771,2357,2601,4549,2427,252,1937,2665,319,1659,289,1578,4670,1503,2945,1869,2175,3978,1381,726,2607,1570,3376,4049,437,1250,1747,1855,4183,4636,4403,3148,4397,3185,1779,1263,286,1472,4271,2708,196,4375,1860,1068,4433,700,4253,2596,1533,1911,2532,2249,1912,665,795,4377,298,2913,2489,3039,3265,4815,1095,2984,644,3575,797,310,0,3285,476,1069,3224,3118,1158,312,3377,2630,2272,3435,3059,1407,3276,4611,4681,2664,2082,948,4894,4330,160,1536,3403,3190,3901,76,393,1162,1832,1675,3329,1771,2304,2940,4471,1061,2185,2001,3863,4743,1512,2670,1719,2833,3606,2394,1762,1693,1901,3851,4164,2901,2095,657,2702,1256,4294,3425,1123,2891,3389,4666,2544,1413,2725,4610,1584,221,129,984,2690,2705,531,3203,2320,2334,3146,3625,4084,1878,3486,3748,928,4641,4544,2256,1214,2530,4842,3599,3549,1914,4412,4768,774,4394,4216,449,3269,3261,842,1277,3330,3391,4304,17,701,3401,3697,4529,2735,4813,2710,2845,2434,2005,359,2491,3396,66,743,4938,1331,2844,1851,2130,2960,4619,2199,3105,1025,3497,3466,4886,2181,585,840,1215,3596,2337,4448,3506,908,3159,2688,3604,2853,3950,3550,3742,2147,4522,3603,3885,1422,4072,1834,2101,4766,725,1975,3921,1236,1078,2809,3672,3754,807,4673,3362,1607,3033,1402,4592,1374,2634,4739,4663,2545,2878,567,3331,1141,2015,775,3985,656,4077,1987,150,1166,408,4707,4291,4507,3955,2400,3327,3818,507,4811,805,4217,3833,2788,381,3817,335,445,4732,3857,2125,2335,4706,1870,2168,770,590,1415,2976,572,1629,2416,3931,4486,1369,2675,2462,3734,3933,521,2289,639,3809,3957,3982,728,1921,1998,2859,1248,3154,1041,1418,4965,4075,2561,71,3508,215,3590,4770,452,2924,1479,484,36,1233,4212,1534,4724,599,4927,1587,902,4751,2648,1981,1965,4475,4301,3275,4608,369,4280,4866,557,509,4984,4134,3223,3731,25,2098,2443,4091,2698,635,3988,2568,1645,4632,1186,169,2965,1787,2108,1055,2122,612,3816,3775,2917,490,2474,4555,3287,1866,2058,4030,4413,1103,4992,879,3266,3095,4661,4926,4209,2799,2344,4942,1881,2730,3867,1611,3186,2602,3696,3611,731,2241,4716,3115,2417,964,206,3309,112,1689,682,4146,3183,3760,3695,580,750,2677,3088,2618,860,4912,1574,4511,1820,469,4881,1378,4518,1439,1813,2551,3678,2063,1661,1777,1748,1199,2870,3498,3317,1715,4892,3344,1589,4220,2359,539,2327,4490,4143,1958,2529,2783,145,733,1734,1426,3928,3728,2091,2693,1928,1421,3499,1531,2118,1676,4786,1674,3090,4617,4376,1108,2405,2468,2449,2910,2161,2431,4740,1354,4055,3745,3942,171,547,4659,1591,4350,2105,3202,1550,439,929,1143,2847,1915,2061,1274,434,2509,4701,626,2691,2316,1963,4308,3773,4999,2654,931,4178,1431,4919,4635,1960,3958,223,2378,1516,2283,705,4789,378,610,3099,1182,674,4959,1464,4096,4363,4269,976,1798,4130,259,1417,3849,4364,932,497,2305,4295,4890,3152,2841,2915,2212,4333,3831,54,4821,262,4692,1288,2825,1775,1599,1161,2221,4218,654,416,4830,1089,3875,219,3476,995,1491,3479,228,2867,4107,946,2770,825,3001,3521,1154,3484,3368,3781,2420,2671,4310,4270,4262,2786,2488,631,4180,197,4582,1347,4531,2662,375,1031,2638,4411,1718,1955,806,3919,2516,3335,1527,3393,1113,2989,3991,1678,184,1016,1231,4957,4626,2401,3632,1886,3053,3801,2070,2414,4179,1035,2057,3325,4698,3735,1784,4838,724,2848,583,4855,863,2656,3989,4323,2140,4946,3782,3277,730,4598,1656,1197,2991,571,1515,79,2347,1097,3577,3205,742,3461,4108,1528,1303,3354,1594,4150,985,2591,1681,2353,3016,2590,4040,4839,3057,609,788,1447,2748,3474,1410,2381,4622,1330,1873,362,1112,3027,4941,1424,564,3206,1665,1720,1325,3042,4063,2655,2909,2096,3406,3706,1600,131,1823,3732,3986,869,4837,2738,1706,1302,4353,384,1416,1702,57,603,749,3411,4054,1812,108,2876,1102,1307,960,225,3727,1321,3927,4643,4379,4073,4891,3595,3714,1871,3894,30,2922,4020,2450,793,2440,712,3332,3363,4414,561,720,3788,737,2775,822,769,1815,2032,1716,554,3292,1352,3237,1460,783,317,4035,3981,1264,2324,4593,1312,1582,4093,3460,1368,2621,2995,818,853,10,919,3124,2388,2029,4550,4647,1085,885,2862,1121,3948,3597,2525,926,2920,3168,4774,1099,370,738,3,1942,4195,422,1064,4683,3163,1433,1376,4510,4760,3845,4684,338,444,1907,170,1028,3346,3054,1348,4961,3827,14,2487,2429,1267,4729,4954,361,1897,756,3259,3028,4439,3647,956,4362,504,2696,2890,1127,4450,3581,2921,1060,3992,996,4272,3013,3912,485,3225,4380,4028,800,2651,3541,1843,90,4849,2075,4623,1913,3996,723,901,1729,2908,4590,4498,2364,3640,4276,4136,3538,137,3786,2894,2720,226,4896,3808,213,727,3896,3195,4157,3855,4491,1449,1733,4915,4964,2625,1310,3009,1778,3509,2036,2035,1443,3139,1696,1822,98,1725,3207,3091,3807,1540,4762,3953,3844,4589,328,2358,3584,744,3613,785,707,379,31,3783,4153,2484,3659,2865,2133,3245,2806,373,1631,1100,934,1301,3453,2998,862,884,3554,4634,1210,1795,4757,4893,997,2160,4335,309,2803,3500,1160,3458,2550,2707,4064,1657,4187,3553,1212,855,1712,4586,3489,856,133,1768,4062,4735,2055,950,3084,4975,4118,541,4828,1034,1222,4010,2972,2572,3548,3428,3019,3400,1010,4162,19,2874,179,4485,56,2024,2034,4914,287,2121,4001,3101,1451,2361,4024,2762,343,3188,2575,1268,2717,4560,2864,4546,94,2553,1269,258,4901,949,3571,773,3404,360,4688,257,3227,2549,3677,1722,595,4763,1305,293,3876,2584,3880,703,3068,762,2192,3217,1652,524,4352,4447,3134,3427,4968,989,2943,4102,4869,203,3097,4538,3910,1098,3694,3995,2854,1726,3246,2538,273,1637,2312,1765,640,2306,3785,1196,4967,3208,2172,2467,2992,2861,2663,119,4037,2771,2704,1178,235,3752,1220,1797,3150,3336,1299,4267,4615,1039,1499,799,3255,2128,3254,1129,345,4382,4769,998,2321,1593,2295,1799,2699,4105,3345,2985,2626,2008,4939,2659,246,2556,2897,3116,2113,2533,253,2223,3934,4722,3709,4705,41,1966,492,2967,3318,3530,3947,1071,2230,1149,4922,227,3602,3861,897,2,201,3932,4406,2737,389,142,3418,953,1846,4432,4057,986,684,4461,3736,4240,1202,1573,734,4435,4213,1181,4596,914,1308,2822,2802,977,2925,2297,3085,3240,3838,1389,1837,4186,1817,3525,3546,1547,3886,3905,2323,1200,1566,4604,836,4188,4347,236,4203,4865,4175,2403,4998,676,1774,4602,1738,4715,450,1732,2087,2608,4258,3328,3598,912,2661,503,3777,3517,4665,1764,355,4419,1662,4816,4201,2811,3048,4851,1317,1806,3077,91,2280,4293,1953,2222,4297,1750,1457,4144,3210,3170,189,4759,2941,1137,194,1453,3348,1613,2896,3539,4754,2322,2852,2947,994,1522,2214,894,1469,3970,543,2286,1232,4446,399,2501,4503,911,2892,2194,4163,3579,264,4227,3534,1289,4519,4982,2076,763,2250,50,1442,3440,4080,1217,2518,606,2251,3568,722,2243,459,2384,3350,4288,486,1876,4971,4783,4527,1628,4230,2298,20,3450,1476,4317,1384,3826,480,2793,183,4612,2074,870,111,1249,2229,1848,4895,1838,3711,3058,4631,3192,3583,1462,3094,467,4944,3898,3395,2481,3029,2932,1111,4750,3676,2155,2187,427,1673,896,947,3757,1788,4814,3072,1688,787,4013,3297,2633,3409,877,442,4829,1211,4002,815,1770,3540,4165,481,499,1626,718,2579,1646,584,33,4504,1511,715,2026,2595,4648,3655,874,3235,4986,4655,2123,1179,4244,2437,2637,823,2252,3561,4780,4474,3969,4693,4923,3087,1523,2373,2519,3355,3171,1610,2064,3386,155,16,4314,857,2264,4606,2315,4337,1811,2131,3067,1272,2224,3229,2171,4117,1412,237,3172,1072,2404,597,2452,292,3813,3558,4137,4385,1927,4526,419,3902,3850,1918,786,1686,3300,2045,1487,2782,428,4156,53,1293,4699,978,209,473,4613,446,2823,2459,178,2981,2827,3600,1329,4265,4449,2311,1882,488,3278,2273,1537,2430,4420,3724,4234,1697,265,3286,632,1475,2114,1874,2179,3151,3520,154,3791,888,1577,4554,4355,3653,1118,4575,3065,3197,2582,2395,3634,294,4307,966,3917,2318,827,4741,4226,4646,2329,2893,4283,1463,4564,1849,4004,371,4523,4443,1175,4068,4141,4696,4388,4465,2139,363,4512,4685,239,4019,1052,42,791,3930,2144,3566,4850,4723,4717,2444,589,3011,2469,1012,4172,3310,2929,4219,658,4138,729,3654,2470,1664,2018,3012,2203,2314,1793,139,4567,4088,1152,2237,1397,4989,176,1489,2797,920,1847,1710,2385,3819,1120,3130,1833,1940,540,1456,2069,3182,1875,3873,3234,3213,2038,2363,1530,925,4940,4817,3837,2191,2513,2942,3449,638,2987,1776,4825,468,4065,1339,4470,2541,2369,1004,3903,3282,84,211,2198,2946,1830,354,2332,454,781,945,4431,4398,2531,1644,3664,4238,2510,2495,667,2731,3908,1859,4029,3545,122,2918,3294,2377,105,3935,1821,168,1471,4026,1555,3375,745,2585,4129,1556,300,2712,2056,100,3050,4856,527,768,681,1957,3666,3610,172,1177,2120,4807,2497,652,3879,3156,1405,741,3025,1800,2627,315,3592,4192,812,1841,4584,4749,3536,801,1667,2903,3420,3578,2958,3306,2302,4867,4515,1481,4171,483,4788,4835,2021,218,1641,3882,3044,3869,1910,4668,4587,1632,274,2333,2428,980,188,4289,113,1745,808,4625,972,4847,4858,1861,2348,2836,3469,4672,86,3507,1079,642,4167,4254,4846,2681,2422,2523,1091,591,3312,2387,224,2980,1080,1772,4386,107,425,4334,2227,3413,1569,4223,4348,1495,3770,4113,1865,4041,336,2196,716,2379,4484,2225,650,2116,2900,2733,305,2907,2485,2346,955,3036,2954,4365,4854,858,3564,778,3840,913,2912,318,530,1836,3456,3716,4247,4806,4140,4360,3829,981,2994,3295,623,2902,4810,4408,3228,4650,2916,3232,2391,4047,3128,4753,3888,887,2177,4210,2971,698,1809,1684,4468,581,1612,47,272,4745,2174,3392,3343,2310,2371,3262,2100,1880,2931,817,1192,2255,3759,3967,1093,3679,659,3842,2905,3046,907,1074,2494,1148,3015,1804,2195,83,3384,4883,1978,4514,2238,2842,496,2576,1042,3442,2728,3361,3359,3488,3764,1008,3369,2973,3075,1066,1614,3881,2111,835,465,271,2884,104,3747,276,2436,2099,1605,4702,421,458,2689,2102,1488,4844,2792,1529,159,3236,1714,2375,3107,2752,313,3800,2062,3737,3868,2461,1565,1017,2686,1749,3383,538,4402,45,4135,3778,2146,1204,982,529,4832,2599,3465,1780,525,1128,3382,279,695,1535,1450,4273,3779,1088,1968,3022,4899,3096,2766,380,2408,1630,3794,3121,627,1130,3342,4319,3698,3380,2412,1366,3447,4947,1746,3975,4170,3705,1049,464,1891,3938,2107,2317,4718,4802,873,430,1526,2758,2053,125,3494,1067,1187,4500,4292,4472,3402,556,2492,3319,3862,2715,3744,2816,1,3093,1429,1597,4250,2552,921,1829,2372,2262,3531,534,1271,4521,2210,607,2526,1623,1508,3681,3263,4368,1403,526,1131,4341,3040,2258,1185,3307,4252,4205,1058,820,1239,1474,760,648,4303,4454,1979,2397,3637,2215,2071,3472,4374,3983,3864,1227,1107,4764,4630,1640,1461,4545,303,3915,2711,3528,3638,3618,2926,1682,3645,280,1045,2419,510,1786,2622,2787,516,2642,3431,2977,3562,4284,2887,281,2135,4994,4396,3601,2435,617,4863,3000,3710,1122,2882,2617,2398,3244,248,2451,3274,4963,136,3351,2207,4936,3157,3161,578,2592,2472,365,2039,988,4204,802,2193,4071,1916,2986,4103,2616,4691,3073,4539,438,1169,1685,1251,2421,1962,2236,3964,199,4973,1478,3582,1506,1789,4185,4690,240,2962,4532,3064,506,4547,405,4911,1165,1007,2325,75,4249,3945,245,290,46,1313,4194,3122,2605,3198,74,4417,2961,1201,4202,4597,2392,1176,1134,2886,2888,4229,1794,3974,2072,1653,26,3385,2821,708,4313,52,568,1950,2340,859,889,1168,3303,132,1934,2136,463,2301,4494,2574,3622,4864,3352,4805,3231,1580,3439,2368,3113,4533,1428,3574,2949,3407,3959,3454,688,2170,4645,2757,231,1077,27,2423,2939,3769,4235,326,4945,1452,3683,35,158,2817,3132,3675,4464,3143,3283,391,4773,4929,4159,2360,1082,49,2138,1053,182,3937,3464,690,2017,3211,4541,3821,2957,207,4225,3491,3839,4189,1279,394,3729,2653,4969,4726,4826,3063,2336,1567,3201,629,4208,3780,357,299,4654,3349,2673,3324,4044,2866,660,1585,3692,872,4714,2517,1740,4951,1980,2239,491,3002,1532,4036,563,832,353,4804,3700,4261,1133,4879,905,2244,3906,3884,80,4675,2476,222,4131,2080,4920,596,2732,2772,60,1172,4905,602,683,409,826,302,4988,2760,296,429,2566,1997,4908,968,2382,3296,3399,23,1902,4803,3899,4018,1557,2703,3994,2623,2643,4281,4524,2790,55,1906,2399,3422,3098,2426,3668,4349,1000,3478,1909,1983,4746,2127,2636,2291,2183,4083,3104,871,4493,3252,1647,3726,4809,3526,1872,2955,4005,2914,2970,2296,4346,670,3815,3337,8,4605,4199,2632,4287,4060,3242,190,1371,4917,3267,2460,2969,3193,560,1346,4841,395,164,3006,792,752,151,1946,1548,1335,3501,2307,447,157,2143,2658,4583,4639,2858,1825,93,4981,2115,88,1013,2580,1337,1895,983,1318,284,3738,904,4373,4090,2567,677,4875,1193,3756,2319,3658,3079,1883,2706,2355,2356,2503,4133,939,3060,2050,4797,2535,882,4853,4260,4336,495,3191,1844,4517,3984,2767,4868,4506,29,1228,1437,500,4257,3017,1683,1003,3167,2254,4436,4121,4785,1862,2465,1446,3081,4719,990,1395,435,699,2834,1388,4069,714,2784,181,1904,3177,443,1498,2537,2052,3644,1467,4860,4078,3284,4182,152,4404,4128,651,1554,2978,2993,1562,2471,2486,3519,3979,1982,6,2042,4263,3340,1754,4256,1244,4618,3031,3922,3334,942,3233,4918,366,3512,144,1340,2393,959,2059,3713,1292,1139,881,2380,4207,3338,2044,1116,4725,1322,824,1521,3702,3516,115,4799,1338,2860,3037,3187,4200,406,1252,4115,1283,1298,1170,3646,4211,321,2342,973,2563,1342,268,2796,3799,2496,692,3055,3007,3811,2534,1598,3715,1596,3158,4038,1349,4505,4338,13,2645,3076,1090,641,3470,410,1781,4900,4801,3848,2004,2660,3649,2090,1024,2988,4943,1935,3308,62,4151,2154,4502,3877,2167,3444,4733,1974,2089,3218,4290,2505,2562,337,4149,3795,4676,4034,4101,2274,693,2606,579,794,334,1275,4487,3347,4556,2692,2559,1392,2997,2641,4708,146,1070,895,61,706,397,1595,4120,4614,4196,4243,1890,3357,943,3998,4371,4682,614,4551,4956,924,691,117,2713,1852,1494,4166,1831,3642,4023,2409,4003,2620,4616,368,4255,390,4906,3789,1159,1785,324,2685,4045,3119,628,2351,1625,1757,890,2190,2413,138,4985,685,4076,166,3535,662,1157,1691,2366,4006,238,4009,2846,4424,401,1721,1853,636,1986,1773,1704,3388,81,4215,2245,3164,2749,2433,3305,1842,753,4015,4302,1672,1972,460,3806,1382,3542,2593,933,432,841,1218,3089,2149,4980,1432,1438,4874,1401,4274,2736,3140,2560,4236,2330,11,2948,899,3441,1984,3977,1929,3166,2010,1818,15,1655,4913,1081,3669,2840,2188,910,1766,1819,2432,4771,843,4910,846,2818,2279,2455,906,1509,517,900,2186,241,2938,2341,3120,1189,134,2242,1188,1931,2719,4369,1183,277,2124,220,2267,1001,3614,266,542,3954,4309,3457,1930,3911,2612,1877,234,4142,2226,1230,1695,2764,3437,3972,4720,1180,1225,275,4761,4415,1723,2547,2697,1334,4056,4833,127,4123,1365,177,2990,1952,4158,2778,4278,3495,2014,944,364,3718,1856,2208,3314,3763,2694,1985,4976,1988,1608,3125,1756,2300,4499,1276,1524,1036,1973,285,2614,4017,3381,671,767,1390,2259,3014,4127,2281,1991,210,3103,4574,3114,2650,4008,2479,4877,4937,2047,1744,3092,1125,3021,1970,2536,1455,4790,4479,4599,3524,4109,4305,4214,1173,4279,903,1767,2768,761,3408,1592,1763,4540,1956,1309,4721,2554,4381,1805,3071,4429,3556,3569,1484,2723,593,3691,831,348,3607,3256,577,2807,1430,1396,2755,4193,413,746,4734,1959,4422,2178,4428,3946,1458,1280,3630,2000,331,3371,3378,922,316,3446,3323,3047,3034,2869,2331,2164,3823,1394,1246,2588,1938,4427,2134,4032,4048,1992,3289,4695,1513,4689,3918,1221,3551,747,2669,4686,4222,2714,1905,3360,2586,295,301,4092,1316,1286,2754,1021,2078,1924,2350,377,186,2851,1238,3670,4569,2043,1350,3755,1649,1284,2477,3102,2597,4570,3264,3832,3372,1459,407,1373,2182,740,4563,4344,440,936,2791,250,1663,2934,4987,4535,2927,153,2742,4658,2683,2354,4997,3117,3798,3704,4119,96,3765,1146,1343,1579,4264,1520,1138,4792,1586,1117,4765,813,1237,3951,4834,866,2868,2794,2197,3511,3626,1889,3412,3291,4168,2640,2104,3482,2141,4444,3222,1624,4728,2524,957,3617,247,3176,470,51,1163,621,2740,3925,2313,4184,3110,1700,412,1153,553,344,2041,1583,2156,3272,3621,3723,965,4818,4416,702,1867,3153,2801,2260,1393,3062,3100,1969,2610,3215,704,3513,1358,847,1751,4476,1493,1359,3665,161,3567,2158,4862,3353,4296,4357,4241,4052,951,4843,678,3138,278,845,2268,1315,2117,4173,3322,4457,3141,1627,4453,3200,3463,1868,2982,350,1796,689,1468,3890,3179,4259,2800,3762,669,713,2611,2003,4642,162,1167,3914,2248,3078,4873,576,267,4628,4657,898,4752,766,3971,1671,4358,3194,1355,2376,958,1502,1145,1518,3106,1850,3619,4342,1026,2679,3708,970,4580,1730,1482,4955,1171,3580,4081,2726,1353,3990,4266,4160,3594,519,2157,4232,3061,3123,549,1917,3853,1297,2718,461,2266,2761,4840,1650,3643,270,3147,967,3943,148,2514,2635,58,1485,4566,3685,3515,1434,3687,616,4451,1742,3620,85,3145,4327,4966,2624,3010,2906,3749,4667,3467,2292,329,4787,1814,2968,849,18,2033,1908,1948,850,4520,2722,2744,569,3173,1622,4794,1994,67,4315,1441,1668,3660,4904,1006,2132,1486,1470,4744,1436,1961,3865,1483,1235,4248,3608,261,4573,3787,73,140,147,765,758,4907,522,2743,2983,1854,2463,3766,307,4351,608,891,4070,3587,3281,868,2540,2480,613,1519,4233,2016,1362,2446,3846,3069,545,3941,229,4621,2855,4993,604,2528,3904,3573,4086,4466,1581,2299,3532,1568,3005,3872,3052,4887,3805,1114,4455,1409,1075,1106,3897,4823,1564,3667,937,4991,991,3452,1617,1810,3414,474,975,4674,2759,124,4393,2020,3109,3828,4872,2445,1727,4231,482,3636,4552,3304,1835,4747,2410,1319,3563,814,2338,3847,175,4112,3784,4025,3241,2270,4897,4328,417,804,2838,3761,619,4473,1922,1954,2220,1501,4572,4711,2999,3410,4299,1999,2881,2213,2919,1971,1015,174,4748,2201,4066,1440,2202,4822,3944,4594,4318,3184,2046,4011,3963,1736,3544,1677,3920,2721,4543,2898,1694,4329,533,3468,3671,1601,1404,4713,244,3973,191,2308,3616,3155,4027,2235,1739,383,1423,3162,69,1020,523,4629,1803,3280,4246,3485,4974,1639,4852,487,4601,1497,4528,2521,256,2832,4046,356,851,717,2966,2077,216,3083,3434,1947,414,2604,2054,4730,4437,4478,987,3051,3956,314,48,1386,3070,3514,2747,1538,202,1367,3480,923,1615,130,3674,4931,573,2219,2411,3753,4742,3249,4384,4644,1076,1360,4418,1135,3214,420,304,1791,1190,4600,1270,341,4791,3673,1281,3503,4679,2263,1195,1273,4687,2458,1144,3455,4930,961,4237,2257,2785,4326,2129,349,1896,3772,3397,4082,415,2727,3891,2850,886,4909,2587,837,4316,489,3221,2613,4095,2508,4169,498,4577,830,1046,4949,418,916,4378,1379,3436,4022,3209,1062,3814,2830,2253,4950,2746,2265,3768,3680,2609,637,3160,1731,2504,2936,1370,1669,3926,4483,2649,70,4559,327,3510,3893,3852,3326,4452,4595,3473,2475,514,550,3126,4340,2153,2499,1893,3858,1057,4050,2012,1327,969,242,217,3803,2769,4700,3270,2798,1147,423,3968,3639,1320,2937,1400,3424,3648,462,297,4996,721,4782,121,2674,2979,2558,116,2565,1018,2068,143,3212,3722,2923,1670,4391,232,694,4191,2933,798,586,1643,4372,2006,562,2928,4430,2739,544,433,4074,1636,739,2522,3952,4977,4558,918,3635,2060,1546,2007,2805,2600,3086,1769,3746,2724,214,2815,1059,3836,2106,3260,3243,2819,4042,4649,3366,3733,1094,4831,2598,4198,34,1884,3586,3502,479,754,1466,1314,776,4051,3859,1208,3576,974,4501,664,28,1445,1105,2883,4779,3767,4579,2287,4324,565,4978,2750,325,1903,2027,396,532,4513,2899,1724,1588,123,876,1492,4568,3892,2498,1240,3299,2975,3739,1925,1203,2083,3684,466,3302,3572,2639,2438,4311,77,3448,3543,3390,1278,548,1807,3315,2079,3293,625,4122,2180,4445,1633,400,332,1932,192,4197,2573,1705,2309,1037,2512,3008,1333,3834,288,796,3686,2774,4888,4962,4694,1680,1761,3523,2065,4793,3825,3965,3802,1711,2209,1420,3593,2142,4177,3703,4542,1473,4627,4496,601,2084,1687,1048,1717,4603,3226,3445,1206,582,4469,4409,732,4312,4383,2290,963,404,1101,552,118,1205,2464,4581,1291,2362,4007,1247,323,3612,2964,4800,1255,771,1032,4124,4876,3257,1323,3443,3949,3812,3358,3220,1899,2389,346,3483,2151,2500,2009,320,1056,4458,4509,1620,2326,1454,254,4756,2857,2709,4561,1465,3451,7,3820,2073,2383,2680,1504,1296,3477,1086,655,594,387,4712,382,3365,193,883,2812,2345,1703,1151,2570,3405,3459,2261,3288,3961,3939,2996,4737,4537,952,4021,3883,3379,4516,852,101,2200,809,4827,917,4640,1660,2282,2349,3907,615,4534,3962,1398,3216,2081,3712,4339,163,508,3830,1047,374,187,1241,4395,3751,4181,3758,2687,2734,2684,811,2628,3628,2829,3730,4356,1500,103,3481,587,2339,1525,4110,1336,1923,559,2629,4440,1802,2493,2456,645,711,1104,2695,4508,2407,4778,2233,3887,4932,3133,2542,622,3131,95,1967,1840,672,1328,3796,971,3966,4012,3373,4016,865,4736,1752,4916,4948,63,3268,2374,3559,1728,3835,1863,611,2418,2763,3547,2037,1510,260,1242,2515,3356,3856,1029,1142,2288,2097,1306,1385,1801,2303,1990,605,2396,1621,515,2539,537,3924,999,2828,1845,4924,1888,1666,4125,4677,1444,426,4492,536,1207,4031,600,2895,4620,2119,4738,4710,4928,2352,1619,3533,1425,4703,3180,927,385,513,4525,1743,68,810,2093,3492,1038,2813,3650,3339,1027,4106,3822,3024,3416,592,1894,1391,3605,941,4438,4176,4678,3741,2231,1857,1560,2473,3490,3108,1229,575,402,1155,1690,4370,1541,4154,4148,4553,1022,167,4983,1808,1435,4557,3870,3174,3719,2328,867,3810,2218,1226,4277,2145,782,4880,1790,4331,915,2837,1996,1993,1124,1140,471,3504,4441,4704,4345,200,376,3866,1759,106,3527,673,120,3999,4392,854,2872,1737,205,2745,3652,2483,3750,4497,306,2285,1083,3149,3035,3518,4405,1576,3367,2849,4859,839,3699,2820,2466,3663,4459,3976,2950,848,3522,330,2011,4571,64,4061,251,453,4332,511,1377,1363,3496,3900,1642,4239,12,3419,634,633,1926,992,2615,22,1030,1054,37,333,844,663,4098,4820,2441,2904,4390,828,4638,4325,819,4206,4067,2112,4085,1345,1552,3633,3565,3415,909,3112,2583,1265,624,2294,4111,647,3682,4925,566,1590,535,3320,59,4776,4361,4400,4878,4442,4251,3250,675,1115,2103,1933,2773,2365,643,1826,1073,518,342,3615,2644,1995,2402,4958,3258,3290,1741,3552,803,1634,2013,4669,4637,2589,555,2873,352,2184,1783,1285,1606,3557,1951,4152,1505,4784,2974,2543,372,2448,3871,2019,3960,719,2453,1136,1209,4562,3020,4727,4861,3321,1261,1496,87,4359,4087,398,82,1254,1900,3570,110,21,1638,1065,1539,4795,1110,4808,2088,2166,2246,1044,1406,748,255,1198,512,4624,620,2424,697,3018,3878,4662,2040,930,962,173,4059,1941,2889,1571,1708,2367,2666,4460,1326,3430,940,893,4089,1559,3688,43,1604,102,1194,2652,528,3247,4656,4970,3394,89,2520,2959,4671,230,2490,198,291,1692,3657,772,1324,3387,339,2701,2152,1864,97,3181,4588,4952,2232,3475,2935,4995,3127,4585,1300,386,3693,757,2581,1014,3987,4245,1219,1828,2030,1258,3023,3423,1713,1150,2275,4495,3041,1701,4282,2885,3142,3720,1816,2457,4824,2478,2646,4401,4423,1063,1092,1563,2741,4953,1224,2370,1011,1372,2159,3316,114,709,4536,3421,679,4399,249,4845,2631,1782,72,1545,1040,1602,165,2284,4147,3895,3273,322,1364,4224,1679,3178,1051,149,735,3049,4709,1936,3433,4548,2779,4221,4607,1408,3529,3980,3374,311,3560,3248,1084,598,3916,1490,4960,4043,4857,3793,2406,1543,4321,4285,2228,2875,3129,1879,1109,3824,3589,1005,2293,4389,4298,263,2951,3144,3313,4099,2879,269,3230,1760,1654,4731,2216,1699,282,2023,109,1213,551,3717,4139,4145,4434,3841,1939,3137,2109,861,4653,3940,2511,40,1184,1707,1002,32,3797,501,1126,4425,3505,4053,4576,1480,2952,3003,2173,2804,3175,1977,1949,3462,2092,3487,3417,2676,351,649,4463,1262,4094,646,3301,2028,9,4481,3627,687,4755,4322,588,1544,2502,4889,4467,789,4775,1651,4767,1824,4935,128,2780,954,864,2824,441,3199,2278,4116,4870,1156,1735,141,3889,2189,3080,4902,1223,3707,779,3774,1411,3843,2276,829,1616,2204,3204,4014,1290,4477,1243,2110,3341,1575,4660,1119,1635,3471,2564,4934,92,661,4796,3169,686,4798,1361,3662,880,1618,979,2751,2548,99,2482,493,833,2022,411,1033,4933,3743,1553,790,3364,3253,4772,2911,1989,2808,2603,2776,666,4819,2137,1477,1023,1043,3792,2126,4921,2447,367,668,574,751,2619,816,2094,4242,431,3165,2507,3026,2765,3196,2163,4114,3219,448,340,4871,2831,477,4530,1304,2826,347,1294,3661,1549,4343,2277,4275,283,2051,1234,1383,1658,1551,3398,388,1892,4190,4132,3651,4300,2672,2048,3909,2753,494,4306,736,3609,4651,1164,1945,2756,3298,755,4591,2956,436,3004,4885,208,2557,4126,3929,4882,2577]
A = [2391,1236,4581,202,4793,4413,1312,4189,3891,2009,1607,3219,1232,3537,1823,3003,2738,1244,1597,2719,1600,4080,1108,586,4917,68,3729,2403,553,2911,3086,3416,4266,10,4285,2086,2309,580,1830,1831,4066,2753,4604,1061,3117,2615,1546,3647,1266,2675,4306,366,2837,1037,496,2769,2669,4440,2030,1001,1353,3988,4426,2662,4288,46,2586,771,2458,4398,4361,4072,239,40,4566,3216,3163,4144,3489,1253,4221,416,2983,1972,2576,4178,4166,2032,2157,4864,1962,2423,1900,431,4039,4017,2251,3563,4661,3963,938,4304,565,4353,279,2717,898,242,1053,3626,1281,1668,3243,2658,1815,4010,261,44,3766,2784,4758,283,4476,4247,3879,3217,879,2946,3288,2349,666,3479,337,2944,3721,4172,3588,3398,3103,3018,3319,897,3955,236,3867,3234,3679,2213,3735,1202,2961,1729,685,3077,3381,2367,4114,2575,2254,2797,1731,2158,4433,359,2966,4879,489,107,4052,1821,3201,1780,2735,3788,1892,3027,3196,3324,993,1317,1919,4959,384,2580,4958,1172,2496,3245,4236,402,4534,3541,4923,2730,4030,3059,1185,4956,515,141,4138,1084,1100,962,4346,74,1622,4638,3307,602,3448,1340,35,3992,2799,2363,3894,2393,946,354,836,566,498,632,4750,4600,1064,270,4095,4057,4993,2105,4562,2649,1774,2440,544,2310,361,2388,20,1179,4503,4589,434,4237,4048,4881,30,4847,4806,4134,2292,4800,206,2937,3818,1308,3135,3631,2825,669,2820,1103,4824,3773,3239,4945,4367,4883,4671,4584,4457,3481,277,3864,613,2741,1867,3923,4508,4683,980,341,1634,3028,2316,2100,2190,2033,429,3523,2238,3957,4174,4008,3530,1283,139,3014,3152,2177,2681,3281,1020,1905,3733,3768,3129,273,3845,3385,591,1566,3916,3393,2256,1489,652,3405,334,722,791,1783,1686,2018,2298,329,3330,71,1035,4629,3011,3195,4121,2954,4199,3227,817,275,2589,95,1845,4341,2351,867,4819,880,4616,851,4725,1176,1939,1099,2090,2866,4592,4194,4852,1707,3900,2023,2990,2716,148,4447,4354,1603,4651,970,4845,2605,2325,4944,1404,2057,3860,4230,93,2981,4294,1094,271,3511,4822,1645,2635,3414,1971,2997,473,304,1994,3279,3379,4778,3113,3558,247,4660,110,9,2905,1135,4757,3000,2642,2071,154,3851,2755,2532,899,3517,1716,1508,2873,360,3493,3569,2109,2217,3211,4504,4197,1679,4252,543,931,882,2270,1705,3210,3275,1054,539,583,3436,3790,2555,3167,2492,3404,2089,3316,3158,4404,3817,2412,3843,4234,1857,262,4869,253,4684,80,3592,2173,3800,3608,2794,4071,3528,3121,1637,1180,4650,1715,1089,3446,3472,4799,1304,4491,3256,1406,1007,521,2026,2307,572,937,1855,2927,1095,467,4965,2982,2702,1989,294,1122,3685,3107,1503,689,4390,2084,3320,1732,288,4448,1270,1692,514,4283,960,894,1587,4085,795,3355,1639,1217,2876,523,4809,4090,4913,1348,2012,3017,748,810,743,2438,1944,3610,1229,164,3782,165,2154,3189,3079,2880,50,1311,2068,2917,1995,1042,3361,251,2431,811,1771,2248,2141,2874,3634,1456,227,4940,1013,4086,1860,3961,163,2302,3972,3304,2060,2856,1159,3980,3308,3731,4622,1685,3056,1505,3520,4002,1156,4552,2622,1879,3258,778,2627,4369,4160,3177,319,3889,1081,2994,3921,3749,3600,4101,349,1958,2891,4375,3725,3888,2988,789,2539,4835,511,4242,1873,4479,4469,840,228,75,3300,4055,4371,3013,4554,2103,2877,1832,2958,2485,3929,4911,2184,892,303,2043,830,1160,3465,1979,3351,328,619,2678,661,2663,1164,4338,2245,4176,2176,2559,4889,3178,2853,540,198,2760,1926,254,2002,721,2160,3459,768,769,2253,1670,4916,2199,2550,2204,3586,1931,2506,4557,84,3198,4863,4931,3822,2679,708,860,2471,3457,2209,3865,1440,73,4335,2059,1322,2614,3035,1173,186,4173,4843,3143,2497,3539,25,3966,2870,2808,1374,2700,1543,3247,2065,4127,3621,2282,2829,1737,2685,1083,388,430,852,1545,2097,2381,3061,947,956,1435,58,3339,2828,1323,1810,1250,1024,945,929,4383,4365,2648,3896,1660,3920,4788,4876,2294,3976,4167,1992,1870,3701,3105,3116,2790,3428,4715,2151,1552,442,3949,339,2271,633,2377,4899,972,2267,4438,3065,4422,3549,1019,2516,1416,3373,2285,623,383,2455,355,2207,387,2155,1336,146,414,2453,925,195,908,903,403,3583,4084,1965,4471,4705,2670,3273,3323,2566,1680,2187,4021,683,592,100,1869,3552,1210,2107,1252,4511,1764,1120,877,1928,4224,568,2689,2418,2611,4727,706,1521,3805,3765,3220,3775,3394,1969,1932,31,732,2118,4633,4305,4480,904,2347,2127,2073,2882,773,921,4062,1649,2142,4399,4439,772,546,3958,2567,3125,4435,682,1197,4175,4543,1718,3358,4522,1901,85,4763,4775,345,3833,978,2476,2344,2913,752,3292,157,4168,2791,1344,4663,4828,2164,3759,1555,1119,4526,3215,2369,4902,2936,2358,2443,3347,1984,915,3658,1798,4094,541,503,1642,3857,4838,3947,2291,1619,316,1408,1325,3974,4531,231,393,3371,113,1743,2175,4810,457,3484,872,1060,3543,2916,4582,4572,4103,1191,3271,2910,311,377,3477,4079,343,2513,2654,420,1886,686,1898,3924,622,1938,1535,2972,1118,29,785,98,2479,3078,1417,2964,485,3431,2237,2163,2058,2871,4738,2239,497,1003,3153,3512,2565,2413,3715,4512,2915,859,397,158,1779,705,3255,3742,1163,4206,3090,3111,3451,930,453,3567,2,1957,927,2461,3380,2495,1691,4474,3506,4219,4740,4153,2705,858,2054,982,1807,201,1005,4015,823,183,3748,3690,371,499,4238,4455,1643,4967,1017,1130,2512,1194,788,3939,1812,3794,1057,1050,36,1557,1034,1887,70,3544,1320,1918,4813,3956,4091,1596,318,1627,4025,4713,2801,246,4708,3094,4345,4267,4443,2098,4050,3054,4798,616,3624,1876,3570,2775,3008,47,1613,1853,3884,4235,465,162,735,3166,4520,715,1381,3521,2404,2095,4130,507,526,4,4640,2394,2652,1933,837,4053,4396,2747,1542,3253,967,1091,1880,350,1540,848,2573,4709,2016,3769,3110,105,2518,408,1397,1220,1326,1438,266,3230,3906,1858,2117,4701,2148,2537,2855,3246,653,134,3618,3664,991,3194,4403,2456,4704,1298,4781,3954,2004,45,1522,3048,3813,2803,3184,4641,4141,1199,1806,1059,300,1506,1661,525,3001,1228,284,4907,348,660,4688,2563,1231,1072,4884,2809,2396,3302,4376,2504,2901,4126,3628,883,2619,2348,4487,423,3462,1087,2849,1742,41,4968,1170,610,3525,1092,2266,220,1134,780,1941,3452,4111,4642,1333,2787,1248,322,3965,149,4442,1413,4862,714,965,2379,1190,4789,595,3437,672,4282,233,1102,4076,1187,2139,4897,4772,2993,458,3091,448,2616,1474,624,2959,1745,4350,4645,1443,678,4748,3913,3145,2317,4523,1617,1799,226,3236,4625,1412,4849,676,3031,2225,3377,2001,375,4370,1316,1675,1048,584,1351,2606,2593,136,2313,1242,3427,4986,3092,3944,4553,2483,3513,1165,1990,386,1318,106,4726,3576,237,11,28,2339,3131,1748,4529,2718,1403,1168,1813,1681,806,3391,3209,3471,1841,4626,1039,3069,3397,1513,374,3250,924,2608,1595,2114,1052,4990,1166,2376,2752,1706,1647,2295,2644,1258,716,4326,4187,3265,1903,102,4836,955,49,464,664,2739,1626,285,4459,4019,1455,932,611,875,2666,415,585,2243,590,1460,534,4037,3368,3100,48,3024,2838,550,4339,3672,1454,26,1437,3636,427,1723,214,1427,4606,4612,17,3698,4774,4802,4409,2072,2953,3815,125,4229,152,1906,1981,4357,3922,3997,1011,1485,3455,4951,4932,3533,2653,933,2761,1859,4667,1909,2341,1031,4429,3627,1885,2899,953,346,4210,1935,1803,4073,4535,4301,2592,1510,1514,4386,1526,2478,1599,4360,4840,4888,1633,4182,3676,751,4470,697,245,4045,3872,3240,2374,1973,1961,111,608,4118,3360,3007,443,522,3611,4978,2664,2359,1986,1576,1963,1214,4627,2250,758,3562,3495,306,2029,3224,4110,4744,2771,762,79,2914,551,2843,828,2938,4214,4109,1833,3139,6,4320,3328,2781,557,1982,3996,2472,4074,4089,2088,1653,445,4212,1430,1171,4407,3318,488,4355,4687,4198,394,1593,3223,2726,506,4464,2395,754,3661,4619,992,1257,1934,2789,3940,3019,1346,2205,282,1076,3082,4100,2338,3235,4865,1760,352,2400,2145,4603,3295,2780,1133,3825,3795,1648,1665,3089,4024,2548,2970,2110,628,88,4853,1299,4158,3821,3238,1274,2488,990,2116,3084,1734,4501,2813,614,4652,3704,1893,4368,104,535,2699,665,4620,1032,2974,876,587,3169,4644,3384,2036,1431,4343,1848,1421,3473,3266,2147,4982,885,863,4882,2361,4964,2552,663,4674,268,3970,4686,1405,3881,3453,651,1109,1315,893,1950,4980,1862,1538,524,3514,805,3168,3546,120,4125,2034,2185,1559,1140,2773,1616,1959,3106,3064,324,1470,2296,474,989,2279,4467,3529,2375,380,2680,4672,2694,677,1491,533,3545,4423,4201,3910,2886,494,3021,32,513,4164,3535,1753,662,2087,4152,1988,3183,1006,2079,3681,3625,3905,255,4542,1023,1547,2426,4328,1849,4038,3781,846,4067,2178,1414,1601,1874,4139,4773,3383,1309,2587,775,4149,2821,3365,1592,764,576,4507,4083,4380,1664,2896,2764,1067,532,1377,3482,3343,4078,1401,3989,1930,4222,4340,3890,115,596,2732,3122,2751,1211,509,1080,2598,1369,4596,3114,2920,1730,2934,3809,1286,1512,159,4801,189,917,4613,996,560,4842,2859,188,1758,528,4623,1142,3159,3847,1289,232,259,2551,2765,2111,3073,4519,3786,263,2311,2140,4991,1754,3985,3311,463,793,3193,2562,1904,3547,390,3261,906,2399,42,3097,797,3553,4056,1393,2728,1945,2588,4953,2062,2776,2777,2659,94,2547,4975,3982,3880,4458,2380,3066,4711,3420,1386,1733,4891,276,1113,4489,1588,1998,794,1843,1203,483,2996,2754,1051,2240,1583,3141,2640,4826,4312,3700,1955,3037,3080,1533,694,493,3870,3269,3670,119,3802,808,4742,3208,3172,3590,725,2621,3192,4330,3264,1776,801,1788,4258,2427,961,3326,4500,1532,2134,3433,344,3622,3565,43,4450,4108,1070,1184,2986,1476,2597,2613,2320,1749,3914,305,4769,531,517,4232,3162,4179,3286,1773,351,1719,3925,3519,2061,3907,3596,3020,3693,1018,33,3713,1063,4601,691,4954,4996,3917,4933,648,4943,1667,973,763,1116,2389,2995,516,2197,2798,398,2130,658,564,1519,3313,1735,1529,2373,4029,4049,1230,1395,1293,1800,1946,2015,655,2625,3926,1782,2860,3109,890,2952,727,3406,62,4493,65,1523,3615,3777,4776,2143,2805,571,3369,1763,2875,959,1409,3176,1139,2554,3359,2884,3827,4157,4906,4096,2274,1896,2540,4155,2342,4904,1987,3389,2984,536,77,1297,2230,2193,3401,2501,1611,4475,3999,1272,966,3289,3632,832,1746,2731,172,2494,4926,177,3722,1237,424,3757,1991,466,4059,2236,60,3536,3911,118,3950,3137,129,34,1495,4586,896,4269,3969,3432,3919,2460,736,117,2246,3252,3871,4796,4615,3641,807,3228,4664,4682,1273,1837,313,2327,3364,1929,862,2505,2439,3582,1029,1175,4239,1829,2857,3072,2509,1811,2189,3025,2940,2684,3102,4723,1287,160,4081,3222,3898,3429,192,2392,4278,2943,4618,3497,2912,4706,912,4318,3936,333,4026,1573,1747,4855,3118,1624,3321,2022,3337,1376,3892,4724,4827,4018,988,2748,3829,332,4092,3485,818,977,2419,2655,199,1631,4783,409,4895,4145,3157,4867,4761,3254,2571,3984,1638,3375,3730,2816,1473,3350,1387,3854,1875,4524,4035,2521,1953,2671,784,4472,4577,450,1022,3677,2720,3678,2233,4389,1149,4545,1883,1338,2407,500,4973,4402,3589,3564,1602,4530,4548,1980,821,2734,3998,3938,219,2465,3297,3026,1960,406,1123,3413,4936,1777,561,323,230,4657,1245,2749,1182,4877,3312,3093,4260,3447,317,1850,1375,4270,3798,3357,3283,302,4807,770,4028,3663,2259,4702,3004,2926,4418,2933,147,4825,916,3423,2475,1107,4240,3705,2037,4675,4666,4377,2229,3165,4209,4325,555,83,2709,4637,2276,1352,1966,519,2211,1560,3585,3751,854,1509,4925,207,4812,477,4941,3653,447,2150,4506,1854,783,1751,3869,4131,2324,1475,274,1581,3714,1097,1794,3409,612,2560,4140,1713,114,1698,4468,2168,4243,2241,1196,1913,4366,4656,2729,1280,3928,476,723,998,101,724,4014,1152,4392,2620,2490,2939,469,23,3186,53,412,1451,3662,911,2498,3838,3962,873,650,2200,1399,126,3491,3237,116,1262,4287,3803,212,4058,2227,91,2998,2371,4814,3859,3047,2120,3660,3885,1676,3099,1328,326,2293,3370,3557,2224,462,4000,3603,4505,265,3846,2631,2203,425,518,3310,358,4156,729,2469,4741,913,2434,19,131,209,459,1471,1390,4097,3609,433,2962,926,2188,4927,1462,4031,1936,92,2691,200,3396,1445,2973,370,3034,4632,2903,4957,3212,2594,856,4136,3804,2242,4431,4416,244,4420,4804,3175,413,1486,1,2231,1324,4786,1419,1354,3581,4434,710,3556,2951,2858,4040,1082,3229,4246,256,4665,4488,4075,3408,1449,3727,593,1518,3207,4013,3959,3762,1093,4992,3606,2812,3620,826,12,871,1809,1695,1511,1610,4719,3067,4634,1026,3858,2119,2278,13,1457,744,4995,4597,4930,4759,4559,1364,1332,3259,1213,976,2832,2076,3419,264,3164,1027,944,1251,1666,4410,140,3490,589,2415,2851,819,1049,1188,4859,2822,2459,1922,2647,1360,3652,4563,1591,4213,1442,4751,1796,3045,2357,4093,2836,2191,767,4203,1014,3301,3811,2596,3952,827,1558,3744,3203,363,3504,4104,702,4914,2928,4752,4364,3434,2208,2430,3483,2083,1612,4016,2261,2634,2529,579,3475,4428,4379,4397,637,2397,3180,559,1264,4692,3584,2895,3242,2332,2329,1086,1147,760,4610,1768,574,2132,1125,4621,4808,2861,700,3778,1071,1663,1127,1861,4393,3527,3411,2522,63,1881,776,181,1484,3946,4994,1267,258,1590,1781,3942,4250,16,2744,156,3883,3516,2617,372,3619,3791,4922,1669,325,1689,3421,582,3930,2574,1000,755,81,2502,1498,2378,2121,4292,2235,4482,3684,194,422,3005,3244,4186,193,3232,4502,615,452,3088,3741,2452,4901,2206,4837,2535,2425,3146,4971,1650,1805,1246,2534,1629,484,3458,2353,3231,588,2766,2186,578,1465,2657,1785,2907,4322,4347,3951,4154,1085,779,4829,1598,720,2833,2000,1516,1884,2405,4735,1428,3296,3836,4648,4765,3188,327,3650,2545,3474,222,223,1983,2819,405,57,2019,3671,2600,1420,2723,4866,4861,1844,505,1565,2584,1580,3932,2807,4451,4974,3442,2844,2553,1079,3912,1238,418,3638,3205,3895,3187,4436,1895,1789,2268,4782,175,243,4146,1110,4912,3964,2503,4497,618,1056,3249,1434,1265,3081,4564,2447,66,4585,1921,309,1016,3717,3500,1720,790,2865,3776,4550,170,3823,728,844,182,1363,835,3893,4200,886,2021,730,1902,1769,950,1976,4098,3095,4248,3747,1537,4068,39,1155,1632,1564,3644,2013,142,562,1295,3878,2159,1041,3002,1144,428,4938,3133,813,3480,1008,3322,3101,4509,2977,491,4537,0,3221,435,4714,1644,4077,1398,4259,4846,3550,292,1820,2827,4202,4462,2636,3460,4928,1208,3449,4787,3508,4359,640,3341,3392,3382,299,1694,4691,4432,3780,1319,3824,2328,4915,2796,78,1492,2690,1062,3467,1911,3607,812,364,4205,234,4575,421,1496,1331,1461,2063,2774,733,4753,2942,2252,4162,968,1292,815,3349,2113,2890,2569,1305,1977,2623,1392,4245,2673,218,699,2971,3190,1391,14,2275,928,2053,1225,4587,2762,3486,342,734,1058,1458,1396,2125,3764,3023,1334,2707,527,1112,910,3439,2091,1838,187,4803,680,1697,1826,2854,4225,1726,2639,3199,1204,820,260,4950,984,2835,4955,2281,4099,3990,3599,4128,1268,3746,3960,2672,556,1520,1143,2343,4298,1300,1494,1247,3074,2174,1609,1577,1015,4151,3325,461,224,1942,1978,1693,1536,1699,4020,4112,704,2011,3456,2223,21,178,2651,3218,3006,8,4785,4296,1924,121,1673,3206,4903,3202,855,3327,376,2830,3353,2064,1725,1795,542,907,480,210,3058,4483,1078,4717,4417,314,3123,3,4762,4816,1866,1425,1479,1313,2786,3578,4669,2457,3774,1836,638,3510,4532,4184,2746,905,2887,3515,690,3771,2957,3492,2514,4659,471,2123,401,2632,644,4419,1717,2181,4697,213,3315,1478,2637,3575,824,4477,2919,1872,1137,1548,3739,169,1952,208,2433,2878,4391,3902,2989,4574,3723,1569,4449,2696,3124,4983,2290,1739,2044,1321,4817,1366,1727,598,2991,750,1241,400,4594,2165,1500,1641,287,3151,1927,4430,4693,3830,3561,4873,2908,4193,4323,3272,1117,4044,2138,1967,4830,1030,1970,1365,2893,2533,1562,1897,850,2733,1226,887,2170,3937,954,1658,4465,440,1275,2583,4890,3559,4754,3299,2924,3709,4254,1525,4643,2247,2779,417,353,1368,4481,3580,2960,948,2845,1940,2055,2814,4768,4946,1750,981,2334,3033,2312,681,1825,2435,3280,4811,1839,1154,2115,1594,3683,942,868,4180,3832,1284,2864,803,1452,1450,3469,1277,1055,4337,2692,2641,2442,3605,1671,3112,1178,4142,3793,112,203,2047,4415,1882,4887,4513,4694,874,1477,4710,1801,3400,82,2144,4069,4352,4963,625,1786,1138,2676,1487,1271,1554,362,444,1407,4119,3287,2727,4721,1708,2318,3994,3478,2894,2852,2345,2737,1433,4273,1899,1640,3010,2546,2782,1968,3695,1111,1651,315,487,4117,3499,1620,2817,356,4654,291,3412,1227,958,2402,4979,3334,1021,2153,4777,1380,151,1615,1379,1121,3841,3050,1157,4348,2082,845,4549,4734,2527,1738,4461,4034,4170,3716,1623,69,688,3635,4624,838,1586,1301,367,3694,373,2638,1714,2444,3532,2947,4394,1004,1356,2124,2280,4609,4276,382,3262,4815,446,2999,3053,1146,3738,4791,3138,3036,2222,2955,2561,4009,4314,4712,3354,4780,1355,3816,1215,2630,2950,4384,99,2340,1347,4233,1625,741,204,1502,1490,2898,2039,27,3572,4595,3154,3204,4211,1949,4220,3728,4794,1888,3267,441,2474,1846,3277,2688,777,2687,4362,1362,4047,3161,2628,1915,3542,2169,4424,3466,2277,217,338,2520,3983,2129,1394,3779,4135,671,4023,1209,184,2811,1621,2578,3155,2096,2066,4614,1816,4064,3868,718,3487,668,1589,2847,3656,235,861,2027,2337,2255,4295,3181,2923,1129,1539,631,3642,1654,3897,4268,3470,2314,4832,2579,570,3022,3909,2743,1269,567,2075,2772,1530,4987,4909,2401,1515,335,2480,4602,2591,2283,3736,1851,2390,888,1575,4116,520,2232,392,4743,742,3568,3136,2410,238,1701,4567,1657,87,1115,2682,250,3104,2102,4228,4918,2881,3801,4977,985,475,2831,4677,3842,357,4310,1472,3108,1531,3918,4327,712,4165,3225,2802,1415,4997,3848,4851,3372,307,145,1150,3029,4223,1426,2963,1065,4872,2135,4006,1098,2536,320,4653,4736,3147,4770,2287,1608,1704,4065,1370,2626,4590,1302,597,4196,3931,4698,696,211,2660,552,3503,381,3395,4226,4540,3633,3306,2422,2384,3012,849,4324,3030,3555,1077,3374,3130,1842,269,2024,1551,4679,3706,2976,4924,1889,3783,1342,4858,2511,2818,3282,3403,636,2624,1741,3418,746,2629,2356,4293,2014,248,3934,330,1468,1255,3986,4576,2322,3645,2493,3752,4183,4737,4533,4427,4658,2582,2262,1678,3399,4722,2968,979,37,2051,2215,4908,1499,713,3761,4538,1920,4485,2846,1817,2668,1169,2437,1350,205,2210,2618,2192,558,3756,4756,3039,4148,693,4495,2543,3340,2840,2462,3814,3987,3329,3591,2810,135,59,196,4636,215,1383,1871,918,4988,3507,4670,3785,3643,229,4277,940,645,4518,599,103,501,798,289,3835,3812,3655,2017,3853,486,456,1467,1614,603,922,2918,1285,1483,2273,4192,2162,4027,3703,3126,4573,1964,969,1517,2289,3450,1635,4120,3132,3171,3882,4336,2508,1359,4441,155,2411,4046,4784,1630,2948,72,385,3278,957,3430,2525,123,4797,2265,3680,4265,4356,308,2740,3200,4257,2841,3899,2595,3855,2052,492,4460,3366,2538,2945,3294,2722,4412,2932,1261,629,569,4251,2904,1223,1752,765,2228,1441,127,1410,2978,4937,1466,4823,2607,3335,2601,4401,3993,3719,3016,4275,4668,2010,150,1200,4241,4948,1263,2352,1349,2661,3604,4760,2889,1778,3772,3755,2603,4551,4492,575,1177,4453,4844,1276,1954,2244,4473,3518,368,3390,738,455,4087,3623,3668,2869,1488,2785,3468,621,1578,2721,2921,15,3648,974,1002,1541,1937,4960,4525,2092,2099,1310,1504,76,4437,1974,109,4317,4107,2604,86,4591,1388,4966,1282,4262,389,3150,4875,2656,4558,3887,4970,1009,1358,2568,3173,1151,2166,3659,3601,829,3797,1221,4281,1856,2146,1688,2028,281,604,1724,4539,2667,3820,2883,122,3754,857,4274,2885,786,293,1145,1254,321,2481,2221,2524,4695,3331,1567,1345,1907,185,4593,2800,3874,878,137,3042,4976,1767,1696,600,3973,4848,620,3720,554,4766,4042,529,889,1124,4227,1167,1025,4043,1411,3149,1045,1432,1385,4935,548,3338,766,2214,839,4746,252,167,3612,296,3087,3784,1222,1917,4374,4159,2975,4920,2758,1996,1770,711,3422,2336,757,2198,3387,994,3767,3808,2085,865,3876,4792,3726,606,809,2070,891,4256,1201,4989,4515,1357,549,508,144,4885,3953,4321,1711,4898,143,834,2362,4764,436,1822,1951,3745,2683,2507,1975,3696,2288,2542,2467,1028,2710,3901,804,3276,1999,410,3540,3270,2025,695,3686,4088,642,941,1584,1073,280,3673,3573,2879,3424,934,4747,866,1192,781,753,1852,2301,1762,3657,2706,479,4984,1224,1341,1772,4022,3062,3425,4003,761,1216,4510,2450,3524,617,1219,2941,4517,643,2297,2284,1422,1572,1278,2319,2888,674,4185,4527,634,4728,4171,1337,4349,3352,1553,2806,2804,2612,4856,1371,3044,4300,1659,1306,4036,573,649,2421,2987,3708,2383,2834,1736,4307,1033,4962,133,3367,272,3560,1074,2609,3740,1480,2487,537,490,2824,2750,4565,4263,2365,2643,301,4860,3185,1382,3342,3646,1674,3305,426,4452,627,3285,3213,3241,153,2650,2484,2714,179,2572,2269,670,1618,1761,124,4821,216,4400,4880,675,3852,3534,1847,2035,2925,1101,3148,949,512,2350,3127,1373,2665,4568,2515,4755,3637,4570,298,1662,1923,2528,4279,3753,2333,4696,4498,2768,4605,2686,3068,3362,56,3597,3866,3443,1683,4820,3941,3060,2956,4561,4571,1840,3616,4569,2473,4716,4122,4685,2763,3551,2074,1721,4544,3758,4910,267,3009,3826,3440,4598,1423,2171,2712,4631,3096,563,833,4929,1757,3750,1524,3303,2499,4106,3819,3438,4732,191,4249,1303,2326,3063,3388,3293,870,4580,1827,1703,1682,654,3977,3927,1162,4406,2464,609,2445,2212,2967,4351,3386,2756,278,4261,4446,1453,594,2156,1868,4999,468,1459,4208,1563,1153,792,3566,4673,3038,4011,747,3981,4244,3291,4303,2826,396,1040,2792,3840,1439,4181,2387,3070,171,3426,4195,2040,130,3043,2922,1233,3410,1865,3574,4947,2306,4611,997,1702,4363,3691,4546,545,3692,1329,4411,2370,3712,3120,2633,3718,1367,1372,1279,2321,740,745,2152,4311,4921,4555,1605,2823,4051,2906,3435,4299,2195,3548,1131,4588,692,1797,1744,504,3979,3975,900,2526,684,3837,4463,1436,1291,2046,2708,4730,1943,737,3629,3526,2161,3639,679,2909,2201,1195,3654,407,399,2486,2599,3908,1655,3873,4315,2482,943,3760,2558,1570,814,3863,739,4129,460,687,2451,4649,2386,3579,4456,1579,2122,3464,1775,800,1561,1890,4874,1424,4681,1361,472,1544,2867,4579,3711,1218,2368,3531,4868,2930,2815,3807,4385,4700,4280,707,4316,3317,174,3498,2897,999,2902,3040,601,3309,369,1628,4033,4207,2398,411,3810,2868,841,502,4188,2767,1288,2863,774,2477,225,3344,1656,166,432,2414,3263,3140,4981,4662,3463,3665,2793,756,4105,3248,3496,4217,1047,3461,3674,2892,2519,884,782,1528,3346,3055,4063,481,1728,1481,2544,3834,2078,2724,843,3356,2992,3284,2713,2069,2842,2408,2931,3991,4284,290,647,1804,971,4484,4041,1010,995,1568,659,437,2263,3737,1894,987,3083,3770,1808,2788,2300,4289,18,2305,2965,4841,2424,4113,2725,241,4805,4850,4169,698,4082,2346,2531,3675,796,646,3734,2610,1402,3806,2172,4733,38,1378,2303,297,4313,641,2042,4253,1259,3333,2900,1501,2077,4689,3156,3943,1916,3402,1046,2050,4132,1956,331,89,2323,2049,4857,2126,4934,1527,895,799,1878,1126,1068,3699,2031,2463,3363,2646,3789,3170,5,847,96,3336,257,2489,1148,983,1446,173,1891,1710,1908,881,2108,1700,4147,1239,2549,2315,3494,3071,4331,2449,1835,240,3179,132,3445,4547,2448,249,3594,4607,404,4408,4985,2429,3119,1132,4272,4749,2149,3971,67,1198,1444,2354,2517,4395,4414,2979,4779,2272,4707,1636,4771,1256,1183,3257,4834,1069,936,2770,914,3115,4204,1582,1418,635,1339,2500,340,4133,4329,605,295,2194,4387,1549,2006,55,3667,2382,2202,2330,759,3415,2491,701,1174,2704,3978,190,1249,2104,2409,2697,138,3614,2468,657,4894,1550,3444,1672,2249,1290,3134,3856,4309,90,2218,4344,3488,221,4731,1235,4639,3948,1234,4739,3630,2711,3649,3076,538,4972,2304,64,4124,935,3142,2783,4405,802,1787,1985,3886,4839,3057,3828,2703,4308,4271,902,787,3669,3617,986,2219,4919,3743,709,3051,2795,1759,1497,3967,2693,3850,4790,1765,454,1766,1343,4334,2585,2286,4900,919,1677,1585,2417,3214,2355,52,4516,3502,4332,2736,4635,4454,482,964,4478,2980,4231,2081,1044,3839,2308,3348,3571,2698,3182,3417,3799,1571,3710,822,2136,853,1910,1012,2196,4215,2112,3509,3554,4490,3904,2258,1687,2406,2056,1790,530,4831,510,4949,3732,4892,2454,1038,3640,673,1088,1330,4942,4854,1260,1556,3763,2715,1193,920,4007,3251,3538,391,4690,4001,4680,1104,1947,3233,703,2101,1792,2466,2260,4745,161,3598,1114,4302,4070,1740,4372,4163,869,24,3098,3831,4939,1834,3651,909,2045,4678,4190,1327,2677,952,3454,1066,4005,3501,4871,3075,1294,2226,1158,842,1802,3724,1096,1709,1863,378,4767,3861,1828,4388,951,4291,4060,1824,2038,3345,2385,1205,1925,2007,1240,1314,1136,1712,547,2778,3522,1912,2003,1206,963,3191,4870,395,1043,4969,4703,3052,3688,4718,2005,1464,4425,4382,1814,3877,639,3707,2570,3144,3160,3085,495,1818,2530,726,581,347,1534,1447,4123,4536,816,2564,2364,3314,4676,630,4342,3577,1755,1507,607,2446,4617,2216,4445,2094,2106,1482,108,4143,1400,4191,3290,1606,4599,3049,1463,1690,128,4161,2331,1105,4514,3933,4319,2131,2133,667,4378,3407,22,1090,2128,2137,4218,4012,1141,4886,2949,4628,1997,312,3332,1189,1784,2839,365,2848,3915,2335,1948,3844,1036,2577,4358,3875,1819,3687,419,717,1652,3476,2432,4061,439,3015,3595,3032,1307,4795,4102,4496,975,97,1161,197,4608,3666,4952,3849,1212,1993,2436,4466,3935,4255,4216,1864,939,4905,4137,2969,2935,3268,4729,2041,2080,749,4556,4878,3689,4720,4264,3441,1914,1389,1207,4177,438,2742,2674,1296,2264,4444,470,3593,3792,2008,3378,1429,2695,2441,2759,2420,2179,3995,51,2581,2850,3602,1791,2701,1493,4630,3587,2985,2183,1604,4286,4115,2541,1469,2645,2872,4486,3274,4373,4421,4578,1243,3046,451,3174,1722,2556,2167,3862,3128,4333,478,577,3697,3945,3505,2360,1448,336,3376,1793,3968,1181,3226,4583,901,1384,286,4290,2523,2470,379,4381,825,3787,61,3903,4893,1574,2929,864,4655,180,2428,1646,4646,2745,3613,2557,54,4054,2180,4004,449,1128,656,7,3197,731,2234,4541,4647,176,2416,3041,2510,4560,4896,4528,4818,1075,4297,2067,1106,3796,2372,3260,626,2257,4998,2020,3682,1684,4833,4032,3702,2048,1756,2590,2757,719,2182,310,4499,4961,4494,1335,168,2093,3298,2220,1186,1877,923,831,2366,2299,4150,4699,4521,2862,2602]
B = [2822,275,2670,505,1775,2797,1249,3285,859,1542,1337,1009,4421,609,2050,1819,4533,1437,4364,1148,3396,4778,3306,867,4523,3941,607,3978,2187,1657,248,4935,4886,3889,3713,4752,419,3343,3159,4921,1336,944,3916,487,4630,3877,691,4217,384,3636,3362,2439,2156,4370,3779,379,201,1173,3601,3488,1607,1792,4897,1802,1457,1846,2727,2342,627,2939,1500,844,1643,774,580,917,3023,4296,2635,3501,3103,448,1379,2733,400,2755,3617,1294,1767,4700,4679,1439,499,538,1744,723,4908,2074,2013,432,177,1171,1301,3327,3965,824,4850,4762,4305,3120,1541,1509,2501,4035,574,3221,2719,4873,4573,4901,2926,1600,3527,2264,3583,283,1671,3785,392,556,1854,3676,4295,4928,1471,2047,3008,3663,3409,501,4937,4176,2179,2735,2085,428,2305,3049,1559,3665,2801,333,4349,4,4192,1543,68,2969,3972,3750,3623,1025,1966,2061,1906,1667,3936,2890,3802,4414,4348,523,2546,2549,4795,3505,2957,2444,2857,2946,29,1847,2206,220,545,495,470,4555,407,4581,2114,2844,2303,171,2034,2888,1735,3547,2783,640,4478,36,514,2202,376,37,1481,1784,2322,1203,2092,4840,2434,1030,1125,2579,1425,4544,2247,552,976,3967,3014,2906,2561,1951,3514,293,4250,1710,680,3476,3009,4408,4657,899,4915,3803,312,1309,2298,1003,4514,2838,809,4363,1176,2205,3433,4040,4891,2316,3690,4050,4280,162,2177,4645,4968,4730,434,3449,888,344,4882,2142,1973,4338,1805,1113,3957,1515,1631,664,575,2145,75,1156,550,2925,4425,4496,3642,677,4286,780,1407,1597,2196,1876,3900,243,225,2988,3201,1816,1584,2440,3512,4076,84,129,252,3725,789,692,1988,2172,4196,1306,3116,860,3982,893,4158,3520,2383,4157,2350,3256,1612,2557,367,4912,802,1820,4858,2044,4205,2655,2664,4378,1303,3257,4164,130,2448,4284,3895,1494,1909,2209,2803,4112,307,2937,1122,1194,926,2784,4302,4894,1089,1406,1456,2433,4352,813,264,1473,1686,591,2960,2014,1580,1001,3483,571,1599,1754,349,4498,1354,2494,2031,3499,196,230,4509,2217,460,4672,3301,950,1280,325,940,792,2510,4214,3858,600,268,153,3062,1451,3638,1562,1483,4564,3657,1077,1571,660,2042,3308,491,1189,3530,2125,2174,673,3559,3328,4178,1567,2412,324,2631,3979,645,551,398,2121,2263,2955,2592,1333,2796,1659,4646,1311,1681,1468,568,2338,1852,3495,604,4340,4188,4463,1887,1998,4292,3316,3622,1403,4324,2478,3218,503,3310,4687,1041,4766,138,1701,370,387,2437,2737,4115,2539,4232,4655,3234,1638,2419,2302,1736,2854,4084,4984,1888,3822,1894,4702,1154,209,3591,3678,925,763,186,3681,2057,3621,1411,3646,2425,170,2989,4599,3800,3807,3422,2076,2779,3209,3022,4588,2411,1498,2756,2540,738,3730,3460,3509,2138,2704,3840,555,2535,4587,416,4027,2318,2024,4997,883,4670,2873,1127,4924,3101,1455,4267,3672,1353,3031,1853,657,632,4683,2392,3992,3352,4488,3693,2821,2524,26,286,3376,2697,1420,3757,3178,3648,1051,3091,3714,2734,4225,3283,4121,435,1836,4624,2011,1462,3774,4701,102,3148,1169,2468,4697,352,1237,389,1232,359,1453,1435,755,4503,1945,1472,1050,3668,4943,747,475,4168,4885,979,1948,1795,2528,1636,119,1763,1423,4906,4388,3333,2619,1098,4623,458,4474,4012,1655,1506,3819,1831,2495,1691,3268,1722,3216,4889,1083,902,4934,3465,714,2870,1346,4848,1475,2589,597,2331,636,2236,2792,1195,544,2746,1186,2776,2566,3395,3549,3594,1665,4716,1341,4627,2597,515,1470,1840,4516,934,1035,4221,2231,4992,2506,894,1316,3491,3842,4871,65,2241,779,4843,2650,4980,2608,973,2963,812,2582,3536,4445,2795,2487,318,3694,3051,1276,1715,2207,4247,1626,589,2587,757,1259,4109,4854,3164,3282,2082,1036,1979,3999,1552,2973,1826,3032,1493,4520,4983,323,494,3229,841,1757,1953,31,1484,4953,4933,1976,239,4276,2056,2265,1592,1923,3688,3692,189,831,1465,4443,4209,4808,206,4665,1688,2614,1497,2464,4737,15,4434,1904,4844,1146,67,2249,1732,3037,2932,3903,735,3602,4974,4026,2830,1020,3596,2834,346,4989,4508,3479,4566,3674,1097,807,1555,4465,618,2502,2718,3129,1367,2184,2666,2810,2940,3727,4078,696,3630,4318,85,2593,2395,3882,3089,4902,1140,3590,4789,795,2451,2192,1704,3230,928,1603,2378,2903,4673,1644,4438,1942,741,655,2170,540,776,473,3519,1032,1661,2660,2965,4483,4141,2977,4832,2725,2069,1116,2455,2612,449,2141,214,4827,1339,3756,3445,1299,731,4393,1565,518,2663,3994,2143,4981,3387,3883,3567,1302,2216,3761,1773,1663,4480,4471,4595,192,3372,2393,4136,1544,2234,2762,3228,3036,4106,410,1772,415,255,2274,652,1677,1634,3811,1377,2927,4831,169,2818,3927,819,3524,705,1577,2488,2429,4400,3482,3940,596,4282,1279,532,3566,3810,750,2079,4334,1192,1647,2517,720,2819,4556,1499,4233,1583,3908,2674,957,1936,3593,4801,3945,4090,2067,403,48,1554,3322,350,966,2090,2923,2605,3949,197,972,3251,615,690,674,2111,2878,1576,2851,1350,4376,3508,2226,1441,527,4880,3738,921,843,1742,343,3324,511,2679,933,1956,106,1640,1622,4814,2279,1452,50,4308,3305,1268,2382,4892,999,77,356,536,3857,878,4384,1913,2990,561,1794,4031,4982,2731,4095,1386,1839,482,4143,3595,1464,3043,788,721,1149,4087,3918,3706,4262,3789,2193,4052,1323,1633,4491,1625,4787,3413,178,1017,3791,3778,3477,1170,227,3217,3987,1272,3174,1679,3726,2095,1043,4970,3172,1829,3377,4914,174,4550,3703,32,4798,2584,1832,3273,2966,4361,617,1307,2346,2364,1731,7,3970,1971,981,1814,3088,351,1902,4448,1527,611,3313,3517,1889,194,1646,4528,1869,4219,2401,3425,3732,4266,606,1175,659,3731,4929,2161,1724,4423,2934,3564,4965,3018,3865,289,453,2059,2695,4199,1182,3138,4515,2257,3382,1229,702,4590,3836,3312,1548,2748,3274,4639,282,2309,3554,3816,3542,124,3034,2930,4575,296,3291,1863,2656,3604,1405,4562,1961,1217,4719,2260,2351,2038,4152,2268,665,2283,2340,3647,2720,2326,462,4107,134,4539,2023,4341,3504,4713,498,2533,3961,4033,726,4986,2653,737,2530,1684,667,3586,2064,3415,2199,4461,4878,2852,2289,2200,1163,2052,2482,4966,2026,621,3801,592,3868,1445,1213,946,1803,4079,1174,4089,512,2519,565,3237,4416,3354,2387,4441,1750,983,4671,3766,113,2380,4470,1503,2306,3718,4991,2556,987,1982,4238,3161,3680,4260,3641,4561,1393,4598,2189,3233,533,2154,4023,1924,4538,4179,4418,4634,2823,1997,3976,465,348,76,2301,3244,3402,4728,653,340,1211,207,4846,3872,870,468,2424,1591,3741,2550,2743,2130,909,1572,2276,3859,3954,2654,4537,4387,86,1401,2522,3119,1458,1535,4159,3864,4083,4294,3135,2753,1049,366,51,2843,4201,3782,132,411,3610,2867,3028,414,3507,2029,4326,4926,4226,2240,3685,793,1996,530,1980,2447,1004,4822,118,3540,103,1133,547,306,2649,4999,2277,1867,2131,3708,1899,4377,1431,1419,2083,4444,2273,1990,2003,4390,211,903,583,3121,3656,2360,1769,1649,4099,1759,840,2959,3160,3808,4228,1335,1827,1568,4772,24,1172,1727,1415,2483,3959,4833,4420,876,3723,3337,273,2877,2442,223,4198,1705,2565,182,3197,3796,3654,1129,901,1801,4740,3489,3071,1177,3515,2469,3953,3689,4862,1334,1486,4565,3254,2413,4739,4521,1842,121,3991,3890,2886,313,688,3083,2976,1230,154,4571,3238,4207,2237,4606,3183,1305,2515,1438,1460,2787,3029,4293,481,2312,3371,4466,492,1728,1433,4770,626,4161,1109,3124,377,443,3904,87,1718,2836,157,2398,4800,90,4450,2183,3909,4969,4807,4113,4446,865,2436,3892,1734,3777,2168,39,3888,3609,1528,1761,3502,3024,3118,1208,898,2399,4584,3211,4073,1978,234,2188,358,1320,1618,1281,1916,397,612,1376,2632,4661,3173,1768,3329,2601,3319,3928,2389,3401,4663,4477,869,4975,381,334,4788,4268,3066,3856,45,2427,63,444,635,963,1398,4016,3279,3751,3109,889,2899,3863,2629,161,4691,3640,4534,3364,280,2160,920,2106,3394,16,3386,1180,204,958,749,3281,3381,3760,4183,3420,1291,4976,2891,469,2358,2712,1575,3131,3651,2875,4301,2766,4958,3295,1711,3486,2997,1261,3235,1950,3734,4230,608,3828,3369,2089,4072,715,3205,4435,4931,613,1298,2084,643,2422,3153,2032,4110,1181,281,4512,1283,2197,4712,3168,3958,3804,1776,4938,3400,980,2191,4088,1985,1381,2388,2497,2445,4900,2961,2421,1798,1143,147,1787,3946,2449,2545,964,4998,1520,1874,1897,2321,3202,2315,4838,1487,525,463,2689,2477,4359,1533,2403,1844,2136,4150,4229,4163,4967,2232,614,915,1719,2555,4715,4518,4608,3598,3222,474,2080,3964,2354,1069,4189,89,2147,3074,3633,595,4484,3056,1947,513,1227,1723,459,3140,4777,2155,1318,4479,4215,689,4582,770,787,1616,1064,1106,3019,1167,4835,1056,4917,3871,4059,1674,3365,3053,2676,1962,3356,4750,3239,1327,1191,1013,1650,141,3339,185,200,2018,4799,2817,1075,4836,1265,718,3847,2662,4622,1635,2825,3249,4860,1052,3577,3854,2588,1091,4067,2075,877,997,88,2493,2701,1911,2643,2637,519,2708,4591,2036,300,1321,3259,4353,647,2887,4522,1939,1252,4524,4032,166,2,756,4753,2474,3157,3821,1925,4172,2443,1038,3307,3576,3428,4426,3388,4019,4160,754,4069,3894,2572,3812,2948,1808,1817,1014,3873,1225,815,4175,601,2304,2786,3835,669,3939,2365,2832,782,3195,314,1778,2845,4440,4371,253,3457,3911,4024,634,4548,2465,3848,1135,4147,4638,697,1466,1837,4847,4810,1593,2563,4868,1412,57,1885,610,2261,3755,4816,1830,4080,2410,3853,1855,1733,1008,3792,2505,885,1963,2669,2118,952,1198,3518,4890,2295,3192,748,4754,2060,4583,1534,2537,363,4319,3592,2750,3635,2921,2471,1881,856,364,2016,3637,646,457,96,1158,3200,22,3624,1860,3232,993,3357,2307,4834,3117,1892,3450,3185,4002,1804,4746,180,1596,751,249,105,4145,4830,1228,3532,2058,1823,1284,1586,825,4485,849,4949,3338,3139,4034,3391,4486,430,2602,586,4751,678,4803,4792,2898,862,1277,4977,3846,2521,4111,4749,2516,3704,1270,3145,81,3712,2333,3528,3829,4662,1102,670,2874,454,3701,797,3571,3968,1664,1812,3269,4385,4990,510,1234,2255,292,563,3478,4328,4431,911,2337,1748,1200,4502,3226,3875,4724,4462,3537,4048,3492,1944,3997,3320,1865,892,598,4863,3539,4417,4994,1101,4407,3813,5,2769,4153,246,2446,399,2992,2739,2911,4412,4174,2010,2863,2820,4785,4708,4075,4200,773,3215,310,1427,2293,2738,762,1896,1399,311,3110,4316,3212,3166,4614,1653,4307,1877,4210,145,3759,4100,10,1615,668,3535,2017,742,2828,1843,3311,2105,1770,4291,2039,2204,683,785,3632,2975,1864,1235,582,3824,4056,968,3389,2406,1918,4535,233,3150,1566,3915,4812,834,284,4859,3771,4705,1558,1716,4579,3047,4821,4367,3990,44,4574,3286,4432,1053,4482,650,4696,3643,3715,3616,1995,4007,4343,2571,4283,3347,4259,2677,4085,4120,354,2320,3523,4442,2915,1779,3600,3318,4365,602,1117,965,3250,4823,1199,2644,1800,2902,1394,2461,193,4042,4881,2657,4941,1011,2858,4557,2723,3181,2091,2791,2943,4735,3996,1871,1220,2848,4748,1250,918,4306,3921,4920,3841,1343,4594,2856,1783,3473,3924,1672,3266,3474,1190,1507,2475,2859,70,3472,1295,679,3246,4333,3263,1765,3100,2275,2492,3290,3710,3203,3025,445,4300,152,3881,3679,2033,4197,3055,3655,3390,2680,507,1824,231,2698,558,1221,2917,3004,2853,2628,2804,3925,1605,4156,2119,4779,3085,3265,4066,4312,1910,3335,904,91,4896,1330,3597,3763,4366,1999,4351,619,256,1362,2053,1841,316,3299,4755,3794,4815,2620,4580,1531,2827,4963,2529,3606,4527,4942,4631,2741,2450,2253,2808,2993,2754,4813,4185,1669,939,3410,4074,2829,2418,3711,4036,4335,4251,4784,1086,2134,4845,1972,1266,4612,2349,4424,1791,1467,4194,274,382,4619,3629,3314,3510,1560,2308,1698,4893,3691,2005,4313,2467,882,2885,681,212,2367,2363,988,521,3441,442,2150,4593,4309,1039,1165,1459,2153,803,218,3605,2368,3634,4021,560,345,1685,1233,3005,1751,4166,1933,693,2987,2101,2839,80,155,2129,3060,1319,2040,19,4600,1813,4922,2278,992,3481,4093,3989,658,1242,548,1510,1774,1793,1044,3673,1373,4962,3419,4245,4861,3818,2180,4879,1226,2503,3935,838,2658,1388,478,3188,3098,4819,2384,4633,684,2002,814,3277,4996,4389,1396,1764,772,190,2415,1859,2548,3436,2452,3471,2164,369,2166,1288,1914,1002,2978,4568,3378,4644,4559,593,4690,3960,49,1236,1930,1223,3861,3569,144,1476,2167,4354,3793,2072,111,3458,1446,4182,339,456,431,3493,271,1981,263,3367,1850,995,3144,3180,3919,4501,4688,4805,301,1144,2511,1811,2220,734,850,1785,846,4883,3735,730,396,4086,2254,3768,3147,1332,4946,4887,3870,480,1513,1408,3133,1231,3728,4648,4732,3179,40,1848,4058,4452,1057,1670,4126,100,1553,4640,1340,3076,712,4047,4102,3984,471,1300,1551,2259,160,3108,285,806,433,3599,2000,4790,1121,1065,549,4604,4629,1355,1695,1693,3611,4570,4003,2892,4429,1590,2311,1927,4865,1087,241,2880,2391,1522,4925,623,4193,2651,329,818,4459,2938,2479,4567,2751,423,3432,701,1479,1608,3199,1908,4699,3219,1404,4493,2894,4374,1325,1254,2564,165,884,2285,1737,156,3194,4927,3366,761,42,3671,2901,2639,3574,4678,830,996,1965,4303,3196,3334,874,142,4856,163,633,4723,1359,3797,203,2951,3705,3799,1080,1364,3985,622,1594,2995,4553,4668,2710,855,3963,303,3061,1570,1954,1164,2006,3006,4289,3820,3446,3094,25,1989,3017,800,2325,967,4320,1429,3442,2711,4252,2686,3644,4020,2124,125,131,1205,372,1901,3348,4586,3165,2732,919,2641,1578,1862,2866,4131,3379,4097,188,338,708,2271,2456,3258,1730,332,2176,391,579,3323,2972,4641,2636,557,531,1114,3937,687,195,2377,808,3455,404,4733,242,1375,716,1104,3659,3330,3686,4867,2683,4592,3545,2258,1547,1690,3252,108,1060,1630,4270,3151,110,2028,3146,3072,836,833,2954,1238,1448,526,299,4138,2171,3827,567,686,291,2063,3236,422,295,1919,3152,1214,1915,4402,4905,1006,4386,221,151,3044,1883,534,1360,2935,2547,380,2267,2284,4123,1210,2430,3452,13,3926,4899,4044,4903,1328,4053,47,259,700,1079,1526,629,4165,1984,98,3170,1078,385,2498,3095,2221,294,3901,1610,2107,1517,4231,2780,240,1968,1658,3142,2454,3699,3214,2538,947,2499,3001,1766,1621,961,4540,624,1986,4526,4597,2968,1084,1289,2618,1797,805,4133,4473,3086,2869,3190,2707,4864,2292,2665,3466,3884,3416,3944,3675,2736,2195,302,4323,3177,3684,1477,3506,8,875,2652,64,2400,2703,1488,3208,2297,3134,4703,1342,2144,2774,4249,1397,2626,4331,3612,4382,3497,732,4455,3302,1258,1760,4532,4008,2296,2568,1712,1197,2051,3404,1780,3385,309,373,2122,1246,6,386,2219,2128,139,2348,4383,1934,3287,2603,2642,2112,2329,1436,1262,4913,393,2964,1130,3653,3534,3658,4572,4578,1938,464,1856,2356,4135,594,4757,4049,1024,2981,4237,953,1573,3013,1059,2624,4610,866,4360,651,2721,1094,1118,4802,3697,4950,1124,2327,1604,4698,4876,4955,1708,3361,78,3418,1312,4043,1082,3184,3899,1271,4134,1524,123,135,3167,566,517,3929,2227,587,2527,1338,244,2015,4381,2390,1275,804,4094,2835,4842,1062,3831,1054,1828,4146,2127,276,4180,2559,3753,1209,4025,4410,2813,83,4256,4995,3533,736,1977,3104,3189,1058,1382,3225,2310,4607,2163,4130,4241,506,3980,2526,395,1993,2999,2230,4756,962,2246,417,262,20,2928,2108,1537,3500,3830,3737,3494,3045,3468,564,1012,2745,3720,1326,3490,3661,4499,3851,2117,401,2562,1512,4148,2600,1958,2250,3952,2272,4063,2347,3746,53,1111,4653,3213,1443,4415,2675,4985,524,406,4960,1687,1749,3143,2764,4244,2362,2280,847,2807,829,3405,3587,198,1519,2782,357,3683,2985,1018,2496,2884,4206,4411,1699,4874,4909,4839,4552,3834,4433,3136,3440,4395,3740,1937,4327,864,2148,3767,1720,1886,2861,1880,845,872,3886,666,3058,4001,2767,2381,4350,863,1838,2397,3855,4139,811,2554,199,18,1641,2339,175,2777,52,2947,3403,4596,1119,4797,4569,361,2490,3007,1935,2486,388,4500,1619,4436,752,2991,2913,4947,3163,927,4549,3553,3531,4605,3932,1851,4243,3241,2613,4761,1673,1463,104,3042,719,2700,955,3296,1243,1563,1587,476,1096,288,4346,1550,3050,2788,4223,1215,2314,4769,229,908,3346,1141,257,4895,1308,1136,11,143,3046,4884,924,2366,4430,4329,4362,3421,1179,2855,4853,452,390,4492,3284,2907,4765,4030,173,584,3719,4731,3123,2742,265,1449,1168,3707,1928,4467,2800,353,4028,4782,3,4857,1516,820,2758,4666,4793,3137,3345,92,3253,2214,3383,2428,3102,30,3444,4692,4519,3020,2520,2198,3487,3115,848,2373,3080,4391,3627,1085,4277,3614,269,1253,2919,2186,1357,2544,698,1825,937,3773,368,2077,3264,573,703,2323,2470,226,3309,3081,504,2625,4923,2699,1922,1414,1579,1682,164,3869,2681,3374,2020,496,3105,222,3075,3628,3969,4046,4545,2009,554,4693,2182,1504,3998,4818,4773,2576,3748,2218,2385,4254,3443,4743,746,4718,1898,305,1940,3557,3467,4272,4129,2647,1955,425,4311,2244,2790,1356,2215,2420,2151,2876,1809,2604,2580,3649,2087,945,2586,3809,4104,2882,328,1088,2116,4763,342,3581,3155,1366,4321,2611,1081,3242,4253,4988,4504,2922,2633,1777,2872,1496,3733,3114,247,4475,2983,1678,4495,4103,341,873,2512,3843,4714,1263,2158,4155,2146,3790,2724,4563,1240,4332,4224,4236,1147,931,1706,4741,3485,3589,4615,3434,3227,4015,2617,2152,1585,2203,4494,1241,1929,4744,1076,1675,4116,1536,4961,2542,4684,424,1545,4014,4298,2229,3747,4706,4439,2744,4637,3350,822,412,4554,2980,2687,3913,3223,183,3341,4722,3077,236,1907,569,1410,1218,4202,3064,1651,1994,1492,4314,1371,1478,3511,3469,1021,2022,960,3298,279,2847,71,4101,3041,488,930,4476,1324,2266,2287,3849,2599,1138,3353,3550,1557,2408,3585,1539,54,1490,4781,1257,420,2634,4664,1108,3973,1756,79,4681,28,4142,1474,2920,2661,1926,671,642,402,347,2691,321,1983,4281,297,3744,4265,72,871,3698,251,2025,2668,1845,1073,187,4339,2688,2299,4275,3729,1023,3575,975,4396,2781,2027,232,1683,2441,1040,3245,4979,1278,437,2282,4045,4118,1178,1074,4649,3786,4677,3012,978,3090,2806,1392,4547,1204,1771,1598,486,2799,467,4065,122,1310,3411,2577,4208,2998,4776,727,2578,3880,4051,23,1758,1461,887,61,1799,1680,4558,3613,2659,2794,1903,2850,3002,3588,1895,3393,2868,2100,461,2607,2473,1782,1161,4656,1807,2374,1416,4636,1297,4038,4791,93,4380,2860,713,4851,3914,2728,3770,4530,335,2994,1131,2481,2805,4317,2081,1662,1450,3059,3947,1383,3175,1159,1244,3584,3764,3934,3762,3454,905,1890,2865,3456,1251,2438,4114,2702,542,2573,1282,3262,1931,1762,1126,4725,1363,176,4771,3615,1434,2684,2243,3067,4497,1868,590,3288,1564,4576,4621,990,1193,2353,3141,2065,4394,4140,672,1588,620,1155,2871,4144,3206,1046,4458,1368,250,219,2831,375,4481,3429,4589,984,1709,319,3529,4837,826,1959,4105,740,116,1530,2409,662,228,2616,1273,588,224,2840,2181,4132,2692,1063,426,408,3667,699,1160,768,1256,1648,929,1005,2507,3453,3122,1882,1569,4852,450,3158,4729,4758,942,3384,298,2459,2879,1967,2798,2525,1361,3498,2944,1037,1447,641,1103,3052,2904,951,4203,3776,4091,2924,2814,4419,2159,1142,308,3906,1857,3503,2286,3563,4264,4186,4447,3898,3619,2088,4654,3784,3289,2208,1629,1047,2055,1033,1055,861,581,2094,3373,3408,3255,1454,777,2594,1293,1529,3525,1620,572,3326,4068,4310,816,1019,278,1613,2414,4513,2099,1390,2812,4427,3742,3359,1875,4009,2646,1753,2815,4658,1482,1351,1491,1866,4796,3448,4806,1932,2416,2233,1313,2621,1352,3639,2958,2785,2793,4817,2760,4122,3035,2974,1387,4531,2936,3325,1432,2324,205,1440,4957,4536,3580,4096,4082,4585,1790,1873,1628,744,2379,4211,2895,365,2270,1905,4651,4617,1525,3082,4972,1187,4811,4775,261,1623,2372,1788,409,2480,58,1317,4017,2918,4191,599,479,1428,4936,1858,570,3650,4464,1260,3087,2054,2489,4720,4543,3573,4469,1480,2132,4457,3582,2693,4686,3368,4451,4973,695,2583,2096,3780,3722,1331,1292,4235,3187,270,4330,2194,4274,2097,798,2030,922,1042,1946,3837,4125,2773,3462,3113,1000,2765,3912,3839,4487,477,3879,4287,2113,535,3423,3572,916,117,1549,2667,136,3931,4269,3033,3893,1007,1157,4449,441,484,900,4242,4841,1132,2883,2585,2569,4077,1139,3862,799,3414,644,2716,3787,3867,1264,3838,3516,4204,172,3783,3220,4667,3852,1090,33,2761,3240,4506,1920,4742,2536,936,559,4944,4041,101,1835,998,2730,2837,2553,2223,729,2300,605,4734,1422,1365,1833,2726,4710,880,1861,1095,315,835,3971,4601,2864,879,3798,2068,2343,21,4951,4704,2281,446,2248,1185,56,4060,2341,4240,2140,3000,2407,4227,3579,2816,4369,3292,3920,759,1818,3974,2394,2846,2722,3907,1395,3480,1029,4916,616,1741,4011,2881,2909,1781,3833,2139,440,3562,1745,760,3360,2509,910,1286,4304,4169,12,330,2041,896,3303,2833,1031,676,3198,2534,989,2717,3272,2046,3069,529,1322,3003,466,625,213,2541,4647,2238,1184,4490,4409,3826,1957,3336,66,4759,3717,1614,2162,974,1384,322,3424,2713,82,337,1068,3112,3825,3765,127,912,2581,1952,4529,38,783,1026,2893,2491,2648,3162,539,3297,3210,3247,4875,2361,3664,537,4092,158,2402,4278,1418,832,4685,2809,3662,69,956,1738,4246,394,3106,3513,1521,3438,4948,725,1022,1247,3016,1627,994,4551,405,3461,2908,4337,3845,4849,4625,1707,4825,710,4745,3321,2330,2986,3769,4794,3430,628,1696,4511,711,4154,1810,638,4978,2211,378,2212,2747,2462,3380,4659,1870,2900,4257,4018,1166,4460,3398,4952,490,2201,3464,1632,94,2609,1349,3331,1713,1267,2770,383,2396,4642,949,62,4297,508,2225,1815,3193,895,3073,982,766,3132,2045,4356,971,3962,1329,427,1400,1120,1900,1202,4546,2567,2043,2706,43,4128,1380,2518,120,2949,1145,3560,2021,2335,2933,3897,1150,4676,2615,413,3097,1469,140,3437,3344,2623,516,287,4181,2558,2178,3231,3111,2789,2752,1196,3561,2262,1666,3558,923,745,3026,2458,707,4907,4786,4171,3814,1015,3526,1222,3349,1100,3975,3431,3107,3521,500,4869,277,891,2359,4804,1611,2740,4959,2104,764,4081,3823,1092,4767,290,630,3977,4399,4064,717,4010,2294,355,3781,3878,4660,2466,436,3276,3079,656,3260,3182,2673,585,4828,2352,771,1821,215,2137,210,4783,2638,99,1421,2570,3541,733,1595,1248,1255,1582,1296,810,4290,1370,4489,2086,3470,4613,3866,1495,2004,4727,943,4643,3603,2457,4428,2996,1639,2531,2386,2290,1921,1514,784,1061,4397,906,95,661,2242,4263,3021,4119,1878,2500,654,2574,2345,823,3874,2165,4809,3439,2222,553,3068,4993,1700,3375,1717,1949,137,2071,331,4609,3417,2672,2476,3551,35,1872,497,3015,4505,2376,3815,3696,260,2019,1269,0,2671,1153,907,2251,17,4261,543,74,1290,2962,128,4373,3300,2317,2842,2423,1960,4239,1581,4910,2426,4392,4299,2078,4273,3207,2715,4315,4167,1589,786,2802,4108,4212,4405,1546,2768,1714,2849,3608,3267,360,4560,1045,3038,3484,3618,1992,2504,1134,1891,1426,2630,2606,2714,722,1642,2239,2126,4877,2375,4517,2435,1,546,1344,941,2102,3687,954,1676,4195,3496,4872,3917,148,3243,3754,758,4004,4542,2404,3788,2228,1806,2157,1702,4279,2826,235,4368,3860,1358,3293,493,1207,3943,184,2682,2543,3010,3078,4173,2245,986,2575,3795,3317,4768,4220,418,2012,1532,4611,109,1430,3204,1879,4602,1245,336,4510,1128,3130,2929,3538,4151,2269,159,217,3459,649,1212,4184,796,3677,1746,4401,4911,3950,3966,4127,2135,208,839,258,4190,1347,4071,2889,112,2291,3758,326,2357,3275,1822,4738,1112,2332,1099,4689,4347,2256,3084,4472,4918,663,1991,1556,3885,3128,1917,4780,2931,3027,854,694,2460,4006,4736,3399,3666,266,4826,1941,1974,455,520,2115,1162,245,371,1796,2952,1523,1729,791,3805,522,1369,1417,1849,4177,3261,4345,4820,150,4005,4919,648,2916,2035,4717,1975,3682,637,2110,4124,3876,3154,1285,528,4577,2970,1315,2190,3271,753,3340,167,3905,3355,3930,1385,781,3406,1115,3948,3412,794,3270,1893,4541,447,3772,4187,817,935,317,3342,1093,4747,2149,3891,2897,1304,2369,202,4285,3552,1345,3065,2485,4764,1137,3426,3280,3607,2210,1789,1239,2103,1689,3475,685,765,168,1694,2749,1943,1739,4288,3427,3625,4650,1110,2523,126,852,483,2685,1755,2319,4940,1067,1505,2914,2532,1540,439,767,3451,3070,4070,3724,2551,3709,1444,1645,1413,778,2109,2073,238,4398,4255,4956,1442,4675,3556,3844,1071,4507,1743,4372,4248,179,4453,1274,3186,1123,2432,429,1609,1834,3739,1501,3850,3435,2598,2066,1372,724,3156,60,4061,2982,3546,272,3544,1151,1314,3447,3922,3955,3278,2759,1606,1721,4406,2513,4711,3463,2910,4468,1485,1206,3736,3752,1224,913,4682,1378,2463,2334,1066,675,3896,4939,775,3749,97,3670,739,149,2093,578,2772,4054,1219,2942,2610,4694,4603,1601,2694,2596,2098,1692,4945,3645,2824,3669,682,4635,4618,3660,3775,4904,1072,4271,828,3570,991,3620,216,2037,2696,4379,3993,14,2905,3938,3988,3543,2984,3743,4344,2133,4358,2862,541,41,4971,3149,3555,2595,1391,2008,55,3986,3887,362,1518,2405,2224,4932,4695,3721,2560,2370,4437,959,3745,2252,3951,3933,1070,1502,2048,1970,9,4707,2001,4218,4930,1697,254,1016,1010,1574,3392,2763,2953,769,3817,4039,2709,2778,4170,3983,133,2591,1489,4037,706,1752,4213,4055,146,3695,3127,827,4674,4322,3995,3191,3126,4355,1726,1884,977,3315,4964,2453,1617,34,2640,842,4062,2336,3363,3407,4137,3397,4216,4616,897,4454,1508,969,562,2472,4342,2945,1747,3063,1602,4726,2371,59,237,2979,4325,3358,485,502,3700,639,4721,1028,4234,4149,3981,1703,489,2811,4652,1668,509,451,2049,1201,3096,2552,3832,4709,4013,2313,1725,2120,2956,2775,3048,1402,3956,374,914,2645,2070,3093,4258,603,3370,181,2967,576,2062,1348,2173,4898,304,2417,631,1188,4774,2288,1654,1034,851,1107,191,3702,728,4456,837,4824,3040,3910,3568,4422,4620,1409,4357,985,3716,4888,327,4870,2590,1987,4029,948,2007,3652,4525,881,3030,1027,709,3176,4628,3351,4222,790,2729,801,4403,1624,1216,3304,3332,1652,4866,1105,890,3171,2896,107,3902,4680,1637,1424,3039,2514,3011,4375,3169,2690,320,4413,704,2484,3923,3565,438,3631,4855,2950,3092,46,3057,3548,421,2841,1511,3224,4632,2355,1656,27,970,1660,267,938,1964,472,2757,3626,3054,2123,3248,114,3522,2328,1389,4162,2235,3942,3806,4057,4000,2627,4336,2912,2169,2971,2678,4669,4626,2508,1048,2431,4954,932,2622,2705,1152,2213,4760,2771,821,1183,1912,853,1740,3578,857,868,1374,3294,886,4117,2185,743,2175,577,3125,4404,1786,1561,4987,858,4022,1287,2941,3099,73,1538,115,2344,4098,1969,4829]
c = "9f8a883d7e045010619a7aba5c0cdeb33ee0482626e2c5e718b3ef955ad9b4986d4406b6a1f53e78e506c7dcf806f964090a1e44fe2737b883"

g = Perm(g)
A = Perm(A)
B = Perm(B)

def comparePerm(temp):
    for i in range(len(g.internal)):
        if temp.internal[i] != B.internal[i]:
            return False 
    return True

# Chain is the "repeating sequence" used in the writeup
# but it's too long so I initially use "chain"
# Helper function to determine the chain length
# Chain ends when it encounters its first element
def makeChain():
    chain = [[] for i in range(len(g.internal))]
    for i in range(len(g.internal)):
        target = g.internal[i]
        chain[i].append(target)
        temp = g.internal[target]
        while True: 
            if temp == target:
                break
            chain[i].append(temp)
            temp = g.internal[temp]
    return chain 

chain = makeChain()

# Factors is the chain (repeating sequence) length here
# We find all the length in every index of the arrays in
# the cycle
factors = [i for i in range(len(g.internal))]
for i in range(len(g.internal)):
    factors[i] = len(chain[i])

# We retrieve the unique factors to use for the CRT
unique_factors = list(set(factors))

# This is to retrieve back the first occurance
# of the given chain length in the array.
# This serves to find the position of the element
# in its chain
factor_position = []
for factor in unique_factors:
    factor_position.append(factors.index(factor))

# Find position in the chain, which is also the
# remainder of b dividing the chain length
remainder = []
for position in factor_position:
    remainder.append(chain[position].index(B.internal[position]))

# Applying Chinese Remainder Theorem using Sage
b = CRT(remainder, unique_factors) + 1
S = A ** b
key = str(S)

def decrypt(key):
    otp = shake_256(key.encode()).digest(len(bytes.fromhex(c)))
    flag = xor(otp, bytes.fromhex(c))
    return flag 

print(decrypt(key))

SlowDown

To retrieve the flag, one has to do operations that combined, takes longer than 5 seconds for the program to execute.

To do that, we have to analyse the runtime of each operation and see which combination will take the longest time. There’s a limit to the number of operations that can be done on the program, which is defined in the LIMIT constant and takes the value of 25000.

The program given is doing 3 opearations depending on the Opcode on the unordered hashmap:

Opcode 0: Add an entry into the unordered hashmap. This operation runs in constant time O(1)
Opcode 1: Calculate the sum of all the values in every (key, value) pair in the mapping. This operation runs in linear time O(n)
Opcode 2: Simply print the amount of time elapsed. This operation runs in constant time O(1)

Hence, to solve this challenge, we need to find a strategy to waste as much time as possible with a combination of operations of opcode 0 and 1.

One strategy is to add a number of entries into the hashmap, then calculate the number of entries added so that the sum of the time taken adding the entries and summing up all the elements takes the longest time. To do this, let x be the number of operations of opcode 0, then the number of operations of opcode 1 will be LIMIT - x

Hence, the total runtime will be x * 1 + (LIMIT - x) * x. The maximum value of this quadratic happens at (LIMIT + 1) / 2, which is not an integer but we can take either the floor or ceil of the value.

Hence, we need 12500 operations opcode 0 and the rest for operations opcode 1 to waste as much time as possible. To waste slightly more time, we can increase the value of the (key, value) pair so that operations on them take a longer time. The key is cubed so it is big enough to waste time, and the value is a random arbitrary number that’s big enough to fit in int

Solution Implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


from pwn import * 

io = remote('challs.nusgreyhats.org', 10527)

print(io.recvline())
print(io.recvline())

for i in range(12500):
	io.sendline(b'0 ' + str(i ** 3).encode() + b' 69696969')

for i in range(12499):
	print(i)
	io.sendline(b'1')
	print(io.recvline())

io.sendline(b'2')
print(io.recvline())

Foreword#

Challenges#

Baby#

Block#

Cube#

Data Degeneration#

Equation#

Firmware#

Flappy-js#

Ghost#

ImageUpload#

Logical Computers#

Memory Game (Part 1)#

Parcel#

Permutation#

SlowDown#

Foreword

Challenges

Baby

Block

Cube

Data Degeneration

Equation

Firmware

Flappy-js

Ghost

ImageUpload

Logical Computers

Memory Game (Part 1)

Parcel

Permutation

SlowDown