#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define pll pair<ll,ll>
ll N, x, y, maxM, minM=3;
map<pll, int> anss; // 0 is unknown (default), 1 is true, 2 is false
string s;
bool is_in(ll x, ll y) {
if (anss[pll(x,y)]) {
return (anss[pll(x,y)])==1;
}
if (x<1 || x>N || y<1 || y>N) {
return false; // cannot go out of bounds.
}
cout << "examine " << x << ' ' << y << endl;
cin >> s;
if (s[0] == 't') {
anss[pll(x,y)] = 1;
return true;
} else {
anss[pll(x,y)] = 2;
return false;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//
cin >> N >> x >> y;
maxM = N/5;
if (maxM%2 == 0) maxM--;
anss[pll(x, y)] = 1; // in case this saves something
// binary search out the value of M some way
// right edge
ll lowR = x; // x could be the right edge
ll highR = min(N, x+maxM*3); // this is the edge of the map / edge of possibility
ll midR;
//cout << "BSEARCHING HIGHR" << endl;
while (highR-lowR > 1) {
midR = (highR+lowR)/2;
if (is_in(midR, y)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowR = midR;
} else {
highR = midR;
}
}
// notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
if (is_in(highR, y)) {
swap(lowR, highR);
}
//cout << "DONE" << endl;
// now, lowR is the edge for sure. just, which edge, we don't know.
// check if it could be [block w x] [gap] [block w lowR]
if (!is_in(x+(lowR-x)/2, y) ) {
// that means that it was the wrong edge. repeat the binary search.
highR = x+(lowR-x)/2;
lowR = x;
while (highR-lowR > 1) {
midR = (highR+lowR)/2;
if (is_in(midR, y)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowR = midR;
} else {
highR = midR;
}
}
// notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
if (is_in(highR, y)) {
swap(lowR, highR);
}
} else if (!is_in(x+(lowR-x)/4, y)) {
// check if it could be [block w x] [gap] [block] [gap] [block w edge]
// it's wrong, repeat binary search.
highR = x+(lowR-x)/4;
lowR = x;
while (highR-lowR > 1) {
midR = (highR+lowR)/2;
if (is_in(midR, y)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowR = midR;
} else {
highR = midR;
}
}
// notice that in the above loop, lowR is always in. highR is in iff it's the edge i think.
if (is_in(highR, y)) {
swap(lowR, highR);
}
}
// now, lowR must be an edge.
// repeat all this for highL.
// binary search out the value of M some way
// right edge
ll highL = x; // x could be the right edge
ll lowL = max((ll)1, x-maxM*3); // this is the edge of the map / edge of possibility
ll midL;
//cout << "BSEARHCING HIGHL" << endl;
while (highL-lowL > 1) {
midL = (highL+lowL)/2;
if (is_in(midL, y)) {
// means that this is within something - should go to the left (assume not a at a diff square)
highL = midL;
} else {
lowL = midL;
}
}
// notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
if (is_in(lowL, y)) {
swap(lowL, highL);
}
//cout << "DONE" << endl;
// now, highL is the edge for sure. just, which edge, we don't know.
// check if it could be [block w lowL] [gap] [block w x]
if (!is_in(x-(x-highL)/2, y) ) {
// that means that it was the wrong edge. repeat the binary search.
lowL = x-(x-lowL)/2;
highL = x;
while (highL-lowL > 1) {
midL = (highL+lowL)/2;
if (is_in(midL, y)) {
// means that this is within something - should go to the left (assume not a at a diff square)
highL = midL;
} else {
lowL = midL;
}
}
// notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
if (is_in(lowL, y)) {
swap(lowL, highL);
}
} else if (!is_in(x-(x-highL)/4, y)) {
// check if it could be [block w x] [gap] [block] [gap] [block w edge]
// it's wrong, repeat binary search.
lowL = x-(x-highL)/4;
highR = x;
while (highL-lowL > 1) {
midL = (highL+lowL)/2;
if (is_in(midL, y)) {
// means that this is within something - should go to the left (assume not a at a diff square)
highL = midL;
} else {
lowL = midL;
}
}
// notice that in the above loop, highL is always in. lowL is in iff it's the edge i think.
if (is_in(lowL, y)) {
swap(lowL, highL);
}
}
ll m = lowR - highL + 1;
//cout << "M = " << m << endl; // debug
//cout << "MAXM = " << maxM << endl;
// now binary search a vertical edge as well, to find out where we are
// binary search out the value of M some way
// right edge
ll lowV = y; // x could be the right edge
ll highV = min(N, y+maxM*3); // this is the edge of the map / edge of possibility
ll midV;
//cout << "BSEARCHING HIGHR" << endl;
while (highV-lowV > 1) {
midV = (highV+lowV)/2;
if (is_in(x, midV)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowV = midV;
} else {
highV = midV;
}
}
// notice that in the above loop, lowV is always in. highR is in iff it's the edge i think.
if (is_in(x, highV)) {
swap(lowV, highV);
}
//cout << "DONE" << endl;
// now, lowV is the edge for sure. just, which edge, we don't know.
// check if it could be [block w x] [gap] [block w lowV]
if (!is_in(x, y+(lowV-y)/2) ) {
// that means that it was the wrong edge. repeat the binary search.
highV = y+(lowV-y)/2;
lowV = y;
while (highV-lowV > 1) {
midV = (highV+lowV)/2;
if (is_in(x, midV)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowV = midV;
} else {
highV = midV;
}
}
// notice that in the above loop, lowR is always in. highV is in iff it's the edge i think.
if (is_in(x, highV)) {
swap(lowV, highV);
}
} else if (!is_in(x, y+(lowV-y)/4)) {
// check if it could be [block w x] [gap] [block] [gap] [block w edge]
// it's wrong, repeat binary search.
highV = y+(lowV-y)/4;
lowV = y;
while (highV-lowV > 1) {
midV = (highV+lowV)/2;
if (is_in(x, midV)) {
// means that this is within something - should go to the right (assume not a at a diff square)
lowV = midV;
} else {
highV = midV;
}
}
// notice that in the above loop, lowV is always in. highV is in iff it's the edge i think.
if (is_in(x, highV)) {
swap(lowV, highV);
}
}
// now, lowV must be an edge.
// GET POINTS !!
ll midX, midY;
midX = (lowR + highL) / 2;
midY = lowV - (m-1)/2;
// now, let's try going across diagonals to get to other points.
int num_topleft = 0;
for (int i=1; i<10; i++) {
if (is_in(midX-m*i, midY-m*i)) {
num_topleft = i;
} else {
break;
}
}
int num_bottomright = 0;
for (int i=1; i<10; i++) {
if (is_in(midX+m*i, midY+m*i)) {
num_bottomright = i;
} else {
break;
}
}
//cout << "NUM TOPLEFT " << num_topleft << "; num_bottomright " << num_bottomright << endl;
if (num_topleft + num_bottomright != 4) {
// it's either 4, 2 or 0.
// if it's 2 or 0, we find the right direction by going top right vs bottom left and seeing what works
int t = (4-num_topleft-num_bottomright)/2; // either 1 or 2
// try going topright
if (is_in(midX+2*m, midY-2*m)) {
midX += t*m;
midY -= t*m;
} else {
midX -= t*m;
midY += t*m;
}
}
// now, align across the other diagonal.
int num_topright = 0;
for (int i=1; i<10; i++) {
if (is_in(midX+m*i, midY-m*i)) {
num_topright = i;
} else {
break;
}
}
int num_bottomleft = 0;
for (int i=1; i<10; i++) {
if (is_in(midX-m*i, midY+m*i)) {
num_bottomleft = i;
} else {
break;
}
}
if (num_topright + num_bottomleft != 4) {
// it's either 4, 2 or 0.
// if it's 2 or 0, we find the right direction by going top right vs bottom left and seeing what works
int t = (4-num_topright-num_bottomleft)/2; // either 1 or 2
// try going topleft
if (is_in(midX-2*m, midY-2*m)) {
midX -= t*m;
midY -= t*m;
} else {
midX += t*m;
midY += t*m;
}
}
cout << "solution " << midX << ' ' << midY << endl;
return 0;
}
