#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ldouble = long double;
const ldouble EPS = 1e-5;
const lint INF = 3e9;
const lint MAXV = 1e4;
const lint BASE = 5e4;
class Line {
public:
ldouble a, b;
Line(ldouble a, ldouble b) : a(a), b(b) {}
Line(ldouble x1, ldouble y1, ldouble x2, ldouble y2) {
a = (y1 - y2) / (x1 - x2);
b = y1 - a * x1;
}
};
void solve(int subtask_id, int N) {
map<pair<lint, lint>, ldouble> memo;
const auto Query = [&](lint x, lint y) {
if (memo.count({x, y})) return memo[{x, y}];
return memo[{x, y}] = query(x, y);
};
const auto IntersectionX = [&](Line l1, Line l2) {
// a1 * x + b1 = a2 * x + b2
// x = (b2 - b1) / (a1 - a2)
return (l2.b - l1.b) / (l1.a - l2.a);
};
set<lint> changing_points;
const auto Solve = [&](const auto &self, Line lft, Line rgt, int depth) -> void {
// cout << lft.a << ' ' << lft.b << ' ' << rgt.a << ' ' << rgt.b << " hi\n";
// if (depth > 10 * N) return;
if (abs(lft.a - rgt.a) < EPS) return;
ldouble interX_ = IntersectionX(lft, rgt);
lint interX = round(interX_);
Line midUp(interX, Query(BASE, interX), interX + 1, Query(BASE, interX + 1));
Line midDn(interX, Query(BASE, interX), interX - 1, Query(BASE, interX - 1));
if (abs(midUp.a - midDn.a) > EPS) {
// cout << interX << ' ' << interX_ << " inter" << endl;
// assert(abs(interX - interX_) < EPS);
changing_points.emplace(interX);
}
self(self, lft, midDn, depth + 1);
self(self, midUp, rgt, depth + 1);
};
Solve(Solve,
Line(-INF, Query(BASE, -INF), -INF + BASE, Query(BASE, -INF + BASE)),
Line(+INF, Query(BASE, +INF), +INF - BASE, Query(BASE, +INF - BASE)), 0);
// cout << "HUH?" << endl;
// for (auto y : changing_points) cout << y << ' '; cout << endl;
vector<int> answerA, answerB;
for (auto y : changing_points) {
// y = ax + b
// x = BASE
// b = y % BASE
lint b = y % BASE;
while (b < -MAXV) b += BASE;
while (b > +MAXV) b -= BASE;
assert((y - b) % BASE == 0);
lint a = (y - b) / BASE;
assert(-MAXV <= a && a <= +MAXV);
assert(-MAXV <= b && b <= +MAXV);
answerA.emplace_back(int(a));
answerB.emplace_back(int(b));
// cout << a << ' ' << b << " line" << endl;
}
return the_lines_are(answerA, answerB);
}
/*
1
17 10000 10000
1 0
2 1
3 2
3 3
4 4
4 3
4 2
4 1
0 1
0 0
0 -1
0 -2
4 -1
4 -2
-4 -4
-10000 -10000
10000 10000
1
2 1000 1000
-10000 -10000
10000 10000
*/
