Bạn đang tìm một vị trí trong đất để đặt một con giun, thú cưng của mình, Maximus. Khu vực tìm kiếm là một vùng hình hộp có kích thước \(N \times M \times K\) được chia thành lưới ba chiều gồm các ô hình lập phương. Các ô trong hộp được gắn nhãn \((x, y, z)\), tương ứng với tọa độ của chúng \((1 \leq x \leq N, 1 \leq y \leq M, 1 \leq z \leq K)\). Mỗi ô có độ ẩm nhất định \(H [x, y, z]\) là một số nguyên trong phạm vi \(1 ... 10^9\). Bạn có thể đo độ ẩm của bất kỳ ô nào bằng một cảm biến đặc biệt.

Maximus rất thích những nơi ẩm ướt, vì vậy bạn cần phải đưa nó vào một ô có độ ẩm ước ít nhất cũng bằng các ô lân cận, nếu không, nó sẽ bỏ đi và bạn sẽ khó tìm thấy nó. Nói cách khác, bạn cần đặt Maximus ở ô \((x, y, z)\), sao cho

\(H [x, y, z] \geq max (H [x + 1, y, z], H [x - 1, y, z], H [x, y + 1, z], H [x, y - 1, z], H [x, y, z + 1], H [x, y, z - 1])\)

trong đó một giá trị được coi là 0 khi nó nằm ngoài hộp (vì Maximus muốn ở trong hộp). Tuy nhiên, số lượng ô có thể rất lớn, vì vậy bạn không thể đo độ ẩm của tất cả các ô. Do đó, bạn chỉ có thể do một số lượng ô nhất định

Tương tác

Đầu tiên, bạn cần đọc vào bốn số nguyên \(N, M, K, Q\). Trong đó \(N, M, K\) là kích thước hình hộp và \(Q\) là số truy vấn bạn được hỏi. Sau đó bạn được phép hỏi chương trình các câu như sau:

• ? x y z: chương trình sẽ in ra giá trị \(H[x, y, z]\), lưu ý rằng bạn không được hỏi quá \(Q\) truy vấn này.
• ! x y z: vị trí bạn chọn cho Maximus. Lưu ý rằng bạn chỉ được trả lời một lần duy nhất và chương trình sẽ dừng lại sau đó. Câu trả lời cần thỏa mãn điều kiện đề bài.

Sau mỗi truy vấn bạn cần dùng endl hoặc flush.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm) \(M = K = 1, N = 1000000, Q = 10000\)
• Subtask 2 (22 điểm) \(M = K = 1, N = 1000000, Q = 35\)
• Subtask 3 (12 điểm) \(K = 1, N = M = 200, Q = 4000\)
• Subtask 4 (19 điểm) \(K = 1, N = M = 1000, Q = 3500\)
• Subtask 5 (14 điểm) \(N = M = K = 100, Q = 10000\)
• Subtask 6 (23 điểm) \(N = M = K = 500, Q = 15000\)

Điểm tối đa của bài là \(100\) điểm. Để đạt được điểm của một subtask, bạn cần làm đúng tất cả test trong subtask đó.

Ví dụ

Máy chấm	Chương trình của bạn
3 1 1 3
	? 1 1 1
1
	? 2 1 1
1
	? 3 1 1
3
	! 3 1 1