QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#700786#41. Worm WorriesTheZone100 ✓120ms7800kbC++233.3kb2024-11-02 13:23:432024-11-02 13:23:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 13:23:43]
  • 评测
  • 测评结果:100
  • 用时:120ms
  • 内存:7800kb
  • [2024-11-02 13:23:43]
  • 提交

answer

#include <map>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <random>
#include <algorithm>
std::mt19937 rnd(time(NULL));
int n, m, k;
struct Node {
    int x, y, z;
    Node(int _x = 0, int _y = 0, int _z = 0) {
        x = _x, y = _y, z = _z;
    }
    friend Node operator +(const Node &a, const Node &b) {
        return Node(a.x + b.x, a.y + b.y, a.z + b.z);
    }
    friend Node operator *(const Node &a, int b) {
        return Node(a.x * b, a.y * b, a.z * b);
    }
    friend bool operator <(const Node &a, const Node &b) {
        return a.x == b.x ? (a.y == b.y ? a.z < b.z : a.y < b.y) : a.x < b.x;
    }
};
const Node d[6] = {Node(1, 0, 0), Node(-1, 0, 0), Node(0, 1, 0), Node(0, -1, 0), Node(0, 0, 1), Node(0, 0, -1)};
std::map<Node, int> mp;
int query(Node a) {
    if (a.x < 1 || a.x > n || a.y < 1 || a.y > m || a.z < 1 || a.z > k) {
        return 0;
    }

    if (mp.count(a) > 0)
        return mp[a];

    printf("? %d %d %d\n", a.x, a.y, a.z);
    fflush(stdout);
    scanf("%d", &mp[a]);
    return mp[a];
}
Node solve(Node a) {
    double x = (3 - sqrt(5)) / 2;
    int val = query(a);

    for (int i = 0; i < 6; ++i) {
        int tmp = query(a + d[i]);

        if (tmp <= val)
            continue;

        int left = 1, right;

        switch (i) {
        case 0:
            right = n - a.x;
            break;

        case 1:
            right = a.x;
            break;

        case 2:
            right = m - a.y;
            break;

        case 3:
            right = a.y;
            break;

        case 4:
            right = k - a.z;
            break;

        default:
            right = a.z;
        }

        int l = left + floor((right - left) * x), r = right - floor((right - left) * x);

        while (l < r) {
            int u = query(a + d[i] * l), v = query(a + d[i] * r);

            if (u <= v && val <= v)
                left = l + 1, l = r, r = right - floor((right - left) * x);
            else
                right = r - 1, r = l, l = left + floor((right - left) * x);
        }

        while (left < right) {
            int mid = (left + right) / 2;
            int u = query(a + d[i] * mid), v = query(a + d[i] * (mid + 1));

            if (u <= v && val <= v)
                left = mid + 1;
            else
                right = mid;
        }

        return solve(a + d[i] * left);
    }

    return a;
}
int main() {
    scanf("%d%d%d%*d", &n, &m, &k);
    Node ans;
    ans.x = rnd() % n + 1, ans.y = rnd() % m + 1, ans.z = rnd() % k + 1;
    ans = solve(ans);
    printf("! %d %d %d", ans.x, ans.y, ans.z);
}























































































































































































































































































































詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 4000kb

input:

1000000 1 1 10000
19815
19815
19815

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
! 137395 1 1

result:

ok ok, 3/10000 queries

Test #2:

score: 10
Accepted
time: 1ms
memory: 3936kb

input:

1000000 1 1 10000
157205
157206
486691
690325
816178
893959
942030
971740
990102
1001450
1008463
1012798
1015477
1017133
1018156
1018788
1019179
1019421
1019570
1019662
1019719
1019754
1019776
1019789
1019798
1019803
1019806
1019808
1019809
1019810

output:

? 137395 1 1
? 137396 1 1
? 466881 1 1
? 670515 1 1
? 796368 1 1
? 874149 1 1
? 922220 1 1
? 951930 1 1
? 970292 1 1
? 981640 1 1
? 988653 1 1
? 992988 1 1
? 995667 1 1
? 997323 1 1
? 998346 1 1
? 998978 1 1
? 999369 1 1
? 999611 1 1
? 999760 1 1
? 999852 1 1
? 999909 1 1
? 999944 1 1
? 999966 1 1
?...

result:

ok ok, 30/10000 queries

Test #3:

score: 10
Accepted
time: 1ms
memory: 4048kb

input:

1000000 1 1 10000
882416
882415
882417
934896
967332
987377
999767
1007423
1012156
1015080
1016888
1018005
1018695
1019122
1019386
1019549
1019650
1019712
1019750
1019774
1019789
1019798
1019803
1019807
1019809
1019810

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 7655 1 1
? 4731 1 1
? 2923 1 1
? 1806 1 1
? 1116 1 1
? 689 1 1
? 425 1 1
? 262 1 1
? 161 1 1
? 99 1 1
? 61 1 1
? 37 1 1
? 22 1 1
? 13 1 1
? 8 1 1
? 4 1 1
? 2 1 1
? 1 1 1
! 1 1 1

result:

ok ok, 26/10000 queries

Test #4:

score: 10
Accepted
time: 1ms
memory: 3992kb

input:

1000000 1 1 10000
107202139
107202039
107202239
112450139
115693739
117698239
118937239
85872677
118463939
86345877
118756339
119048839
86457577
119006239
86500177
119032639
119059039
86510277
119055039
86514177
119057439
119059839
119060439
86514677
119060239
86514877
119060339
200322608

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/10000 queries

Test #5:

score: 10
Accepted
time: 0ms
memory: 4000kb

input:

1000000 1 1 10000
312370
312370
312370

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
! 137395 1 1

result:

ok ok, 3/10000 queries

Subtask #2:

score: 22
Accepted

Test #6:

score: 22
Accepted
time: 1ms
memory: 4044kb

input:

1000000 1 1 35
33088585
33118585
36881523
107014757
66631685
108052209
88819534
62744461
39654111
77481521
85570971
32696920
80124835
44655133
44098713
90508204
96322209
115312209
83248204
112522209
80488204
114232209
115972209
79828204
115702209
79588204
115852209
116032209
79528204
116002209

output:

? 137395 1 1
? 137396 1 1
? 466881 1 1
? 670515 1 1
? 796368 1 1
? 592734 1 1
? 544662 1 1
? 622444 1 1
? 574372 1 1
? 604082 1 1
? 585720 1 1
? 597069 1 1
? 590055 1 1
? 594390 1 1
? 591711 1 1
? 593367 1 1
? 592343 1 1
? 592976 1 1
? 593125 1 1
? 592883 1 1
? 593033 1 1
? 592940 1 1
? 592998 1 1
?...

result:

ok ok, 30/35 queries

Test #7:

score: 22
Accepted
time: 0ms
memory: 3944kb

input:

1000000 1 1 35
19815
19815
19815

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
! 137395 1 1

result:

ok ok, 3/35 queries

Test #8:

score: 22
Accepted
time: 1ms
memory: 4000kb

input:

1000000 1 1 35
157205
157206
486691
690325
816178
893959
942030
971740
990102
1001450
1008463
1012798
1015477
1017133
1018156
1018788
1019179
1019421
1019570
1019662
1019719
1019754
1019776
1019789
1019798
1019803
1019806
1019808
1019809
1019810

output:

? 137395 1 1
? 137396 1 1
? 466881 1 1
? 670515 1 1
? 796368 1 1
? 874149 1 1
? 922220 1 1
? 951930 1 1
? 970292 1 1
? 981640 1 1
? 988653 1 1
? 992988 1 1
? 995667 1 1
? 997323 1 1
? 998346 1 1
? 998978 1 1
? 999369 1 1
? 999611 1 1
? 999760 1 1
? 999852 1 1
? 999909 1 1
? 999944 1 1
? 999966 1 1
?...

result:

ok ok, 30/35 queries

Test #9:

score: 22
Accepted
time: 0ms
memory: 3920kb

input:

1000000 1 1 35
882416
882415
882417
934896
967332
987377
999767
1007423
1012156
1015080
1016888
1018005
1018695
1019122
1019386
1019549
1019650
1019712
1019750
1019774
1019789
1019798
1019803
1019807
1019809
1019810

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 7655 1 1
? 4731 1 1
? 2923 1 1
? 1806 1 1
? 1116 1 1
? 689 1 1
? 425 1 1
? 262 1 1
? 161 1 1
? 99 1 1
? 61 1 1
? 37 1 1
? 22 1 1
? 13 1 1
? 8 1 1
? 4 1 1
? 2 1 1
? 1 1 1
! 1 1 1

result:

ok ok, 26/35 queries

Test #10:

score: 22
Accepted
time: 1ms
memory: 3988kb

input:

1000000 1 1 35
107202139
107202039
107202239
112450139
115693739
117698239
118937239
85872677
118463939
86345877
118756339
119048839
86457577
119006239
86500177
119032639
119059039
86510277
119055039
86514177
119057439
119059839
119060439
86514677
119060239
86514877
119060339
200322608

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #11:

score: 22
Accepted
time: 0ms
memory: 3916kb

input:

1000000 1 1 35
171191901
171191801
171192001
176439901
179683501
181688001
182927001
86170001
182453701
86643201
182746101
183038601
86754901
182996001
86797501
183022401
183048801
86807601
183044801
86811501
183047201
183049601
183050201
86812001
183050001
86812201
183050101
200619932

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #12:

score: 22
Accepted
time: 0ms
memory: 4000kb

input:

1000000 1 1 35
107202139
107202039
107202239
112450139
115693739
117698239
118937239
85872677
118463939
86345877
118756339
119048839
86457577
119006239
86500177
119032639
119059039
86510277
119055039
86514177
119057439
119059839
119060439
86514677
119060239
86514877
119060339
200322608

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #13:

score: 22
Accepted
time: 1ms
memory: 4040kb

input:

1000000 1 1 35
171191901
171191801
171192001
176439901
179683501
181688001
182927001
86170001
182453701
86643201
182746101
183038601
86754901
182996001
86797501
183022401
183048801
86807601
183044801
86811501
183047201
183049601
183050201
86812001
183050001
86812201
183050101
200619932

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #14:

score: 22
Accepted
time: 1ms
memory: 3860kb

input:

1000000 1 1 35
134259743
134259464
134260021
150996021
165116986
177924466
193577044
89285482
185496789
143344365
189733076
198237599
167121766
195842684
183458871
197108468
199569483
190814895
198889849
196394011
199244402
199804881
200120557
197912875
199980140
198927020
200041106
200312370

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #15:

score: 22
Accepted
time: 1ms
memory: 3860kb

input:

1000000 1 1 35
192329426
192329325
192329527
196989865
199104695
200001532
200303906
162400318
200222285
195191003
200279570
200312122
199299536
200309896
200179764
200311458
200312358
200288638
200312290
200310703
200312336
200312366
200312369
200311987
200312368
200312296
200312369
200312370

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
? 84915 1 1
? 52479 1 1
? 32434 1 1
? 20044 1 1
? 12388 1 1
? 24777 1 1
? 17120 1 1
? 21853 1 1
? 18928 1 1
? 18237 1 1
? 19354 1 1
? 18663 1 1
? 19090 1 1
? 18826 1 1
? 18764 1 1
? 18866 1 1
? 18803 1 1
? 18842 1 1
? 18818 1 1
? 18812 1 1
? 18808 1 1
? 18814 1...

result:

ok ok, 28/35 queries

Test #16:

score: 22
Accepted
time: 1ms
memory: 3840kb

input:

1000000 1 1 35
312370
312370
312370

output:

? 137395 1 1
? 137396 1 1
? 137394 1 1
! 137395 1 1

result:

ok ok, 3/35 queries

Subtask #3:

score: 12
Accepted

Test #17:

score: 12
Accepted
time: 1ms
memory: 3904kb

input:

200 200 1 4000
19815
19815
19815
19815
19815

output:

? 195 132 1
? 196 132 1
? 194 132 1
? 195 133 1
? 195 131 1
! 195 132 1

result:

ok ok, 5/4000 queries

Test #18:

score: 12
Accepted
time: 0ms
memory: 3976kb

input:

200 200 1 4000
20136
20137
20138
20140
20141
20142
20167
20184
20194
20200
20204
20206
20208
20209
20208

output:

? 195 132 1
? 196 132 1
? 197 132 1
? 199 132 1
? 200 132 1
? 200 133 1
? 200 158 1
? 200 175 1
? 200 185 1
? 200 191 1
? 200 195 1
? 200 197 1
? 200 199 1
? 200 200 1
? 199 200 1
! 200 200 1

result:

ok ok, 15/4000 queries

Test #19:

score: 12
Accepted
time: 1ms
memory: 3940kb

input:

200 200 1 4000
312370
312370
312370
312370
312370

output:

? 195 132 1
? 196 132 1
? 194 132 1
? 195 133 1
? 195 131 1
! 195 132 1

result:

ok ok, 5/4000 queries

Test #20:

score: 12
Accepted
time: 1ms
memory: 3920kb

input:

200 200 1 4000
1329868
1329869
1312372
1312372
1312372
1329870
1330824
1331431
1331823
1332035
1332322
1332347
1332362
1312369
1332361
1332363
1312372
1332364
1312492
1312445
1312521
1332115
1312372
1332245
1332277
1332367
1332365
1312372
1332366
1332368
1330919
1312372
1331440
1312372
1332021
13323...

output:

? 195 132 1
? 196 132 1
? 197 132 1
? 199 132 1
? 196 133 1
? 196 131 1
? 196 81 1
? 196 50 1
? 196 30 1
? 196 18 1
? 196 11 1
? 196 6 1
? 196 3 1
? 196 1 1
? 196 4 1
? 196 2 1
? 197 2 1
? 195 2 1
? 121 2 1
? 74 2 1
? 150 2 1
? 168 2 1
? 179 2 1
? 186 2 1
? 190 2 1
? 192 2 1
? 194 2 1
? 191 2 1
? 19...

result:

ok ok, 46/4000 queries

Test #21:

score: 12
Accepted
time: 0ms
memory: 3924kb

input:

200 200 1 4000
61335973
61330973
61340973
95830973
93880973
1494365
94960973
96365973
96600973
96860973
96935973
1494365
96930973
96940973
96945973
87630973
1494365
89600973
97030973
96990973
97060973
89770973
1494365
1494365
97065973
62325973
62390973
97685973
97660973
97700973
62310973
97695973
14...

output:

? 195 132 1
? 196 132 1
? 194 132 1
? 120 132 1
? 74 132 1
? 149 132 1
? 102 132 1
? 131 132 1
? 138 132 1
? 142 132 1
? 145 132 1
? 147 132 1
? 144 132 1
? 146 132 1
? 146 133 1
? 146 158 1
? 146 175 1
? 146 148 1
? 146 142 1
? 146 138 1
? 146 144 1
? 146 146 1
? 146 143 1
? 146 145 1
? 147 144 1
?...

result:

ok ok, 105/4000 queries

Test #22:

score: 12
Accepted
time: 0ms
memory: 4188kb

input:

200 200 1 4000
1019813
1021826
1019813
1019813
1020278
1020277
1020279
1020329
1020360
1020380
1020392
1020399
1020404
1020407
1019810
1020406
1020408
1020409
1020485
1020532
1020562
1020580
1020591
1020598
1020602
1019813
1020600
1020603
1020604
1020605
1020680
1020727
1020756
1020774
1020785
10207...

output:

? 195 132 1
? 196 132 1
? 197 132 1
? 199 132 1
? 200 132 1
? 200 133 1
? 200 131 1
? 200 81 1
? 200 50 1
? 200 30 1
? 200 18 1
? 200 11 1
? 200 6 1
? 200 3 1
? 200 1 1
? 200 4 1
? 200 2 1
? 199 2 1
? 123 2 1
? 76 2 1
? 46 2 1
? 28 2 1
? 17 2 1
? 10 2 1
? 6 2 1
? 3 2 1
? 8 2 1
? 5 2 1
? 4 2 1
? 4 3 ...

result:

ok ok, 2311/4000 queries

Test #23:

score: 12
Accepted
time: 7ms
memory: 4048kb

input:

200 200 1 4000
1322609
159908980
138398980
120458980
1322609
1322609
1322609
135608980
1322609
1322609
138393980
138403980
138578980
138688980
1322610
138643980
135933980
138668980
138698980
138703980
1322610
1322610
138708980
139028980
139233980
139358980
124833980
139308980
1322610
139338980
13936...

output:

? 151 93 1
? 152 93 1
? 170 93 1
? 182 93 1
? 163 93 1
? 175 93 1
? 167 93 1
? 172 93 1
? 169 93 1
? 171 93 1
? 170 94 1
? 170 92 1
? 170 57 1
? 170 35 1
? 170 21 1
? 170 44 1
? 170 30 1
? 170 39 1
? 170 33 1
? 170 32 1
? 170 31 1
? 171 32 1
? 169 32 1
? 105 32 1
? 64 32 1
? 39 32 1
? 24 32 1
? 49 3...

result:

ok ok, 1069/4000 queries

Subtask #4:

score: 19
Accepted

Test #24:

score: 19
Accepted
time: 1ms
memory: 4000kb

input:

1000 1000 1 3500
19815
19815
19815
19815
19815

output:

? 151 493 1
? 152 493 1
? 150 493 1
? 151 494 1
? 151 492 1
! 151 493 1

result:

ok ok, 5/3500 queries

Test #25:

score: 19
Accepted
time: 1ms
memory: 3920kb

input:

1000 1000 1 3500
20468
20469
20792
20994
21117
21195
21241
21271
21289
21300
21307
21311
21314
21316
21317
21316
21318
21505
21623
21694
21739
21767
21784
21794
21801
21805
21807
21809
21808
21808

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 990 493 1
? 994 493 1
? 997 493 1
? 999 493 1
? 1000 493 1
? 1000 494 1
? 1000 492 1
? 1000 305 1
? 1000 187 1
? 1000 116 1
? 1000 71 1
? 1000 43 1
? 1000 26 1
? 1000 16 1
? 1000...

result:

ok ok, 30/3500 queries

Test #26:

score: 19
Accepted
time: 0ms
memory: 3920kb

input:

1000 1000 1 3500
312370
312370
312370
312370
312370

output:

? 151 493 1
? 152 493 1
? 150 493 1
? 151 494 1
? 151 492 1
! 151 493 1

result:

ok ok, 5/3500 queries

Test #27:

score: 19
Accepted
time: 1ms
memory: 3868kb

input:

1000 1000 1 3500
1312371
1379366
1312371
1312371
1312372
1312372
1312372
1312372
1312372
1312371
1312371
1312372
1312371
1312372
1312371
1312371
1596679
1312372
1312372
1312372
1778620
1312372
1778602
1781375
1312372
1778627
1312372
1781329
1781374
1312372
1312372
1781376
1730910
1722575
1783845
178...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 909 1
? 976 938 1
? 976 945 1
...

result:

ok ok, 156/3500 queries

Test #28:

score: 19
Accepted
time: 2ms
memory: 4008kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #29:

score: 19
Accepted
time: 1ms
memory: 4000kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #30:

score: 19
Accepted
time: 0ms
memory: 3952kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #31:

score: 19
Accepted
time: 1ms
memory: 4056kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #32:

score: 19
Accepted
time: 2ms
memory: 4016kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #33:

score: 19
Accepted
time: 0ms
memory: 3968kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #34:

score: 19
Accepted
time: 2ms
memory: 3928kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #35:

score: 19
Accepted
time: 1ms
memory: 4004kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #36:

score: 19
Accepted
time: 2ms
memory: 4000kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #37:

score: 19
Accepted
time: 1ms
memory: 3920kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #38:

score: 19
Accepted
time: 1ms
memory: 4012kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #39:

score: 19
Accepted
time: 1ms
memory: 4052kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #40:

score: 19
Accepted
time: 2ms
memory: 3876kb

input:

1000 1000 1 3500
1494364
78957973
1494364
1494364
65341497
1494365
67227497
68697497
69220697
1494364
1494364
69700697
1494364
69277497
1494364
1494364
69700497
69700897
1494365
1494365
69787297
1494365
1494365
69772497
69806097
1494365
69804497
1494365
69804897
69806297
69806497
1494365
69806697
80...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 295/3500 queries

Test #41:

score: 19
Accepted
time: 0ms
memory: 4012kb

input:

1000 1000 1 3500
1619933
116943998
1619933
1619933
96328306
1619934
101644901
105993563
107589848
1619933
1619933
109078545
1619933
107764779
1619933
1619933
109077920
109079170
1619934
1619934
109349688
1619934
1619934
109303293
109408656
1619934
109403636
1619934
109404891
109409284
109409911
1619...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 754 493 1
? 724 493 1
? 706 493 1
? 695 493 1
? 713 493 1
? 702 493 1
? 699 493 1
? 704 493 1
? 701 493 1
? 703 493 1
? 702 494 1
? 702 492 1
? 702 305 1
? 702 187 1
? 702 376 1
? 702 421 1
? 702 349 1
? 702 394 1
? 702 366 1
...

result:

ok ok, 162/3500 queries

Test #42:

score: 19
Accepted
time: 1ms
memory: 3920kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #43:

score: 19
Accepted
time: 0ms
memory: 4060kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #44:

score: 19
Accepted
time: 1ms
memory: 3928kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #45:

score: 19
Accepted
time: 1ms
memory: 3988kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #46:

score: 19
Accepted
time: 1ms
memory: 3876kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #47:

score: 19
Accepted
time: 0ms
memory: 3992kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Test #48:

score: 19
Accepted
time: 0ms
memory: 3992kb

input:

1000 1000 1 3500
1322609
70873142
1322609
1322609
57640742
78716342
93427142
103933142
110582342
1322609
1322609
112095142
1322609
111337142
1322609
1322609
112095342
112133942
112157942
112172742
112181942
112187542
112191142
115258942
1322610
113718942
1322610
114487342
1322610
1322610
115258742
1...

output:

? 151 493 1
? 152 493 1
? 475 493 1
? 677 493 1
? 800 493 1
? 878 493 1
? 924 493 1
? 954 493 1
? 972 493 1
? 983 493 1
? 965 493 1
? 976 493 1
? 979 493 1
? 974 493 1
? 977 493 1
? 975 493 1
? 976 494 1
? 976 687 1
? 976 807 1
? 976 881 1
? 976 927 1
? 976 955 1
? 976 973 1
? 976 984 1
? 976 991 1
...

result:

ok ok, 156/3500 queries

Subtask #5:

score: 14
Accepted

Test #49:

score: 14
Accepted
time: 1ms
memory: 3988kb

input:

100 100 100 100000
19815
19815
19815
19815
19815
19815
19815

output:

? 51 93 56
? 52 93 56
? 50 93 56
? 51 94 56
? 51 92 56
? 51 93 57
? 51 93 55
! 51 93 56

result:

ok ok, 7/100000 queries

Test #50:

score: 14
Accepted
time: 0ms
memory: 4048kb

input:

100 100 100 100000
19997
19998
20016
20028
20035
20040
20043
20045
20046
20047
20049
20051
20052
20053
20052
20052
20054
20075
20088
20097
20102
20105
20107
20108
20107
20107

output:

? 51 93 56
? 52 93 56
? 70 93 56
? 82 93 56
? 89 93 56
? 94 93 56
? 97 93 56
? 99 93 56
? 100 93 56
? 100 94 56
? 100 96 56
? 100 98 56
? 100 99 56
? 100 100 56
? 99 100 56
? 100 100 57
? 100 100 55
? 100 100 34
? 100 100 21
? 100 100 12
? 100 100 7
? 100 100 4
? 100 100 2
? 100 100 1
? 99 100 1
? 1...

result:

ok ok, 26/100000 queries

Test #51:

score: 14
Accepted
time: 1ms
memory: 4000kb

input:

100 100 100 100000
312370
312370
312370
312370
312370
312370
312370

output:

? 51 93 56
? 52 93 56
? 50 93 56
? 51 94 56
? 51 92 56
? 51 93 57
? 51 93 55
! 51 93 56

result:

ok ok, 7/100000 queries

Test #52:

score: 14
Accepted
time: 3ms
memory: 4024kb

input:

100 100 100 100000
1322609
1322610
1322610
62765542
1322609
1322609
1322609
1322610
1322609
1322609
62765942
62819542
62825142
1322610
1322610
1322610
62825542
1322610
40503542
61103542
61805942
1322610
62879542
62825942
1322610
1322610
1322610
1322610
62879142
62879942
77461142
77477542
77490742
13...

output:

? 51 93 56
? 52 93 56
? 70 93 56
? 82 93 56
? 89 93 56
? 77 93 56
? 85 93 56
? 80 93 56
? 83 93 56
? 81 93 56
? 82 94 56
? 82 96 56
? 82 98 56
? 82 99 56
? 82 97 56
? 83 98 56
? 81 98 56
? 51 98 56
? 30 98 56
? 62 98 56
? 70 98 56
? 75 98 56
? 78 98 56
? 80 98 56
? 77 98 56
? 79 98 56
? 78 99 56
? 7...

result:

ok ok, 385/100000 queries

Test #53:

score: 14
Accepted
time: 2ms
memory: 4016kb

input:

100 100 100 100000
1619933
1619934
1619934
73365054
1619933
1619933
1619933
1619934
1619933
1619933
73365805
73466427
73476945
1619934
1619934
1619934
73477696
1619934
36801376
70283267
71576791
1619934
73579158
73478447
1619934
1619934
1619934
1619934
73578407
73579910
104792417
104833190
104866019...

output:

? 51 93 56
? 52 93 56
? 70 93 56
? 82 93 56
? 89 93 56
? 77 93 56
? 85 93 56
? 80 93 56
? 83 93 56
? 81 93 56
? 82 94 56
? 82 96 56
? 82 98 56
? 82 99 56
? 82 97 56
? 83 98 56
? 81 98 56
? 51 98 56
? 30 98 56
? 62 98 56
? 70 98 56
? 75 98 56
? 78 98 56
? 80 98 56
? 77 98 56
? 79 98 56
? 78 99 56
? 7...

result:

ok ok, 340/100000 queries

Test #54:

score: 14
Accepted
time: 6ms
memory: 4100kb

input:

100 100 100 100000
400854994
400854995
400854979
400854967
400854986
400854991
400854994
400854996
400854995
400854995
400854997
400855024
400855002
400855018
400855015
400855027
400855023
400855027
400855026
400855028
400859943
400855010
400854998
400855017
400855021
400855024
400859944
400859945
4...

output:

? 51 93 56
? 52 93 56
? 70 93 56
? 82 93 56
? 63 93 56
? 58 93 56
? 55 93 56
? 53 93 56
? 54 93 56
? 53 94 56
? 53 92 56
? 53 57 56
? 53 35 56
? 53 71 56
? 53 48 56
? 53 62 56
? 53 66 56
? 53 60 56
? 53 59 56
? 53 61 56
? 54 61 56
? 71 61 56
? 83 61 56
? 64 61 56
? 60 61 56
? 57 61 56
? 55 61 56
? 5...

result:

ok ok, 898/100000 queries

Subtask #6:

score: 23
Accepted

Test #55:

score: 23
Accepted
time: 1ms
memory: 3860kb

input:

500 500 500 150000
19815
19815
19815
19815
19815
19815
19815

output:

? 151 493 456
? 152 493 456
? 150 493 456
? 151 494 456
? 151 492 456
? 151 493 457
? 151 493 455
! 151 493 456

result:

ok ok, 7/150000 queries

Test #56:

score: 23
Accepted
time: 1ms
memory: 3920kb

input:

500 500 500 150000
20696
20695
20697
20754
20790
20812
20826
20835
20840
20843
20845
20846
20847
20849
20851
20852
20853
20852
20852
20854
21027
21136
21202
21244
21269
21285
21295
21301
21305
21307
21308
21307
21307

output:

? 151 493 456
? 152 493 456
? 150 493 456
? 93 493 456
? 57 493 456
? 35 493 456
? 21 493 456
? 12 493 456
? 7 493 456
? 4 493 456
? 2 493 456
? 1 493 456
? 1 494 456
? 1 496 456
? 1 498 456
? 1 499 456
? 1 500 456
? 2 500 456
? 1 500 457
? 1 500 455
? 1 500 282
? 1 500 173
? 1 500 107
? 1 500 65
? ...

result:

ok ok, 33/150000 queries

Test #57:

score: 23
Accepted
time: 1ms
memory: 3868kb

input:

500 500 500 150000
312370
312370
312370
312370
312370
312370
312370

output:

? 151 493 456
? 152 493 456
? 150 493 456
? 151 494 456
? 151 492 456
? 151 493 457
? 151 493 455
! 151 493 456

result:

ok ok, 7/150000 queries

Test #58:

score: 23
Accepted
time: 0ms
memory: 4092kb

input:

500 500 500 150000
1494364
1494365
49530105
1494365
1494365
1494364
1494364
1494364
1494364
1494365
1494365
1494364
1494364
1494364
49530102
49530108
1494365
1494365
52632852
1494365
53762973
60173256
60170814
1494365
60171444
1494365
60173010
1494365
1494365
1494365
1494365
60173259
60173307
601733...

output:

? 151 493 456
? 152 493 456
? 284 493 456
? 368 493 456
? 234 493 456
? 317 493 456
? 265 493 456
? 297 493 456
? 277 493 456
? 290 493 456
? 282 493 456
? 287 493 456
? 285 493 456
? 283 493 456
? 284 494 456
? 284 492 456
? 284 305 456
? 284 187 456
? 284 376 456
? 284 421 456
? 284 349 456
? 284 ...

result:

ok ok, 788/150000 queries

Test #59:

score: 23
Accepted
time: 5ms
memory: 4056kb

input:

500 500 500 150000
1322609
1322610
22655674
1322610
1322610
1322609
1322609
1322609
1322609
1322610
1322610
1322609
1322609
1322609
22655671
22655677
1322610
1322610
25758421
1322610
26888542
33298825
33296383
1322610
33297013
1322610
33298579
1322610
1322610
1322610
1322610
33298828
33298876
332989...

output:

? 151 493 456
? 152 493 456
? 284 493 456
? 368 493 456
? 234 493 456
? 317 493 456
? 265 493 456
? 297 493 456
? 277 493 456
? 290 493 456
? 282 493 456
? 287 493 456
? 285 493 456
? 283 493 456
? 284 494 456
? 284 492 456
? 284 305 456
? 284 187 456
? 284 376 456
? 284 421 456
? 284 349 456
? 284 ...

result:

ok ok, 788/150000 queries

Test #60:

score: 23
Accepted
time: 5ms
memory: 3908kb

input:

500 500 500 150000
1619933
1619934
12423880
1619934
1619934
1619933
1619933
1619933
1619933
1619934
1619934
1619933
1619933
1619933
12423877
12423884
1619934
1619934
15957265
1619934
17261062
24838339
24835390
1619934
24836151
1619934
24838042
1619934
1619934
1619934
1619934
24838342
24838400
248384...

output:

? 151 493 456
? 152 493 456
? 284 493 456
? 368 493 456
? 234 493 456
? 317 493 456
? 265 493 456
? 297 493 456
? 277 493 456
? 290 493 456
? 282 493 456
? 287 493 456
? 285 493 456
? 283 493 456
? 284 494 456
? 284 492 456
? 284 305 456
? 284 187 456
? 284 376 456
? 284 421 456
? 284 349 456
? 284 ...

result:

ok ok, 788/150000 queries

Test #61:

score: 23
Accepted
time: 2ms
memory: 3884kb

input:

500 500 500 150000
1312357
1312357
1312357
1312356
1312358
1312371
1312371
1312372
1312371
1312371
1312372
16994476
1312371
1312372
1312371
1312372
1312371
1312371
16994477
18479409
20909537
26474611
26478535
26487739
26488519
1312372
1312372
26488522
26488524
26488525
1312372
1312372
26488526
26488...

output:

? 151 493 456
? 152 493 456
? 150 493 456
? 151 494 456
? 151 492 456
? 151 305 456
? 151 187 456
? 151 116 456
? 151 71 456
? 151 143 456
? 151 98 456
? 151 88 456
? 151 81 456
? 151 92 456
? 151 85 456
? 151 90 456
? 151 87 456
? 151 89 456
? 152 88 456
? 284 88 456
? 368 88 456
? 418 88 456
? 450...

result:

ok ok, 335/150000 queries

Test #62:

score: 23
Accepted
time: 74ms
memory: 6276kb

input:

500 500 500 150000
400585546
400585545
400585547
400585604
400585640
400585662
400585676
400585681
400585676
400585681
400585679
400585683
400585682
400585682
400585682
400585684
400585871
400585989
400586060
400586105
400586115
400586098
400586122
400586115
400586122
400586119
400586124
400586123
4...

output:

? 151 493 456
? 152 493 456
? 150 493 456
? 93 493 456
? 57 493 456
? 35 493 456
? 21 493 456
? 12 493 456
? 7 493 456
? 16 493 456
? 10 493 456
? 14 493 456
? 15 493 456
? 13 493 456
? 14 494 456
? 14 492 456
? 14 305 456
? 14 187 456
? 14 116 456
? 14 71 456
? 14 43 456
? 14 26 456
? 14 54 456
? 1...

result:

ok ok, 37310/150000 queries

Test #63:

score: 23
Accepted
time: 76ms
memory: 5932kb

input:

500 500 500 150000
399942282
399942281
399942283
399942326
399942354
399942353
399942343
399942361
399942359
399942358
399942361
399942360
399942362
399942363
399942530
399942634
399942586
399942594
399942625
399942619
399942640
399942634
399942640
399942638
399942642
399942641
399942641
399942641
3...

output:

? 115 61 9
? 116 61 9
? 114 61 9
? 71 61 9
? 43 61 9
? 26 61 9
? 54 61 9
? 36 61 9
? 32 61 9
? 39 61 9
? 34 61 9
? 33 61 9
? 35 61 9
? 35 62 9
? 35 229 9
? 35 333 9
? 35 397 9
? 35 293 9
? 35 358 9
? 35 318 9
? 35 343 9
? 35 349 9
? 35 339 9
? 35 345 9
? 35 341 9
? 35 340 9
? 35 342 9
? 36 341 9
? 3...

result:

ok ok, 30330/150000 queries

Test #64:

score: 23
Accepted
time: 120ms
memory: 7800kb

input:

500 500 500 150000
399768997
399768996
399768998
399769026
399769018
399769015
399769029
399769025
399769030
399769028
399769031
399769030
399769032
399769151
399769225
399769271
399769295
399769277
399769288
399769288
399769295
399769292
399769297
399769296
399769296
399769296
399769296
399769298
3...

output:

? 75 187 292
? 76 187 292
? 74 187 292
? 46 187 292
? 28 187 292
? 57 187 292
? 39 187 292
? 35 187 292
? 42 187 292
? 44 187 292
? 41 187 292
? 40 187 292
? 41 188 292
? 41 307 292
? 41 381 292
? 41 427 292
? 41 455 292
? 41 473 292
? 41 444 292
? 41 462 292
? 41 451 292
? 41 458 292
? 41 453 292
?...

result:

ok ok, 63072/150000 queries

Test #65:

score: 23
Accepted
time: 30ms
memory: 5272kb

input:

500 500 500 150000
400008078
400008077
400008079
400008177
400008116
400008140
400008154
400008163
400008169
400008172
400008174
400008176
400008176
400008178
400008177
400008179
400008344
400008447
400008511
400008494
400008486
400008518
400008509
400008520
400008516
400008522
400008520
400008521
4...

output:

? 260 66 354
? 261 66 354
? 259 66 354
? 161 66 354
? 98 66 354
? 198 66 354
? 136 66 354
? 175 66 354
? 151 66 354
? 166 66 354
? 156 66 354
? 162 66 354
? 158 66 354
? 160 66 354
? 159 66 354
? 160 67 354
? 160 232 354
? 160 335 354
? 160 399 354
? 160 438 354
? 160 374 354
? 160 414 354
? 160 423...

result:

ok ok, 19638/150000 queries