#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define LB(v, x) (int)(lower_bound(ALL(v), x) - (v).begin())
#define UQ(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define IO ios::sync_with_stdio(false), cin.tie(nullptr);
#define chmax(a, b) (a) = (a) < (b) ? (b) : (a)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

/*
                                    .-WVyyyVyVyWkfWHWHVyVyyyyyyyVyyyVyyyyVWMmkyyyyyyyyyVH&.
                                ..WVyVyyVyyWWHHVyyyVyVHHkyVyyyyyyyyyyyyyyyyyWMkVyyyyyyyyVVn,
                                .XVVVyyyyVyVKWyyyyyyyyyyyyWMkyVyVyyyyyyyyyyyyyyVyWHWVyVyyyyyVVS,
                            .HyyyyyyyyyVWHyyVyVyVyVyyyVyyVWNkyyVyVyyyyyyyyyyyyyyyWNkyyyyyyyyyVh,
    :_.                     `.HyyyyVVyyVyVWWyVyyyyyyyyyyyyyyyyyWHWyyyyyyyyyyyyyyyyyyVyWHWyyyyyyyyyVn.
    :::_.                 ` JWyyyVWyyyyyVWyyWyyyyyyyyyyyyyyyyyyyyWWyyyyyyyyyyyyyyyyyyyyyWkyyyyyyyyyyW,`
    ~::::-                .WyyyyyWWyyyyyWyyWyyyyyyyyyyyyyyyyyyyyyyWWyyyyyyyyyyyyyyyyyyyyyyWyyyyyyyyyyVn
    :~~:~:~.     `   `  `.HyyyyyWWyyyyyWyyWWyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyVWyyyyyyyyyyyyyyyyyyyyyyyyyyk.
    :~:~::::_           .WyyyyyWWyyyyyyWyyWyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyWkyyyyyyyyyyyyZyWyyyyyyyyyyyW,
    ~::~:~~::~         ,WyyyyyWHyyyyyyyyyWyyyyyyyyyyyyyyyyyyyyyyWkyyyyyyyyyZyWkyyyZyZyyyyyyyyHyyyyyyyyyyyW,`
    ::~:::~:~`        ,yyyyyyWHyyyyZyyyyWkyyyyyyyZyyZyyZyyZyyZyyyWkyyyZyyyyyyyWkyyyyyZyyyyyyyWHyyyyZyyyyyyW;  `   `   `   `   `
    ~:~~:::~       ` .WyyyyyWHyyyZyyZyyyWyyyyyyyyyyyyyyyyyyyyyyyyyWWyyyyyyyyyyyHWyyyyyWyZyyyyyWkyyyyZyZyyyyy;                    `
    :~::~~`         .HyWHyyyWyyyyyyyyyyyWyyyyZyyZyyZyyZyyZyyZyyyyyyVyyyyyWWyyyyyHyZyyyyHyyyyyyyWkyZyyZyZyy=?W, `  ```     ............
    :~::~`      `  .kyyWyyyWHyyyyyyyyyyyWyyyyyyyyyyyyyyyyyyyyZyZyyyyyZyZyyyyyZyyyWyZyZyWyyZZyyyyHyyZyyyyy%..(X-::::~::~::::::::::~:~::
    ::~~         ` (yyWyyyyWyyyyyyyyWyyWyyyZZyZyZyZyZyZyZyZyyyZyZyZyyyyyyyyWyyZyyWkyyyyWkyyyZyZyWHyyyk..(W-..Oh::~~:~::~:~~~~~:~::~:~:
    ~:~       `   .WyWyyZyWHyyZZyZyWyyyWyyyyyyyZyyyZyyyZyyZyZyyyyZyyZyyZyyyyHyyyZyWyZyyWNyyZyyyY7Wkyyyk-(yyyyyW2:~::~~:~::~::~~:~:~:~~
    ~``_:::::::~::dyyWyyyyWyyyyyyyyWyyyWyyyWyyyyyZyyyZyyyyyZyyZyyyyZyyWyZyZyWHyyyyyHyyyyNZyyyyyl.(NyyyyyyyyyyyyW_~:~::~:~::~:::~:~::::
    `~:~:~:~~:(HyyyyZyWHyZyyZyyWHyZyWyZyVZyZyyyZyyyZyZyyyyZyZyZyyyyWkyyyZyWyZyyyWkyZyWyyZyZyyyyWkyyyyyZyZyZyWr:~:~::~:~:~:~::~:~~:~
    ` `  :~::~::~JWyWyyyyWyyyZyyZyWWyyyWyyyyyZyZyyyZyyyZyZyZyyyyZyyyZyyHyyyyyyZyZyyyWyyZWkyyZyyZyyyNyZyyZyyyZyyWk:::~:~::~::~:~::~::~:
    `  ` ~::~::(WyW$-?4yHZyyyyyyyWyyZyWyyyyZyyyZyyZyZyyyWyyZyyZyC74yZyWkyyZyyyyyZyyykyyWHyyyyZyyZyWkyyWyyZyyyyWW2:~::~:~:~::~:~::~::~
    ` `  `   `~(#yW{..dW#y>.dfjyyWyyyZWWyZWyyyyZyyyZyyyyyyyyyZyyWdyyyyyHyyyZyZyyZyyyWyyyHyyZyyyZyyWNyyWyyyZyZyyWb::~::~:~:~::~:~:~:~:
    ` ` ``   ` `.WWyn((dWHy&-yk+WyHyZyyyWyyWWyyZyyZyyyZyyyyyyZyyyyyZyyZyWyZykyyZyyZyZyHyypyyZyyZyyyyWWyWyyyyZyyyWR:~:~:~::~:~:~::~:~:~
    `   ` ``  `dyKyyyyyWyyyyyyWWyHyyZyyWyyyHyyyyZyyZyyZyyWyyyyZyyZyyZyyWkyyWWyyyyyyyyWyyWyyyZyyyZyZWHyWkyZyyyZyyH<:~:~:~:~::~:~:~::~:
    ` ` `  ` ` HWWyyyyyWyyZyyyWyyHyyyZyWyyyWyyZyyyZyyZyyZWkyyZyyZyyyyyyWHyyWNyyyWyyyyyHyWyyZyyZyyyyyNyyWyyZyyyZyW>::~:~:~:~:~::~:~:~:
    ` ` ` `  ``.HWyZyZyyyyyZyZyXyyHyyZyyWkyyWkyyZyyyyZyyyyyHyyyyZyyZyZyyyHyyybHyyWWyZyyWyWyyyyZyyZyyyHyykyyyZyyWyW[~::~::~::~:~:~::~:~
    `  `` ` ` ,yHyyyyyZyyZyyyyWyyHyyyyyyHyyyHyyyZyyZyyZyyyWWyZyyyZyyyZyyHyyyWWWyykyyZyWkWyyyZyyZyZyyWyyHyyZyyyWHyD:~:~:~:~:~:~::~~::~
    ` `  ` ` `JWHyyykyyZyyyZyyWyyHyWyZyyWyyyWkyyyZyyyZyZyyWHyyZyyyZyyyyyHyZyWWHyyHyyyyyHWWyyyyyyyyZyWkyHyyyZyyyWWS::~:~:~:~:~:~:~:~::
    ` `  `  `  XWyZyykyyyZyyyZyWyyNyWyyZyWHyyyHyZyyZyyyyyZyykyyyZyyyZyZyyHyyZH<WWyWkyZyyWWWWyZyZyyZyyWHyWyyZyyZyXNW:~::~::~::~::~::~~:
    ` `` ` `.WHyyZyWyZyyZyyyyWyyHyWyyyyWdkyyWHyyyyZyZyyyZyWZyyZyZyyyyZyHyyyK:?HyWHkWWyWHWWyyyZyyyZyW#yWWyyyZyyyHWr:~~:~:~:~:~:~:~::~
    `  `  ` ``.yMyyyWHyyZyyZyZyWyyHyyHyyyW>4yyyWkyZyyyyZyyyZWkyZyyyZyyyyWHyZWD~.?WWEdkyyyNHWyyyyZyyyyyNyWHyyZyyyyHHb:::~:~:~:~:~:~:~::
    `` ` `   .XWyZyWHyyyyyyZyyXWykyyWyyZWr(HyyyHkyyZyyZyZyyWHyyyyyyZyZyWHyyW:.-YHyW;?kyyWHWyZyyZyZyZyWyWNyyyyZyy$WW:~::~:~::~::~:~:~~
    `  `` _::dWdyyyyHyZyyZyyyyWWyWyyWKyyW].-kyyyNWyyZyyyyZyyHyZyZyyyZyyWyWWNY=..zyW<;dkyWHWyyyZyyyZyyWWyHyyZyyZybJW<:~~::~:~:~:~::~::
    `  `  .:~(kfJyyZyHyyyyyZyZyykyWWyyNyyyb../kyyyHWyyZyyyyyyWyyZyZyWWkkHHWW\.`.`.WW<;;dkW#WWyyyyZyyyyWWyHkyyZyyyP(W2:~:~::~:~:~:~:~:~
    `` ` ~::(H$JyyyyHyyWWyyyyyWWyWkkW#HkkW-..?kyyWNWyyyZZyZyWWyyyyyyWyWNyyf. ..(?WH++++HWNHkWyyyyZyyyWWkHHyyyZyyP:Xr::~:~~::~::~:~:~:
    ` `.:::(WlJWyZyHyyyWZyyZyWWyWHyW6vWyyr_?7THWWMHKyyyyyyyyHyZyZyyyyWWyWI<~-(igmWqHHNMMHHWHyyZyyZyyWHHWWyZyyyyP:dR:~::~:~::~:~::~::
    `  ` ~:~:JW<(kyyyWyyyVyZyyyWVWyHyWv_jyyk_.../kyyb?kyyZyyZyHyyZyyZyW$wWf-+dqHNMMMMM=jN(NNHyyyyZyyZyWXNWWyyyZyyP:JW:~:~::~~:~::~:~:~
    ` `  ~:~JS:(HyyyWyyZWyyyyyyHWyWyW:..jyVh..--(HkWs?WyyZyyyWyyyyyyyX!Jy<WB=NMMMMNVTWY@.WMyyyyyyyyyyyKHWWHyyyyWD:(W<:~:~::~::~~:~:~:
    ` `  `  ~dk:(HyZyWWyyWWyZyZyWWyWWk..`.?Wk-.....WXWc<4WyyZyWkyZyWWW%.JP?H` ,MH6OH6=vz% dNyyWyZyZyyyy]WWHHyZyyWD:(W2::~:~::~:~::~::~
    ` ` `   X0:~HyyyHWWyyHyyZyyyHHWkkumWqqHkHHHNHHNMkH-<?WyyyyHyyyWyf..d!.D   ?fz<:::j}`.HHyyyyyZyZyyW#dWNWyyZyW$~:Wr:~:~:~~:~::~:~:~
    ` ` `` Wt~:dyyyHWHyyWyyyyyyWHXHHHY=<?MMNMMMMM<(MNN._?4yyyHyyyWK_`.<..}.  `."w++7~ -<NWyyWyyyyyZyWKXHHWHyyyyC::dP:~::~::~:~~:~:~:
    ` `  `   Hr  JyyZWXHyyWkyZyyyyHkWWW2`` ?M#HSvW#zZH}4j. <?WyHyyZW{..`.`.`... .. ~_~..._qXyykyZyyZyyWKuHHkHyyZy>~:Jb~:~:~:~::~::~::~
    ` ` ` ` H)``,WyyWXHWyyHyyZyZyWNWR.?n   (HvI?<<:<z~.~(_.-<?Wyyf4}.`..`..``......~~-~_(WdyyHyyZyyyyW#zHKHWyyyy>:~(H::~~:~:~::~::~::
    `  ` `  k\ .(HyyWXHHyZHyyyZyyyWkD...<.  `?4++<jJ^ ......`-dWf`.4..`..`..`.``...~~~._(UJyyHyyyZyZyy#zWKHWHyyWI::(W:~:::~:~~:~~:~~:
    ` ` `` ` W[_:(HyyWXHHyyWkyyyyZyWHW.`....( ......_!.``.`.`..J^```.!`.``.`..`..........(WJyyWyZyyyyZyHzWHdyHyyW2:~(W<:~:~:::~::~::~:
    ` `  ` .HR:::WyyWkNWyyyHyZyyyyWWHZ+.``...........`..`.`..`. ```..`...`.`..`.`..`.`..(WJyyWyyZyyyyyHzXKXkWkyWr:~(Wr:~:~~:~:~::~:(?
    `  ` ` `.KR:~:dyyWSbWyHyWyyZyyyyWWRQn.....(~_<~...`...`..`...--..`.`.`..`..`..``.`.`.JW(yWWyyyZyZWWHzXKuHWHyWr::(Wr::~::~:~:~::(<`
    _..  ` ((HW:~:(kyWKWWKHyUHyyZyZyWWWuzX-.....__.....``..`.`.` _^`..`..`..`.`.`..`..`..Jk(yWWZyyyZyWWHzXHzWyWyyP~::WP~::~::~::~:(=..
    ::~::_::(WW<:~(HyyRdfNWyyNyyyZyyyWyRzuH,.......`.`..`.`.`.`.`.`.`..`.`.`...`..`.`.`..dRJyWyyZyyyyWyHuX#uXyWkyD:~:Wb:~:~~::~:(J!..!
    ~:~~::~::ZW<:::dyyHXHMWWyWkyZyyZyyNWkzXX,.`.`.`..`...`...`...`..`.`..`..``..`..`..`..dMWyWyyyZyZyWy#uu#uuyyHyD::~dK::~::~::J^. __(
    :~::~:~::XW2~::JWyWuHSHHyWNyyyyyyyWkHudkXo.`.`..`.``..`.`.`.`..`..`.`.`..`.`.`...`..VWWXyWyyyyZyyWy#zuHzXkyWyS:~:XS:~:::~(<.-(!.(+
    :~:~:~:~:wWr:~~(HyWXWWdNyWWkyZyZyyWMWKuKzuX,..`..`..`..`.`.`.`.`.`...`.`..`..`.`.J9=dWHWyWyZyyyyyHyKuzHuuHyWkW<::WS::~:(<_.-!` (<z
    ~:~:::~::dyb::::qyWRdW2NyyHNyyZyyyyWNWuXuuuHU&....`..`..`...`...(<77!.`..`..` .d3===dyWWyWyyZyZyWHXRuuHzuHyyHW>::kk_:(C..-!...;+6v
    :~:~:~::~dyK~:~:?Wy#XHRJWyWdWyyyZyyWHkWXuuuXuuuUnJ,.`.`..`.`..`..`.``..`..`.J9======dWdXyWyyyZyyWWWSzuHuuHyyWW$~(HW>(! -!`..(j9jC:
    ::~:~:~::JyW:~:~(HyHuHW(HyWXNyyyZyyyHWWXSuuXXuuuuuXWUGJ...`.`.`.`...`.`...X3========dWdHyWyyZyyyHyWkuuWuzqyZyHR:(WW^.(^`..(jZ>;Z::
    ~:~::~:~:(yW::::~qyWkWW2vyWKWWyyyZyyWRWWWuuuWuuuuuXpuuuuXdBk&(...`.`. .J6===========XWzNyVZyyyyW#yWkuuWuuWyyyWH_dY-/~....<JI;;jt:~
    :~:~::~:~(WWr:~::JHWKXWb(Wy#uNyyyyZyWWXWWuuuXkuuuuuHkuuX@::?O==zvTUU96==========?===yyzHyfyyZyyWyyfWuuWuuWyyWyHsi/_...`.jZJ;;+P::(
    :~:~::~:::Wyb~:~:~HyNXHW2WyWuXWyZyyyyHXXWKuuuWuuuuuHXT8X:::u?s============?==?=====zkRdNyWyyyyyHyyKXuuWuuXyyWkKv~..`. (+$+C;<d<(Y!
    ~:~:~:~::~XyW:::(JdUTYYYYTYTYUNyyZyZyWRuHKuuuXRuuuXY;:jt::;?NNz================?===zyW5XykyyyyWHyyHXuuXuukQH9^...`. (JSzvY;<d>J3.`
    ::~::~:~::dyW:~(d1::::::::::;:dkyyyyyWWuXHkXkXVYUE<:::Z:::::?M#=======?==?==?======dyD:XyHyZyyKyyWIZXkXKX#^..``...(J3;;;;;;d-J>!..
    ~::~::~:~:(ky$(D?;I;::::::::::<NyyZyyyH9<dn:;:<J3:;;:+K;::::::?S==?==?============zXWI:XWHyyyWHZyW<:;<yHY..`..`.`(>;:;:;;:+t.$;~``
    :~~:~::~::(HySd_<:?I::;::::::::JkyyZyyWR;<H<:jZ+++1<<<H;::;::;::?z=======?=====uZ3:dWI;WXWZyyHyyyK::;+W=.`.``....J;:;;:;;;J` >;~..
    :~::~:~:~::XyW'` <:j<::::;:::;:<HyyyZyyk<:dkj9>:;::::<H;::;:;::;<jHmx======udT3::::JWb:HyyyyWWyyyb<:;J~.`.`..`..j3;:;:;:<JiJ3Z+-.`
    ~::~:~::~:~JWF ```_:X1z&++<;::::JkyyyyyVn+JW$;::::::;+H<::<_~~~(dHHMCR==dMHmHe:_```JWm<HyyZWHyZyW3O+>.`.`..`...J6;:;;;:jdJ;;;<>3..
    :~~::~:~(vYTC1OI-.`-?<::::<?71++;WyZyyyWk:jyP:;<:;;::+M>;!````.XuZK?SX1zJWHmmHs_`.,=`` ~7TWWyyyyW<jC.`.`.`.``..@;;;:;++TC;;:;<-.`.
    ::~::::(izrOz+?>?zT+Jj::::::;::::?HyZyZyW2jyb:;:`_<::<MR~````.XuXWmmmgggHHWHmmge?!   J<<_``.7WyWDj'...`..`...`.P;:<+7;;;;:;:;<_`.t
    ~:~:(Y6YTUU99XAz>??>?Us<;;x;:;::::dWyyyyWSdyR:<_```_:;HH.```.XZXf?7THHmH9Y"TWM=     `X:<``````_T<_.``.`.`.`....I<JC;;;:;:;;;:~.(^`
    :~(J(?>>?>?>>>>1T9e+>???G+j+::::::<HyyyyWWWyW:+_```` ~jHr``.HZuK;:<+vCG.` .dHH       d+<.``````,.`..`..`.`.``..<<;;:;:;;:;:<_._```
    :(d->??>??>?>??>>?>>>+>>?1Gy:::;::;?yyZyWHHyW<z_`````` SX..KuuV<::v~~((mJHkkkH       (J+/~.`` /.`.`..`.`..`..`J;;::;:;;:;;<..:````
    z1uaaggwZCuu&+>??>>??>vGxrrrX+::::::4yyyyHyyWII````````(XGKuXW#7=!`   (kkkkkkH       .;:<T,<.>.`.`.``.`.`.`...P;;:;;:;:;;<_(^`````
    uuX0uXQXVVT9WAdVV&x?>>?>?4yrrvW;:::;(WyZyWyyWrS````````.HuuX#H:       ,kkkkkkH_       <::_ W>.`..`..`..`.`..`J<;:;;:;;:;;-J!``````
    XX9C11>??>>?>?4uXWHAwOx?1zdHyrrG<;:::vyyyWHyyDw``....,..dkXK<+<       ,qkkkkkH_       >;+v7'.`.`..`..`.`..`.-C;:;:;;:;;:jC````````
    >?>>+1ug&g&+>??vXuuuuXUAXyrrdHwwb::::<WkyyHQKYYT1???>?>??>?13?[       ,qkkkkkH}       ?!..``.`.``.``.`..`...<;:;;;:;;;j/~`````````
    UQgMHHHH@HHHMHe+?WuuuuuuuuOZQwWHdc:;:<jHB6<>?>?>?>>>?>>>>>>?>>S       ,qkkkkkH[       ...`..`...`..`..`.`.v<:;;:;;;<+7````````````
    HMMMHBYMMMMkkkkHUAWkuuuuuXkYY1??+OTmVSryT1>>>?>>?>?>>?>?>?>>??d    `  .qkkkkqk]       .;.`.`.``..`..`.`.J3;:;:;<<(v=:`````````````
    1>>?>>?>v&7TMHHStrZHmuXk9z?>>>?>uUwwwV3>>?>?>>?>>?>?>>?>?>?>>>J-      .HkkkkkkE        L..`..`.``.`. .JC;;;<!_(JY:~/``````````..``
    >zzzzzz+>?vzrrWHmAgkMB3?>>>>??uUrwZC?>?>?>?>?>?>?>>?>?>>>?>?>?d]       HkkkkkqH.       j_.`.`...`.`.?<<<~_ .JW<::~.!````````./` ``
    >??1z7TWAAyOWgYYCjd5?>>?>?>?+dXwV1?>>?>>>?>>?>>?>>?>>?>?>>?>?>dD       XqkkkkkH[       ,c_..`.`..`.`.....JD::X::: /```````./_.,zOT
    ?>>>?>??udY6??+ud3?>>?>>?>?>7C???>>?>>?>>?>?>?>>?>>?>>?>?>>?>?JH. `    ,qkkkkkkb        P:<-...---.-!!````z+;K::<._`````.-Y1?>?>?>
    zzzuz&v6?1+zrQY1?>>?>>?>>?>>?>>>>>?>?>?>?>>>?>?>?>?>?>>?>?>>>?j#]      .HkkkkkqH.  `    u;j+gV"=_:>< `````.b;@;:<_```..1?>>>>>>?>>
    >??xC>>jrrrQ91??>>>?>?>?>>?>>?>?>>?>>?>>>?>?>>>?>>?>>?>>?>?>?>jKS    `  Hkkkkkkq{`````  ,$<::;_``{+;_``````J+b::<``.J<??>?>?>>>>>?
    1z1>?jrrrAY1?>>>??>>?>>?>?>>?>?>?>>?>>?>?>?>?>?>>?>?>?>?>>?>>??Nd,`  ```dkkkkkkkb````````S:::::.`~(:<``````.PX;:<.1?>>?>?>?>?????1
    ?uy0rrrw91>?>?>>>?>>?>?>>?>>?>>?>>?>?>>>?>>>?>>?>>?>>>?>>?>?>?>drn``````(qkkqkkkH-```````(c;:::<. d::.``````S?2+1>?>?>?+&ggw0VC111
    VwrrrwV1?>>>?>??>>?>>?>>?>?>>?>>?>>?>?>>?>>?>?>?>?>>?>>?>>?>>>?JkZ;`````,Hkkkkkkkh,```````.1+;:::;d::_``````(+C+&uQdY961>?>>?>>>>>
    wwwwZ<>>>?>?>1+&&&&x&+??>>?>>?>?>>?>>?>>?>?>>?>>?>>?>?>?>?>>?>>>OrG.`````4qkkkkkkkqn.``````` !+::2P:::.```` .kkVY1>?>>?>>>>?>>?>?>
    11??>>>?>>?>?>1zOOrOOvz1?>>>?>>??++??>??>?>?>>?>>?>>?>>>?>>?>????zzL``````.4kqkkkkkkHa,````````?jw3:;;<````./6?>>?>>>>>?>>?>>>>?>>
*/

/// @file xor128.hpp
/// @brief 疑似乱数生成

/// @brief xor shift による疑似乱数を生成する
uint64_t Xor128() {
    static bool flag = false;
    static uint64_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    if (!flag) {
        w = time(0);
        flag = true;
    }
    uint64_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

/// @brief 0 以上 n 未満の整数から乱数を生成する
uint64_t Xor128(uint64_t n) { return Xor128() % n; }

/// @brief [l, r) の範囲の整数から乱数を生成する
uint64_t Xor128(uint64_t l, uint64_t r) { return Xor128(r - l) + l; }  // [l, r)

/// @brief 0 以上 1 未満の浮動小数点数から乱数を生成する
double Xor128Prob() { return (double)Xor128() / (1LL << 32); }

/// @file bins.hpp
/// @brief 二分探索
/// @param ok `judge` が true になる値
/// @param ng `judge` が false になる値
/// @param judge 判定関数
/// @return `judge(x)` が true になる境界値
template <typename T, typename Judge>
T BinarySearch(T ok, T ng, Judge judge) {
    while (abs(ok - ng) > 1) {
        T mid = (ok + ng) / 2;
        (judge(mid) ? ok : ng) = mid;
    }
    return ok;
}

/// @brief 回数指定二分探索
/// @param ok `judge` が true になる値
/// @param ng `judge` が false になる値
/// @param judge 判定関数
/// @param iter 探索回数
/// @return `judge(x)` が true になる境界値
template <typename T, typename Judge>
T BinarySearchIteration(T ok, T ng, Judge judge, int iter = 100) {
    while (iter--) {
        T mid = (ok + ng) / 2;
        (judge(mid) ? ok : ng) = mid;
    }
    return ok;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> X(2 * N), Y(2 * N);
    for (int i = 0; i < 2 * N; i++) cin >> X[i] >> Y[i];

    const int mx = 1e5;

    while (true) {
        ll A = Xor128(mx), B = Xor128(mx);
        auto count = [&](ll c) {
            ll ans = 0;
            for (int i = 0; i < 2 * N; i++) {
                ll val = A * X[i] + B * Y[i] + c;
                if (val > 0) ans++;
            }
            return ans;
        };
        auto f = [&](ll c) { return count(c) >= N; };
        ll res = BinarySearch(INFL, -INFL, f);

        bool ok = true;
        for (int i = 0; i < 2 * N; i++) {
            ll val = A * X[i] + B * Y[i] + res;
            if (val == 0) ok = false;
        }
        if (count(res) != N) ok = false;
        if (res < -mx || res > mx) ok = false;

        if (ok) {
            cout << A << " " << B << " " << res << endl;
            return 0;
        }
    }
}