#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;
#define ll long long
#define ld long double
#define pii pair <int, int>
#define pld pair <ld, ld>
#define fi first
#define se second
#define mp make_pair
const ll LIM = 1e4;
const ld EPS = 1e-9, inf = 1e18;
struct line{
ld a, b, c;
};
ll MAX_DEP = 32, x0 = 2*LIM+10;
vector <int> va, vb;
vector <ld> pos, neg;
set <pii> S;
void get(ld y){
int b = int(round(y+x0*LIM+LIM))%x0-LIM, a = int(round(y-b)/(ld)x0);
if (!S.count(mp(a, b))){
va.push_back(a);
vb.push_back(b);
S.insert(mp(a, b));
if (x0 > 0) pos.push_back(y); else neg.push_back(y);
}
}
void dnc(int dep, ld l, ld r, ld fl, ld fr){
if (dep == MAX_DEP){
get((l+r)/2.0);
return;
}
ld mid = (l+r)/2.0;
if (fl == +inf) fl = query(x0, l);
if (fr == +inf) fr = query(x0, r);
ld fmid = query(x0, mid);
if (abs(2.0*fmid - (fl+fr)) <= EPS) return;
dnc(dep+1, l, mid, fl, fmid);
dnc(dep+1, mid, r, fmid, fr);
}
line calc(pld A, pld B){
line d;
d.a = A.se-B.se, d.b = B.fi-A.fi, d.c = -A.fi*(A.se-B.se)-A.se*(B.fi-A.fi);
return d;
}
void solve(int subtask_id, int N){
if (N == 3) MAX_DEP = 34;
dnc(0, -2*LIM*(x0+1), 2*LIM*(x0+1), +inf, +inf);
if (N == 3){
x0 = -x0;
dnc(0, -2*LIM*(-x0+1), 2*LIM*(-x0+1), +inf, +inf);
va.clear(); vb.clear();
assert((int)pos.size() >= N);
assert((int)neg.size() >= N);
sort(pos.begin(), pos.end(), greater <ld>());
sort(neg.begin(), neg.end());
for (int i = 0; i < N; i++){
line d = calc(mp(-x0, pos[i]), mp(x0, neg[i]));
int a = round(-d.a/d.b), b = round(-d.c/d.b);
va.push_back(a);
vb.push_back(b);
}
}
the_lines_are(va, vb);
}
