#include <bits/stdc++.h>
bool inside_shape(int X, int Y);
bool am_i_square(int N, int Q) {
std::vector asked(N + 1, std::vector<bool>(N + 1)), q(N + 1, std::vector<bool>(N + 1));
auto query = [&](int x, int y) -> bool {
if (x < 1 or x > N or y < 1 or y > N) {
return false;
}
if (asked[x][y]) {
return q[x][y];
}
asked[x][y] = true;
bool left = false, top = false;
for (int i = 0; i < N; ++i) {
left = left or q[i][y];
top = top or q[x][i];
}
if (left and top) {
return q[x][y] = true;
}
return q[x][y] = inside_shape(x, y);
};
const int gap = N / 5;
std::pair<int, int> t_l, t_r;
bool at_least_one = false;
for (int i = gap + 1; i <= N; i += gap) {
for (int j = gap + 1; j <= N; j += gap) {
if (!query(i, j)) {
continue;
}
at_least_one = true;
if (t_l.first == 0) {
t_l = {i, j};
}
if (t_l.first == i) {
t_r = {i, j};
}
}
}
auto binary_search = [&](const std::function<bool(int)> &f, int s, int d) {
int del = 0;
for (int i = 1 << int(std::log2(gap)); i >= 1; i /= 2) {
if (del + i <= gap) {
del += i * f(s + d * (del + i));
}
}
return s + d * del;
};
if (at_least_one) {
int TL_x = binary_search([&](int i) { return query(t_l.first, i); }, t_l.second, -1);
int TR_x = binary_search([&](int i) { return query(t_r.first, i); }, t_r.second, 1);
int TL_y = binary_search([&](int i) { return query(i, TL_x); }, t_l.first, -1);
int len = TR_x - TL_x + 1;
return query(TL_y + len - 1, TL_x) and !query(TL_y + len, TL_x);
} else {
int cnt = 0;
for (int i = 1; i <= N; i += gap) {
for (int j = 1; j <= N; j += gap) {
cnt += (i == 1 or j == 1) and query(i, j);
}
}
return cnt == 1;
}
}
