Ta có thể coi bài toán như 3 bài toán nhỏ liên quan đến nhau: Phiên bản 1-chiều, 2-chiều, và 3-chiều. Để tiện cho việc giải thích, ta sẽ gọi các ô đáp án là các cực trị.

Phiên bản 1-chiều:

Về cơ bản, để tìm một đáp án, ta sẽ giả sử một phần tử nào đó là cực trị trước. Và trong quá trình kiểm chứng nó là cực trị, ta sẽ lợi dụng những thông tin đã có để tìm các cực trị tiềm năng khác. Cụ thể như sau:

• Duy trì một bộ ba ~(l,m,r)~ thỏa mãn ~l < m < r~: Ban đầu ~l=0~ và ~r=N+1~, vậy thì chắc chắn ~H[l] \le H[m] \ge H[r]~.

• Tiếp theo, cho một ~m'~ bất kỳ thỏa mãn ~l < m' < m~.

  • Nếu ~H[m'] \le H[m]~, ta có thể gán ~r := m~, vì khi đó thì chắc chắn ~H[l] \le H[m'] \ge H[m]~.

  • Nếu ~H[m'] \ge H[m]~, ta có thể gán ~l := m'~, vì khi đó thì chắc chắn ~H[m'] \le H[m] \ge H[r]~.

  • Điều tương tự xảy ra nếu ta chọn ~m < m' < r~.

• Với bộ ba mới, quay về bước đầu. Khi bộ ba đã thỏa mãn ~l + 1 = m = r - 1~ thì ~m~ là một cực trị.

• Để thực hiện điều này tiết kiệm truy vấn, duy trì khoảng cách giữa các phần tử trong bộ ba theo tỉ lệ vàng. Phần chứng minh xin nhường bạn đọc.

Phiên bản 2-chiều:

Mở rộng phương pháp cho phiên bản 1-chiều cho phiên bản 2-chiều.

Phiên bản 3-chiều:

Nhận thấy bài toán cho phép sử dụng rất nhiều truy vấn. Một thuật toán duyệt ngây thơ + cải tiến bằng ngẫu nhiên trở nên khả thi hơn.

Nhắc lại một thuật toán ngây thơ sẽ dò những ô xung quanh nó và di chuyển đến ô có giá trị cao nhất cho đến khi trở thành cực trị.

Trong trường hợp tệ nhất, giả sử chỉ tồn tại một cực trị duy nhất, khi đó thì thuật toán ngây thơ sẽ sử dụng trên trung bình ~6 \cdot \frac{500^3}{2}~ truy vấn.

Để cải tiến, thay vì chọn một điểm duy nhất để bắt đầu thuật toán ngây thơ, ta chọn nhiều điểm bắt đầu, và chỉ thực sự bắt đầu thuật toán từ điểm có giá trị lớn nhất. Cụ thể, gọi số điểm bắt đầu là ~m~, kì vọng cho số truy vấn được sử dụng là:

$$E = 6 \cdot 500^3 \cdot \frac{1}{m+1} + m$$

Phần chứng minh xin nhường bạn đọc. Trong cả hai subtask, giá trị nhỏ nhất và điểm rơi của ~E~ đều nằm trong giới hạn bài toán.

/* https://oj.uz/submission/109708 */

// spoiled

#include <iostream>
#include <vector>
#include <cstring>
#include <random>
#include <algorithm>
#include <chrono>
#include <cassert>

using namespace std;

namespace Subtask1D
{

    const double RATIO = 1 - 2 / (1 + sqrt(5));

    int N;
    vector<int> A;

    int get(int i)
    {
        if (i <= 0 || i > N) return 0;
        if (A[i]) return A[i];
        cout << "? " << i << " 1 1" << endl;
        cin >> A[i];
        return A[i];
    }

    void run(int _N, int _Q)
    {
        N = _N;
        A.assign(N+1, 0);

        int l = 0, r = N+1, ml = l + (r - l) * RATIO, mr = r - int((r - l) * RATIO);
        while (l < ml && ml < mr && mr < r) {
            if (get(ml) < get(mr)) l = ml, ml = mr, mr = r - int((r - l) * RATIO);
            else r = mr, mr = ml, ml = l + (r - l) * RATIO;
        }
        for (int i = l + 1; i < r; ++i) {
            if (get(i) >= get(i-1) && get(i) >= get(i+1)) {
                cout << "! " << i << " 1 1" << endl;
                return;
            }
        }

        assert(0);
    }
}

namespace Subtask2D
{
    vector< vector<int> > A;

    int N, M, Q;

    int get(int i, int j)
    {
        if (0 >= i || i > N || 0 >= j || j > M) return 0;
        if (A[i][j]) return A[i][j];
        // return A[i][j] = 10000 - abs(i - 214) - abs(j - 532);
        cout << "? " << i << ' ' << j << " 1" << endl;
        cin >> A[i][j];
        return A[i][j];
    }

    void run(int _N, int _M, int _Q)
    {
        N = _N, M = _M, Q = _Q;
        A.assign(N + 1, vector<int>(M + 1, 0));
        int li = 1, ri = N, lj = 1, rj = M, maxi = 0, maxj = 1;

        while (li < ri || lj < rj) {
            if (li < ri) {
                int mi = (li + ri) >> 1, mj = rj;
                for (int j = lj; j < rj; ++j) {
                    if (get(mi, mj) <= get(mi, j)) mj = j;
                }

                if (get(mi, mj) <= get(maxi, maxj)) {
                    if (mi < maxi) li = mi + 1;
                    else ri = mi - 1;
                } else if (get(mi, mj) < get(mi + 1, mj)) {
                    maxi = mi, maxj = mj;
                    li = mi + 1;
                } else if (get(mi, mj) < get(mi - 1, mj)) {
                    maxi = mi, maxj = mj;
                    ri = mi - 1;
                } else {
                    assert(get(mi, mj) >= get(mi, mj - 1) && get(mi, mj) >= get(mi, mj + 1));
                    cout << "! " << mi << ' ' << mj << " 1" << endl;
                    return;
                }
            }

            if (lj < rj) {
                int mj = (lj + rj) >> 1, mi = ri;
                for (int i = li; i < ri; ++i) {
                    if (get(mi, mj) <= get(i, mj)) mi = i;
                }

                if (get(mi, mj) <= get(maxi, maxj)) {
                    if (mj < maxj) lj = mj + 1;
                    else rj = mj - 1;
                } else if (get(mi, mj) < get(mi, mj + 1)) {
                    maxi = mi, maxj = mj;
                    lj = mj + 1;
                } else if (get(mi, mj) < get(mi, mj - 1)) {
                    maxi = mi, maxj = mj;
                    rj = mj - 1;
                } else {
                    assert(get(mi, mj) >= get(mi - 1, mj) && get(mi, mj) >= get(mi + 1, mj));
                    cout << "! " << mi << ' ' << mj << " 1" << endl;
                    return; 
                }
            }
        }

        cout << "! " << li << ' ' << lj << " 1" << endl;
    }
}

namespace Subtask3D
{
    const int di[6] = {-1, 1, 0, 0, 0, 0}, dj[6] = {0, 0, -1, 1, 0, 0}, dk[6] = {0, 0, 0, 0, -1, 1};
    int dd[6] = {0, 1, 2, 3, 4, 5};
    vector< vector< vector<int> > > A;
    int N, M, K, Q;
    mt19937 rng(chrono::system_clock().now().time_since_epoch().count());
    uniform_int_distribution<int> rnd(1, 1e9);

    int rd(int l, int r) { return l + rnd(rng) % (r - l + 1); }

    int get(int i, int j, int k)
    {
        if (0 >= i || i > N || 0 >= j || j > M || 0 >= k || k > K) return 0;
        if (A[i][j][k]) return A[i][j][k];
        cout << "? " << i << ' ' << j << ' ' << k << endl;
        cin >> A[i][j][k];
        return A[i][j][k];
    }

    void run(int _N, int _M, int _K, int _Q)
    {
        N = _N, M = _M, K = _K, Q = _Q;
        A.assign(N+1, vector< vector<int> >(M+1, vector<int>(K+1, 0)));

        int i0 = 0, j0 = 0, k0 = 0;
        for (int _ = 0; _ < Q / 2; ++_) {
            int i = rd(1, N), j = rd(1, M), k = rd(1, K);
            if (get(i0, j0, k0) < get(i, j, k)) i0 = i, j0 = j, k0 = k;
        }

        while (true) {
            shuffle(dd, dd + 6, rng);

            int d = 0;
            for (; d < 6; ++d) {
                int i = i0 + di[dd[d]], j = j0 + dj[dd[d]], k = k0 + dk[dd[d]];
                if (get(i0, j0, k0) < get(i, j, k)) {
                    i0 = i, j0 = j, k0 = k;
                    break;
                }
            }

            if (d == 6) {
                cout << "! " << i0 << ' ' << j0 << ' ' << k0 << endl;
                return;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, M, K, Q; cin >> N >> M >> K >> Q;
    if (K > 1) Subtask3D::run(N, M, K, Q);
    else if (M > 1) Subtask2D::run(N, M, Q);
    else Subtask1D::run(N, Q);
}