#include "squarerect.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 2 * 1e5 + 15;
// static int T;
// static int N, Q, X1, X2, Y1, Y2, q;
// bool inside_shape(int X, int Y) {
// q++;
// if (q > Q) {
// printf("Wrong Answer. Used too many queries.\n");
// exit(0);
// }
// if (X <= 0 || X > N || Y <= 0 || Y > N) {
// cout << X << ' ' << Y << '\n';
// printf("Wrong Answer. Query parameters out of range.\n");
// exit(0);
// }
// return (X >= X1 && X <= X2 && Y >= Y1 && Y <= Y2);
// }
int n;
bool inside_shape1(int x, int y) {
if (x <= 0 || x > n || y <= 0 || y > n) return 0;
return inside_shape(x, y);
}
bool f[10][10], flg;
bool am_i_square(int _n, int _q) {
n = _n; flg = 0;
for (int i = 0; i <= 9; i++)
for (int j = 0; j <= 9; j++) f[i][j] = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
f[i][j] = inside_shape1(20 * i, 20 * j);
flg |= f[i][j];
// cout << 20 * i << ' ' << 20 * j << ' ' << f[i][j] << '\n';
}
}
if (flg) {
int mnx = 5, mxx = 0, mny = 5, mxy = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (!f[i][j]) continue;
mnx = min(mnx, i); mxx = max(mxx, i);
mny = min(mny, j); mxy = max(mxy, j);
}
}
int U, D, L, R;
int l = (mnx - 1) * 20, r = mnx * 20, m;
while (l < r) {
m = (l + r) / 2;
if (inside_shape1(m, mny * 20)) r = m;
else l = m + 1;
} U = l;
l = mxx * 20; r = (mxx + 1) * 20;
while (l < r) {
m = (l + r + 1) / 2;
if (inside_shape1(m, mny * 20)) l = m;
else r = m - 1;
} D = l;
l = (mny - 1) * 20; r = mny * 20;
while (l < r) {
m = (l + r) / 2;
if (inside_shape1(mnx * 20, m)) r = m;
else l = m + 1;
} L = l;
R = L + D - U;
// cout << L << ' ' << R << ' ' << U << ' ' << D << '\n';
if (inside_shape1(mnx * 20, R) && !inside_shape1(mnx * 20, R + 1)) return 1;
return 0;
}
for (int i = 1; i <= 5; i++) {
f[i][5] = inside_shape1(20 * i, 100);
if (i != 5) f[5][i] = inside_shape1(100, 20 * i);
flg |= f[i][5]; flg |= f[5][i];
}
if (!flg) return 0;
int x = -1, y = -1;
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 5; j++) {
if (f[i][j]) {
if (x != -1) return 0;
x = i; y = j;
}
}
}
if (x == 5) {
int l = (y - 1) * 20 + 1, r = y * 20, m;
while (l < r) {
m = (l + r) / 2;
if (inside_shape1(100, m)) r = m;
else l = m + 1;
}
if (inside_shape1(100, l + 19) && !inside_shape1(100, l + 20)) return 1;
return 0;
}
int l = (x - 1) * 20 + 1, r = x * 20, m;
while (l < r) {
m = (l + r) / 2;
if (inside_shape1(m, 100)) r = m;
else l = m + 1;
}
if (inside_shape1(l + 19, 100) && !inside_shape1(l + 20, 100)) return 1;
return 0;
}
// int main() {
// if (scanf("%d%d%d", &T, &N, &Q) != 3) {
// printf("Input file invalid.\n");
// return 0;
// }
// int mxq = 0;
// for (int i = 0; i < T; i++) {
// if (scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2) != 4) {
// printf("Input file invalid.\n");
// return 0;
// }
// q = 0;
// bool user_ans = am_i_square(N, Q);
// bool act_ans = (Y2 - Y1) == (X2 - X1);
// if (user_ans != act_ans) {
// printf("Wrong Answer.\n");
// cout << X1 << ' ' << Y1 << ' ' << X2 << ' ' << Y2 << '\n';
// // exit(0);
// } else {
// cout << "Correct Answer.\n";
// cout << X1 << ' ' << Y1 << ' ' << X2 << ' ' << Y2 << '\n';
// }
// mxq = max(mxq, q);
// }
// printf("Correct. Used %d out of %d queries.\n", mxq, Q);
// }
