#include using namespace std; struct Point { int x, y; Point(int x_, int y_) { x = x_; y = y_; }; }; int W, H; vector P; map Sky, Sea; vector Hor; bool check(map& M, int x, int y) { map::iterator it = M.find(x); if(it == M.end()) { map::iterator itR = M.upper_bound(x); map::iterator itL = itR; itL--; if((itR->first - itL->first) * (y - itL->second) <= (x - itL->first) * (itR->second - itL->second)) return true; } else { if(y <= it->second) return true; } return false; } void add(map& M, int x, int y) { M[x] = y; map::iterator it = M.find(x); map::iterator itR = it; itR++; if(itR != M.end()) { map::iterator itRR = itR; itRR++; while(itRR != M.end()) { if((itR->first - x) * (itRR->second - itR->second) < (itR->second - y) * (itRR->first - itR->first)) break; M.erase(itR); itR = itRR; itRR++; } } map::reverse_iterator itL = make_reverse_iterator(it); if(itL != M.rend()) { map::reverse_iterator itLL = itL; itLL++; while(itLL != M.rend()) { if((itL->first - x) * (itLL->second - itL->second) > (itL->second - y) * (itLL->first - itL->first)) break; M.erase(itLL.base()); itLL = itL; itLL++; } } } int main() { srand(time(0)); cin >> W >> H; for(int i = 1; i <= W; i++) for(int j = 1; j <= H; j++) P.push_back(Point(i, j)); random_shuffle(P.begin(), P.end()); Sky[1] = 1; Sky[W] = 1; Sea[1] = 1; Sea[W] = 1; for(int i = 0; i < P.size(); i++) { // cerr << "Checking " << P[i].x << " " << P[i].y << endl; if(check(Sea, P[i].x, P[i].y)) { // cerr << P[i].x << " " << P[i].y << " IS SEA" << endl; continue; } if(check(Sky, P[i].x, H + 1 - P[i].y)) { // cerr << P[i].x << " " << P[i].y << " IS SKY" << endl; continue; } cout << "? " << P[i].x << " " << P[i].y << endl; string s; cin >> s; if(s.compare("horizon") == 0) { Hor.push_back(P[i]); if(Hor.size() == 2) { cout << "! " << Hor[0].x << " " << Hor[0].y << " " << Hor[1].x << " " << Hor[1].y << endl; return 0; } } if(s.compare("sky") == 0) add(Sky, P[i].x, H + 1 - P[i].y); if(s.compare("sea") == 0) add(Sea, P[i].x, P[i].y); } return 0; }