#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;
bool ask(int i, int j) { return inside_shape(i,j); }
bool am_i_square(int n, int q) {
int t = 1, b = n, l = 1, r = n, lo = 1, hi = n;
while (lo < hi) {
int m = lo+(hi-lo)/2, yes = 0;
for (int i = 1; i <= n; i++) if (ask(m,i)) {yes = 1; break; }
if (yes) hi = m;
else lo = m+1;
}
t = lo, lo = t, hi = n;
while (lo < hi) {
int m = lo+(hi-lo+1)/2, yes = 0;
for (int i = 1; i <= n; i++)if (ask(m,i)) { yes = 1; break; }
if (yes) lo = m;
else hi = m-1;
}
b = lo, lo = 1, hi = n;
while (lo < hi) {
int m = lo+(hi-lo)/2, yes = 0;
for (int i = t; i <= b; i++) if (ask(i,m)) { yes = 1; break; }
if (yes) hi = m;
else lo = m+1;
}
l = lo, lo = l, hi = n;
while (lo < hi) {
int m = lo+(hi-lo+1)/2,yes = 0;
for (int i = t; i <= b; i++) if (ask(i,m)) { yes = 1; break; }
if (yes) lo = m;
else hi = m-1;
}
r = lo;
return b-t+1 == r-l+1;
}
