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
from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
import random

TRIES = {
    3: 7, 
    5: 4,
    7: 3,
    9: 3,
    11: 2,
    13: 2,
    15: 2,
    17: 2,
    19: 1,
    21: 2,
    23: 1,
    25: 2,
    27: 2,
}
TRIES.update({x: 1 for x in range(29, 48, 2)})

def single_try(r, divisor, mod, c):
    random_modifier = -1
    while random_modifier < 0 or random_modifier > c:
        random_modifier = r + mod * random.randint(-1, c // mod)
    divisors = Ask(random_modifier)
    return divisors % divisor == 0

def multiple_tries(r, divisor, mod, c, tries):
    for _ in range(tries):
        if not single_try(r, divisor, mod, c):
            return False
    return True

def find_residue1(residues, divisor, mod, c):
    random.shuffle(residues)
    while len(residues) > 1:
        w = []
        for i in range(len(residues)):
            r = residues[i]
            if len(w)==0 and i == len(residues) - 1:
                return r
            if single_try(r, divisor, mod, c):
                w.append(r)
        residues = w
    return residues[0]

def find_residue2(residues, divisor, mod, c):
    random.shuffle(residues)
    for i in range(len(residues)):
        r = residues[i]
        if i == len(residues) - 1:
            return r
        if multiple_tries(r, divisor, mod, c, TRIES[divisor]):
            return r

def find_residue(residues, divisor, mod, c):
    if divisor in [3, 5, 7, 9]:
        return find_residue1(residues, divisor, mod, c)
    else:
        return find_residue2(residues, divisor, mod, c)

#######################
t = GetT()
q = GetQ()
c = GetC()
n = GetN()

### !!!!!
#c = min(c, 10 * n)

for _ in range(t):
    residues = [0, 1, 2, 3, 4, 5, 6, 7]
    r = find_residue(residues, 3, 8, c)
    e = 5
    while True:
        r += (1<<(e-3))
        r = find_residue([r, r + (1 << (e-2)), r + (2 << (e-2)), r + (3  << (e-2))], e, 1<<e, c)
        if n < (1<<e):
            break
        e += 2
    x = ((1<<e) + (1<<(e-1)) - r) % (1<<e)
    Answer(x)