QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90881#41. Worm WorriesHe_Ren100 ✓399ms7448kbC++233.3kb2023-03-26 02:15:222023-03-26 02:15:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 02:15:23]
  • 评测
  • 测评结果:100
  • 用时:399ms
  • 内存:7448kb
  • [2023-03-26 02:15:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct Vector {
    int x, y, z;
    Vector(void) {}
    Vector(int _x, int _y, int _z): x(_x), y(_y), z(_z) {}
    bool operator < (Vector oth) const {
        if (x != oth.x)
            return x < oth.x;

        if (y != oth.y)
            return y < oth.y;

        if (z != oth.z)
            return z < oth.z;

        return 0;
    }
};
Vector operator + (Vector p, Vector q) {
    return Vector(p.x + q.x, p.y + q.y, p.z + q.z);
}

int n, m, d;

map< tuple<int, int, int>, int > asked;

int ask(int x, int y, int z) {
    if (x < 1 || x > n || y < 1 || y > m || z < 1 || z > d)
        return 0;

    auto cur = make_tuple(x, y, z);

    if (asked.count(cur))
        return asked[cur];

    printf("? %d %d %d\n", x, y, z);
    fflush(stdout);
    int res;
    scanf("%d", &res);

    return asked[cur] = res;
}
void answer(int x, int y, int z) {
    printf("! %d %d %d\n", x, y, z);
    fflush(stdout);
    exit(0);
}

int ask(Vector p) {
    return ask(p.x, p.y, p.z);
}
void answer(Vector p) {
    answer(p.x, p.y, p.z);
}

void solve1(void) {
    int l = 1, r = n;
    int vl = ask(l, 1, 1), vr = ask(r, 1, 1);

    while (r - l + 1 > 5) {
        int mid = (l + r) >> 1;

        int x = ask(mid, 1, 1);

        if (x <= vl) {
            r = mid;
            vr = x;
            continue;
        }

        if (x <= vr) {
            l = mid;
            vl = x;
            continue;
        }

        int y = ask(mid + 1, 1, 1);

        if (x >= y)
            r = mid, vr = x;
        else
            l = mid + 1, vl = y;
    }

    int x = 0, y = vl;

    for (int i = l + 1; i <= r; ++i) {
        int z = i == r ? vr : ask(i, 1, 1);

        if (y >= x && y >= z)
            answer(i - 1, 1, 1);

        x = y;
        y = z;
    }

    answer(r, 1, 1);
}

void solve2(void) {

}

void solve3(int num) {
    mt19937 gen(114514);

    int dx[] = {1, -1, 0, 0, 0, 0};
    int dy[] = {0, 0, 1, -1, 0, 0};
    int dz[] = {0, 0, 0, 0, 1, -1};
    Vector delta[6];

    for (int i = 0; i < 6; ++i)
        delta[i] = Vector(dx[i], dy[i], dz[i]);

    vector< pair<int, Vector>> vec;

    for (int i = 1; i <= num; ++i) {
        int x = uniform_int_distribution<int>(1, n)(gen);
        int y = uniform_int_distribution<int>(1, m)(gen);
        int z = uniform_int_distribution<int>(1, d)(gen);
        vec.emplace_back(ask(x, y, z), Vector(x, y, z));
    }

    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());

    Vector u = vec[0].second;

    while (1) {
        int my = ask(u);

        int val[6];

        for (int i = 0; i < 6; ++i)
            val[i] = ask(u + delta[i]);

        int pos = max_element(val, val + 6) - val;

        if (val[pos] <= my) {
            answer(u);
        }

        u = u + delta[pos];
    }
}

int main(void) {
    int Q;
    scanf("%d%d%d%d", &n, &m, &d, &Q);
    string t;
    getline(cin, t);

    if (m == 1 && d == 1) {
        solve1();
    }

    if (d == 1) {
        if (Q == 4000)
            solve3(1e3);
        else
            solve3(1.5e3);
    }

    solve3(2e4);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

1000000 1 1 10000
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/10000 queries

Test #2:

score: 0
Accepted
time: 4ms
memory: 3524kb

input:

1000000 1 1 10000
19811
1019810
519810
769810
894810
957310
988560
1004185
1011997
1015903
1017856
1018833
1019321
1019565
1019687
1019748
1019779
1019794
1019802
1019806
1019807
1019808
1019809

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 750000 1 1
? 875000 1 1
? 937500 1 1
? 968750 1 1
? 984375 1 1
? 992187 1 1
? 996093 1 1
? 998046 1 1
? 999023 1 1
? 999511 1 1
? 999755 1 1
? 999877 1 1
? 999938 1 1
? 999969 1 1
? 999984 1 1
? 999992 1 1
? 999996 1 1
? 999997 1 1
? 999998 1 1
? 999999 1 1
! 100...

result:

ok ok, 23/10000 queries

Test #3:

score: 0
Accepted
time: 4ms
memory: 3684kb

input:

1000000 1 1 10000
1019810
19811
519811
769811
894811
957311
988561
1004186
1011998
1015904
1017857
1018834
1019322
1019566
1019688
1019749
1019780
1019795
1019803
1019807
1019809

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/10000 queries

Test #4:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

1000000 1 1 10000
84633977
20941639
70941639
95941639
95941539
108441639
108441539
114691639
114691539
117816639
117816539
86196377
118597939
118597839
118988539
118988439
86391677
86489277
119037439
119037339
86513677
119049639
119049539
119055739
119055639
119058839
119058739
119060339
119060239
8...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 1 1
? 18860 1...

result:

ok ok, 34/10000 queries

Test #5:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

1000000 1 1 10000
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/10000 queries

Subtask #2:

score: 22
Accepted

Test #6:

score: 22
Accepted
time: 3ms
memory: 3564kb

input:

1000000 1 1 35
32198112
312371
74918191
32104285
58843316
126838952
17127579
105112322
80515805
63904677
39247311
60791391
46469853
73552345
119752322
119782322
66232345
62572345
60742345
59842345
59392345
119992322
120022322
120112322
59302345
120052322
120082322

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 500001 1 1
? 250000 1 1
? 375000 1 1
? 375001 1 1
? 312500 1 1
? 343750 1 1
? 328125 1 1
? 320312 1 1
? 316406 1 1
? 314453 1 1
? 313476 1 1
? 312988 1 1
? 312989 1 1
? 313232 1 1
? 313110 1 1
? 313049 1 1
? 313019 1 1
? 313004 1 1
? 312996 1 1
? 312997 1 1
? 313...

result:

ok ok, 27/35 queries

Test #7:

score: 0
Accepted
time: 3ms
memory: 3580kb

input:

1000000 1 1 35
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/35 queries

Test #8:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

1000000 1 1 35
19811
1019810
519810
769810
894810
957310
988560
1004185
1011997
1015903
1017856
1018833
1019321
1019565
1019687
1019748
1019779
1019794
1019802
1019806
1019807
1019808
1019809

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 750000 1 1
? 875000 1 1
? 937500 1 1
? 968750 1 1
? 984375 1 1
? 992187 1 1
? 996093 1 1
? 998046 1 1
? 999023 1 1
? 999511 1 1
? 999755 1 1
? 999877 1 1
? 999938 1 1
? 999969 1 1
? 999984 1 1
? 999992 1 1
? 999996 1 1
? 999997 1 1
? 999998 1 1
? 999999 1 1
! 100...

result:

ok ok, 23/35 queries

Test #9:

score: 0
Accepted
time: 3ms
memory: 3632kb

input:

1000000 1 1 35
1019810
19811
519811
769811
894811
957311
988561
1004186
1011998
1015904
1017857
1018834
1019322
1019566
1019688
1019749
1019780
1019795
1019803
1019807
1019809

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/35 queries

Test #10:

score: 0
Accepted
time: 2ms
memory: 3528kb

input:

1000000 1 1 35
84633977
20941639
70941639
95941639
95941539
108441639
108441539
114691639
114691539
117816639
117816539
86196377
118597939
118597839
118988539
118988439
86391677
86489277
119037439
119037339
86513677
119049639
119049539
119055739
119055639
119058839
119058739
119060339
119060239
8651...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 1 1
? 18860 1...

result:

ok ok, 34/35 queries

Test #11:

score: 0
Accepted
time: 4ms
memory: 3632kb

input:

1000000 1 1 35
84931301
84931401
134931401
134931301
159931401
159931301
172431401
172431301
178681401
178681301
181806401
181806301
86493701
182587701
182587601
182978301
182978201
86689001
86786601
183027201
183027101
86811001
183039401
183039301
183045501
183045401
183048601
183048501
183050101
1...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 500001 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 ...

result:

ok ok, 35/35 queries

Test #12:

score: 0
Accepted
time: 4ms
memory: 3500kb

input:

1000000 1 1 35
84633977
20941639
70941639
95941639
95941539
108441639
108441539
114691639
114691539
117816639
117816539
86196377
118597939
118597839
118988539
118988439
86391677
86489277
119037439
119037339
86513677
119049639
119049539
119055739
119055639
119058839
119058739
119060339
119060239
8651...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 1 1
? 18860 1...

result:

ok ok, 34/35 queries

Test #13:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

1000000 1 1 35
84931301
84931401
134931401
134931301
159931401
159931301
172431401
172431301
178681401
178681301
181806401
181806301
86493701
182587701
182587601
182978301
182978201
86689001
86786601
183027201
183027101
86811001
183039401
183039301
183045501
183045401
183048601
183048501
183050101
1...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 500001 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 ...

result:

ok ok, 35/35 queries

Test #14:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

1000000 1 1 35
10312369
10312466
67256239
67256101
108084829
108084629
137807074
137806780
160219873
160219414
178919464
178918604
122116810
187266295
187264885
195165498
195161925
151667086
178103535
197397071
197390768
195317423
198309788
198300622
198983453
198969682
199521506
199498578
200041106...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 500001 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 ...

result:

ok ok, 35/35 queries

Test #15:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

1000000 1 1 35
10312369
10312660
135059823
135059619
178581621
178581480
193547752
193547657
198527189
198527128
200041162
200041129
187067763
200250861
200250841
200308593
200308585
197123660
200008931
200311683
200311679
200308917
200312147
200312144
200312304
200312302
200312356
200312355
2003123...

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 500001 1 1
? 250000 1 1
? 250001 1 1
? 125000 1 1
? 125001 1 1
? 62500 1 1
? 62501 1 1
? 31250 1 1
? 31251 1 1
? 15625 1 1
? 23437 1 1
? 23438 1 1
? 19531 1 1
? 19532 1 1
? 17578 1 1
? 18554 1 1
? 19042 1 1
? 19043 1 1
? 18798 1 1
? 18920 1 1
? 18921 1 1
? 18859 ...

result:

ok ok, 35/35 queries

Test #16:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1000000 1 1 35
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370

output:

? 1 1 1
? 1000000 1 1
? 500000 1 1
? 250000 1 1
? 125000 1 1
? 62500 1 1
? 31250 1 1
? 15625 1 1
? 7813 1 1
? 3907 1 1
? 1954 1 1
? 977 1 1
? 489 1 1
? 245 1 1
? 123 1 1
? 62 1 1
? 31 1 1
? 16 1 1
? 8 1 1
? 4 1 1
? 2 1 1
! 1 1 1

result:

ok ok, 21/35 queries

Subtask #3:

score: 12
Accepted

Test #17:

score: 12
Accepted
time: 14ms
memory: 3628kb

input:

200 200 1 4000
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
198...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 993/4000 queries

Test #18:

score: 0
Accepted
time: 15ms
memory: 3660kb

input:

200 200 1 4000
20113
20069
20158
20014
20019
19876
20103
19977
20022
19934
20096
19929
20047
20076
19986
19917
20043
20099
20103
20071
20000
20044
20004
20013
19873
19965
20002
20091
19978
19974
20111
19932
19993
19876
20037
19918
19955
19941
19822
19990
20135
19852
19987
20139
20102
20121
19950
200...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 998/4000 queries

Test #19:

score: 0
Accepted
time: 8ms
memory: 3664kb

input:

200 200 1 4000
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
31237...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 993/4000 queries

Test #20:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

200 200 1 4000
1325573
1330753
1327942
1312372
1331895
1316144
1324663
1312371
1323322
1312792
1326576
1315737
1312371
1312372
1313672
1312477
1324123
1327619
1312371
1320471
1312372
1312372
1325898
1312371
1312371
1312371
1312372
1312371
1323708
1312372
1327719
1312372
1312371
1312372
1322517
13123...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 1090/4000 queries

Test #21:

score: 0
Accepted
time: 4ms
memory: 3768kb

input:

200 200 1 4000
82810973
56910973
70965973
1494365
51200973
40968297
87360973
1494364
94065973
24208297
77795973
38933297
1494364
1494365
28608297
22633297
90060973
72580973
1494364
108320973
1494365
1494365
81185973
1494364
1494364
1494364
1494365
1494364
92135973
1494365
72080973
1494365
1494364
14...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 1031/4000 queries

Test #22:

score: 0
Accepted
time: 15ms
memory: 3644kb

input:

200 200 1 4000
1031334
1029242
1023215
1019813
1027480
1027665
1032824
1019812
1019813
1019813
1028497
1033510
1019812
1037083
1026225
1020502
1035704
1023156
1019812
1032432
1033641
1019813
1029001
1019812
1019812
1019812
1022319
1019812
1031715
1022737
1024600
1031153
1019812
1029435
1038538
10198...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 994/4000 queries

Test #23:

score: 0
Accepted
time: 8ms
memory: 3668kb

input:

200 200 1 4000
143233980
132773980
102638980
1322610
123963980
124888980
150683980
1322609
1322610
1322610
129048980
154113980
1322609
171978980
117688980
89073980
165083980
102343980
1322609
148723980
154768980
1322610
131568980
1322609
1322609
1322609
98158980
1322609
145138980
100248980
109563980...

output:

? 138 166 1
? 174 86 1
? 157 192 1
? 197 8 1
? 180 30 1
? 24 43 1
? 134 160 1
? 31 137 1
? 80 133 1
? 116 9 1
? 111 176 1
? 76 44 1
? 131 107 1
? 138 129 1
? 159 18 1
? 106 2 1
? 88 146 1
? 98 192 1
? 101 193 1
? 162 100 1
? 46 145 1
? 46 189 1
? 28 167 1
? 7 197 1
? 53 11 1
? 21 135 1
? 8 185 1
? 1...

result:

ok ok, 1030/4000 queries

Subtask #4:

score: 19
Accepted

Test #24:

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

input:

1000 1000 1 3500
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
1...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 1503/3500 queries

Test #25:

score: 0
Accepted
time: 33ms
memory: 3812kb

input:

1000 1000 1 3500
20671
21250
20638
21755
21560
20717
20682
20281
20544
21344
20486
20968
20930
20855
21512
21329
20520
20343
20351
21119
20316
20095
20116
19860
21022
20241
19927
20832
20346
21556
20442
20552
21062
20861
20691
21125
21292
21101
20824
20242
20870
20995
20920
21048
20589
20851
21368
2...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 1592/3500 queries

Test #26:

score: 0
Accepted
time: 25ms
memory: 3620kb

input:

1000 1000 1 3500
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 1503/3500 queries

Test #27:

score: 0
Accepted
time: 27ms
memory: 3744kb

input:

1000 1000 1 3500
1312372
1312371
1787217
1312372
1458815
1362458
1312371
1381040
1312371
1418487
1312371
1488167
1312371
1312372
1436107
1312372
1695383
1312372
1726720
1600360
1312371
1312372
1372859
1312367
1312371
1312372
1312372
1312371
1312371
1312371
1312371
1396639
1312371
1399842
1312372
131...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2942/3500 queries

Test #28:

score: 0
Accepted
time: 25ms
memory: 3856kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #29:

score: 0
Accepted
time: 16ms
memory: 3672kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #30:

score: 0
Accepted
time: 11ms
memory: 3836kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #31:

score: 0
Accepted
time: 13ms
memory: 3768kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #32:

score: 0
Accepted
time: 13ms
memory: 3804kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #33:

score: 0
Accepted
time: 9ms
memory: 3748kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #34:

score: 0
Accepted
time: 9ms
memory: 3800kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #35:

score: 0
Accepted
time: 18ms
memory: 3768kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #36:

score: 0
Accepted
time: 11ms
memory: 3812kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #37:

score: 0
Accepted
time: 4ms
memory: 3728kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #38:

score: 0
Accepted
time: 20ms
memory: 3696kb

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #39:

score: 0
Accepted
time: 9ms
memory: 3700kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #40:

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

input:

1000 1000 1 3500
67726373
1494364
61806173
1494365
47679297
38009897
1494364
78617173
1494364
29880897
1494364
43522497
1494364
71006697
27866497
24101097
80161697
59718373
59778373
64948297
1494364
1494365
71795373
1494364
1494364
1494365
1494365
1494364
1494364
1494364
1494364
79670573
1494364
149...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #41:

score: 0
Accepted
time: 20ms
memory: 3756kb

input:

1000 1000 1 3500
67642362
1619933
47892455
1619934
55652725
37603009
1619933
115034078
1619933
23841036
1619933
47633807
1619933
113255905
20592439
14671347
151512752
41507514
41687450
95253355
1619933
1619934
83109998
1619933
1619933
1619934
1619934
1619933
1619933
1619933
1619933
121083807
1619933...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2176/3500 queries

Test #42:

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

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #43:

score: 0
Accepted
time: 13ms
memory: 3740kb

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #44:

score: 0
Accepted
time: 21ms
memory: 3724kb

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #45:

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

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #46:

score: 0
Accepted
time: 37ms
memory: 3784kb

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #47:

score: 0
Accepted
time: 18ms
memory: 3712kb

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Test #48:

score: 0
Accepted
time: 15ms
memory: 3680kb

input:

1000 1000 1 3500
1322610
1322609
104786142
114297142
84835342
80905142
1322609
1322610
1322609
105222542
1322609
53332942
1322609
36221142
89321742
88704580
42611342
1322610
1322610
1322610
1322609
1322610
74800942
1322609
1322609
85827542
107883142
1322609
1322609
1322609
1322609
64400142
1322609
7...

output:

? 688 827 1
? 867 427 1
? 784 956 1
? 982 37 1
? 898 148 1
? 118 211 1
? 669 797 1
? 155 684 1
? 397 663 1
? 578 44 1
? 555 879 1
? 378 220 1
? 651 531 1
? 690 645 1
? 792 90 1
? 527 8 1
? 438 728 1
? 490 957 1
? 504 963 1
? 809 500 1
? 229 723 1
? 226 941 1
? 138 832 1
? 33 983 1
? 265 53 1
? 102 6...

result:

ok ok, 2397/3500 queries

Subtask #5:

score: 14
Accepted

Test #49:

score: 14
Accepted
time: 117ms
memory: 5196kb

input:

100 100 100 100000
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19813/100000 queries

Test #50:

score: 0
Accepted
time: 128ms
memory: 5204kb

input:

100 100 100 100000
19993
20016
20005
19990
19938
19879
20041
19988
19943
19932
20034
19967
20020
20028
19974
19904
19971
20019
19994
19987
19988
19960
19966
19912
19858
19933
19978
19981
19906
19917
19963
19917
19945
19905
20007
19954
19919
19948
19911
19942
20033
19861
19934
20014
20048
19972
19949...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19828/100000 queries

Test #51:

score: 0
Accepted
time: 124ms
memory: 5188kb

input:

100 100 100 100000
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
3...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19813/100000 queries

Test #52:

score: 0
Accepted
time: 120ms
memory: 5104kb

input:

100 100 100 100000
1322609
1322608
1322609
1322610
1322610
26521942
1322609
1322610
1322609
1322610
90755942
44539942
94688742
1322608
1322610
1322607
1322609
1322609
1322608
1322609
1322608
1322608
1322610
1322610
28543142
1322609
1322610
59533942
1322610
1322609
1322609
33604342
1322609
30535942
1...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19943/100000 queries

Test #53:

score: 0
Accepted
time: 199ms
memory: 5100kb

input:

100 100 100 100000
1619933
1619932
1619933
1619934
1619934
17513393
1619933
1619934
1619933
1619934
147066302
142704378
168710355
1619932
1619934
1619931
1619933
1619933
1619932
1619933
1619932
1619932
1619934
1619934
20174871
1619933
1619934
67437785
1619934
1619933
1619933
27017254
1619933
4770152...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19943/100000 queries

Test #54:

score: 0
Accepted
time: 213ms
memory: 5148kb

input:

100 100 100 100000
400854978
400854995
400854944
400854943
400854925
400854940
400855006
400854985
400854992
400854983
400855013
400854972
400855013
400855019
400854969
400854965
400855008
400855010
400854983
400854992
400854999
400854953
400854981
400854897
400854919
400854980
400854971
400856526
4...

output:

? 69 83 68
? 87 43 23
? 79 96 79
? 99 4 22
? 90 15 76
? 12 22 64
? 67 80 15
? 16 69 6
? 40 67 73
? 58 5 40
? 56 88 19
? 38 22 2
? 66 54 9
? 69 65 15
? 80 9 24
? 53 1 59
? 44 73 55
? 49 96 35
? 51 97 63
? 81 50 53
? 23 73 17
? 23 95 67
? 14 84 41
? 4 99 100
? 27 6 84
? 11 68 55
? 4 93 28
? 72 70 70
?...

result:

ok ok, 19979/100000 queries

Subtask #6:

score: 23
Accepted

Test #55:

score: 23
Accepted
time: 206ms
memory: 5108kb

input:

500 500 500 150000
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815
19815...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 20004/150000 queries

Test #56:

score: 0
Accepted
time: 98ms
memory: 5076kb

input:

500 500 500 150000
20541
20476
20501
20229
20055
20541
20800
21048
20578
20343
20880
20725
20709
20715
20341
20257
20683
20871
20727
20393
20972
20837
20953
20787
20288
20824
21112
20452
20606
20064
20512
20671
20399
20597
20793
20603
20251
20529
20779
20804
20580
20368
20437
20390
20884
20325
20378...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 20155/150000 queries

Test #57:

score: 0
Accepted
time: 160ms
memory: 5104kb

input:

500 500 500 150000
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
312370
3...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 20004/150000 queries

Test #58:

score: 0
Accepted
time: 222ms
memory: 5692kb

input:

500 500 500 150000
73259697
125508246
1494365
1494363
1494365
88662273
1494364
26468085
1494364
1494365
30657657
1494365
127412061
1494363
1494365
75844101
1494365
1494363
78490371
1494365
1494364
1494363
95114607
1494365
1494364
1494364
1494364
1494364
1494364
1494364
1494364
92383809
1494363
95677...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 28914/150000 queries

Test #59:

score: 0
Accepted
time: 174ms
memory: 5684kb

input:

500 500 500 150000
46385266
98633815
1322610
1322608
1322610
61787842
1322609
26296330
1322609
1322610
30485902
1322610
100537630
1322608
1322610
48969670
1322610
1322608
51615940
1322610
1322609
1322608
68240176
1322610
1322609
1322609
1322609
1322609
1322609
1322609
1322609
65509378
1322608
688034...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 28914/150000 queries

Test #60:

score: 0
Accepted
time: 222ms
memory: 5684kb

input:

500 500 500 150000
41415966
143644708
1619934
1619932
1619934
63452774
1619933
63842322
1619933
1619934
151472608
1619934
151138110
1619932
1619934
44897042
1619934
1619932
48543454
1619934
1619933
1619932
73808542
1619934
1619933
1619933
1619933
1619933
1619933
1619933
1619933
69326730
1619932
7475...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 28914/150000 queries

Test #61:

score: 0
Accepted
time: 249ms
memory: 5916kb

input:

500 500 500 150000
7773260
22697403
1312372
1312369
1312372
1312372
1312371
1854571
1312371
1312372
6112563
1312356
10547120
1312370
1312372
1312364
9578880
1312370
1312368
1312372
1312371
1312370
1312372
1312327
1312371
1312371
1312359
1312371
1312371
1312371
1312368
4700952
1312370
1312372
1312370...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 32785/150000 queries

Test #62:

score: 0
Accepted
time: 181ms
memory: 5412kb

input:

500 500 500 150000
400585549
400585570
400585381
400585637
400585743
400586165
400585444
400585710
400585750
400585933
400585478
400585811
400585553
400585509
400585767
400585989
400585791
400585553
400585599
400585711
400585712
400585731
400585823
400585639
400586020
400585988
400585764
400585594
4...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 25028/150000 queries

Test #63:

score: 0
Accepted
time: 399ms
memory: 7448kb

input:

500 500 500 150000
399942590
399942221
399942480
399941964
399942308
399942690
399942349
399942615
399942825
399942260
399942383
399942254
399942308
399942378
399942094
399942360
399942698
399942458
399942588
399942434
399942617
399942756
399942728
399942702
399942541
399942883
399942637
399942651
3...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 55920/150000 queries

Test #64:

score: 0
Accepted
time: 166ms
memory: 5288kb

input:

500 500 500 150000
399769002
399768487
399768912
399768230
399768516
399768956
399768731
399768883
399769039
399768526
399768847
399768520
399768574
399768644
399768360
399768626
399769010
399768948
399769078
399768700
399768925
399769246
399769144
399769122
399768749
399769149
399769115
399768913
3...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 22738/150000 queries

Test #65:

score: 0
Accepted
time: 361ms
memory: 7080kb

input:

500 500 500 150000
400008337
400007830
400008181
400007573
400007871
400008097
400008074
400008062
400008394
400007869
400008130
400007863
400007917
400007987
400007703
400007969
400008353
400008205
400008335
400008043
400008178
400008409
400008293
400008153
400008050
400008274
400008134
400008268
4...

output:

? 344 414 339
? 434 214 114
? 392 478 395
? 491 19 109
? 449 74 380
? 59 106 316
? 335 399 74
? 78 342 26
? 199 332 365
? 289 22 200
? 278 440 92
? 189 110 6
? 326 266 41
? 345 323 73
? 396 45 118
? 264 4 293
? 219 364 272
? 245 479 173
? 252 482 313
? 405 250 262
? 115 362 85
? 113 471 331
? 69 416...

result:

ok ok, 50899/150000 queries