QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116784#5155. Faster Than Lightbatrr#WA 194ms32068kbC++235.1kb2023-06-30 04:22:312023-06-30 04:22:32

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 04:22:32]
  • 评测
  • 测评结果:WA
  • 用时:194ms
  • 内存:32068kb
  • [2023-06-30 04:22:31]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}
int n;
const int maxN = 2e5 + 10;
int x[maxN][2];
int y[maxN][2];
bool cmp(tuple<ll,ll,int>& a, tuple<ll,ll,int>& b) {
    ll X1 = get<0>(a);
    ll Y1 = get<1>(a);
    ll X2 = get<0>(b);
    ll Y2 = get<1>(b);
    assert(X1 > 0 && Y1 > 0 && X2 > 0 && Y2 > 0);
    return (X1 * Y2 < X2 * Y1);
}
bool check() {
    vector<int> lower(n), upper(n);
    iota(lower.begin(), lower.end(), 1);
    iota(upper.begin(), upper.end(), 1);
    sort(lower.begin(), lower.end(), [&](int i, int j) {
        return make_pair(x[i][0], y[i][0]) < make_pair(x[j][0], y[j][0]);
    });

    sort(upper.begin(), upper.end(), [&](int i, int j) {
        return make_pair(x[i][1], y[i][1]) < make_pair(x[j][1], y[j][1]);
    });

    vector<pair<ll,ll>> pt_l, pt_u;
    for (int id : lower) {
        ll X = x[id][0];
        ll Y = y[id][0];
        while (!pt_l.empty() && pt_l.back().second <= Y) {
            pt_l.pop_back();
        }
        while (pt_l.size() >= 2) {
            auto t1 = pt_l[pt_l.size() - 2];
            auto t2 = pt_l.back();
            if ((t2.second - Y) * (t2.first - t1.first) > (X - t2.first) * (t1.second - t2.second)) {
                break;
            }
            else {
                pt_l.pop_back();
            }
        }
        pt_l.emplace_back(X, Y);
    }

    for (int id : upper) {
        ll X = x[id][1];
        ll Y = y[id][1];
        if (!pt_u.empty() && pt_u.back().second <= Y) {
            continue;
        }
        while (pt_u.size() >= 2) {
            auto t1 = pt_u[pt_u.size() - 2];
            auto t2 = pt_u.back();
            if ((t2.second - Y) * (t2.first - t1.first) < (X - t2.first) * (t1.second - t2.second)) {
                break;
            }
            else {
                pt_u.pop_back();
            }
        }
        pt_u.emplace_back(X, Y);
    }
//    for (auto& it : pt_l) {
//        cout << it.first << " " << it.second << endl;
//    }
    vector<tuple<ll, ll, int>> events;
    for (int i = 0; i + 1 < pt_l.size(); i++) {
        events.emplace_back(pt_l[i].second - pt_l[i + 1].second, pt_l[i + 1].first - pt_l[i].first, i);
    }
    for (int i = 0; i + 1 < events.size(); i++) {
        assert(cmp(events[i], events[i + 1]));
    }
    for (int i = (int)pt_u.size() - 2; i >= 0; i--) {
        events.emplace_back(pt_u[i].second - pt_u[i + 1].second, pt_u[i + 1].first - pt_u[i].first, ~i);
    }
    sort(events.begin(), events.end(), cmp);
    int ID_U = pt_u.size() - 1;
    int ID_L = 0;
    ll PRV_A = 0;
    ll PRV_B = 1;
    for (auto& it : events) {
        ll A = get<0>(it);
        ll B = get<1>(it);
        if (PRV_A * pt_l[ID_L].first + PRV_B * pt_l[ID_L].second <= PRV_A * pt_u[ID_U].first + PRV_B * pt_u[ID_U].second) {
            return true;
        }
        if (A * pt_l[ID_L].first + B * pt_l[ID_L].second <= A * pt_u[ID_U].first + B * pt_u[ID_U].second) {
            return true;
        }
        if (get<2>(it) >= 0) {
            ID_L++;
        }
        else {
            ID_U--;
        }
        PRV_A = A;
        PRV_B = B;
    }
    assert(ID_L == pt_l.size() - 1);
    assert(ID_U == 0);
    PRV_A = 1;
    PRV_B = 0;
    if (PRV_A * pt_l[ID_L].first + PRV_B * pt_l[ID_L].second <= PRV_A * pt_u[ID_U].first + PRV_B * pt_u[ID_U].second) {
        return true;
    }
    return false;


}
mt19937 rnd(228);
void solve() {
    cin >> n;
//    n = rnd() % 10 + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> x[i][j] >> y[i][j];
        }
//        ll A = rnd() % 10 + 1;
//        ll B = A + rnd() % 10 + 1;
//        x[i][0] = A;
//        x[i][1] = B;
//        A = rnd() % 10 + 1;
//        B = A + rnd() % 10 + 1;
//        y[i][0] = A;
//        y[i][1] = B;
    }
    for (int iter = 0; iter < 2; iter++) {
        if (check()) {
            cout << "possible\n";
            return ;
        }

        for (int i = 1; i <= n; i++) {
            swap(y[i][0], y[i][1]);
            y[i][0] *= -1;
            y[i][1] *= -1;
        }
    }
    cout << "impossible\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

4
1 1 2 2
1 3 2 4
3 1 4 2
3 3 4 4

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5460kb

input:

3
1 1 2 2
1 3 2 4
3 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5476kb

input:

5
0 0 1 999999999
0 999999999 999999999 1000000000
1 0 999999998 1
999999998 0 999999999 999999999
2 999999998 3 999999999

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5568kb

input:

4
0 1 1 1000000000
1 0 999999999 1
999999999 0 1000000000 999999999
2 999999999 999999999 1000000000

output:

possible

result:

ok single line: 'possible'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5532kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 999999999 1000000000

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5500kb

input:

3
0 0 1 1000000000
2 0 999999999 1
2 999999999 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #8:

score: 0
Accepted
time: 112ms
memory: 8148kb

input:

199999
433914929 216935871 433914930 216935872
621822279 310889546 621822280 310889547
395914333 197935573 395914334 197935574
582775641 291366227 582775642 291366228
658726133 329341473 658726134 329341474
71689261 35823037 71689262 35823038
453260967 226608890 453260968 226608891
249802825 1248798...

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 139ms
memory: 8112kb

input:

199999
783545903 638444708 783545904 638444709
129510863 105527268 129510864 105527269
844145756 687822366 844145757 687822367
69111161 56312696 69111162 56312697
820438487 668505332 820438488 668505333
541037357 440845152 541037358 440845153
201057677 163824672 201057678 163824673
132372296 1078588...

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 132ms
memory: 8172kb

input:

199999
90035476 60020102 90035477 60020103
482291029 321523804 482291030 321523805
943496815 628994328 943496816 628994329
278866936 185907742 278866937 185907743
310938589 207288844 310938590 207288845
203677765 135781628 203677766 135781629
368744134 245825874 368744135 245825875
559390024 3729231...

output:

impossible

result:

ok single line: 'impossible'

Test #11:

score: 0
Accepted
time: 131ms
memory: 8196kb

input:

199999
207687261 415417709 207687262 415417710
150460947 300965081 150460948 300965082
9349830 18742847 9349831 18742848
87879837 175802861 87879838 175802862
354035800 708114787 354035801 708114788
305159254 610361695 305159255 610361696
248609913 497263013 248609914 497263014
499646110 999335407 4...

output:

impossible

result:

ok single line: 'impossible'

Test #12:

score: 0
Accepted
time: 148ms
memory: 8132kb

input:

199999
79738802 97861382 79738803 97861383
614827422 754561052 614827423 754561053
517213290 634761890 517213291 634761891
788424494 967612004 788424495 967612005
613541698 752983118 613541699 752983119
698980304 857839589 698980305 857839590
487475098 598265018 487475099 598265019
733711836 9004646...

output:

impossible

result:

ok single line: 'impossible'

Test #13:

score: 0
Accepted
time: 134ms
memory: 8140kb

input:

199999
161399962 242105266 161399963 242105267
385751852 578633101 385751853 578633102
222705450 334063498 222705451 334063499
503730932 755601721 503730933 755601722
454037530 681061618 454037531 681061619
334605270 501913228 334605271 501913229
478675624 718018759 478675625 718018760
137316204 205...

output:

impossible

result:

ok single line: 'impossible'

Test #14:

score: 0
Accepted
time: 146ms
memory: 8200kb

input:

199999
222639792 110935680 222639793 110935683
931931336 465581452 931931337 465581455
35474718 17353143 35474719 17353146
206777070 103004319 206777071 103004322
914064786 456648177 914064787 456648180
301496196 150363882 301496197 150363885
515345552 257288560 515345553 257288563
500949336 2500904...

output:

impossible

result:

ok single line: 'impossible'

Test #15:

score: 0
Accepted
time: 138ms
memory: 8172kb

input:

199999
14166026 11542586 14166027 11542589
212205815 172908340 212205816 172908343
997392464 812690054 997392465 812690057
766610585 624645560 766610586 624645563
843092432 686964102 843092433 686964105
362333537 295234632 362333538 295234635
724513967 590344612 724513968 590344615
903878693 7364936...

output:

impossible

result:

ok single line: 'impossible'

Test #16:

score: 0
Accepted
time: 126ms
memory: 8100kb

input:

199999
259728590 173148768 259728591 173148771
221053226 147365192 221053227 147365195
899826680 599880828 899826681 599880831
847582532 565051396 847582533 565051399
258078974 172049024 258078975 172049027
369519293 246342570 369519294 246342573
214263539 142838734 214263540 142838737
737461550 491...

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 129ms
memory: 8116kb

input:

199999
310634507 622037446 310634510 622037447
14947597 30663626 14947600 30663627
99728538 200225508 99728541 200225509
184650291 370069014 184650294 370069015
166422010 333612452 166422013 333612453
302228792 605226016 302228795 605226017
386996090 774760612 386996093 774760613
326681088 654130608...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 139ms
memory: 8112kb

input:

199999
799006978 980599598 799006981 980599599
101833006 124976996 101833009 124976997
491420512 603107117 491420515 603107118
529582438 649942208 529582441 649942209
453375406 556415396 453375409 556415397
591719612 726201467 591719615 726201468
775042202 951188282 775042205 951188283
218921560 268...

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 121ms
memory: 8108kb

input:

199999
354595980 531899408 354595983 531899409
57294868 85947740 57294871 85947741
297914740 446877548 297914743 446877549
306592118 459893615 306592121 459893616
648745732 973124036 648745735 973124037
267426974 401145899 267426977 401145900
363073104 544615094 363073107 544615095
512209740 7683200...

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 78ms
memory: 7752kb

input:

200000
183486 13299 183487 13300
102571 78692 102572 78693
170699 23633 170700 23634
62500 111076 62501 111077
175314 19903 175315 19904
147075 42725 147076 42726
131050 55675 131051 55676
165234 28050 165235 28051
98541 81949 98542 81950
186747 10663 186748 10664
128558 57690 128559 57691
75090 100...

output:

possible

result:

ok single line: 'possible'

Test #21:

score: 0
Accepted
time: 111ms
memory: 8172kb

input:

200000
84832 76958 84833 76959
10067 59201 10068 59202
59229 70877 59230 70878
106141 82019 106142 82020
89100 77971 89101 77972
107123 82252 107124 82253
29040 63708 29041 63709
174481 98249 174482 98250
149793 92386 149794 92387
31435 64276 31436 64277
152941 93133 152942 93134
112041 83420 112042...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 127ms
memory: 8112kb

input:

200000
44135 36736 44136 36737
89083 45138 89084 45139
71165 41788 71166 41789
68851 41356 68852 41357
94251 46104 94252 46105
24076 32986 24077 32987
75127 42529 75128 42530
21105 32431 21106 32432
97018 46621 97019 46622
100975 47361 100976 47362
122230 51334 122231 51335
131723 53109 131724 53110...

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 87ms
memory: 7732kb

input:

200000
12123595 65272337 12123596 65272338
47819779 50226819 47819780 50226820
34587193 55804197 34587194 55804198
31014123 57310204 31014124 57310205
55526647 46978466 55526648 46978467
63405174 43657760 63405175 43657761
92658071 31328012 92658072 31328013
69459554 41105911 69459555 41105912
13473...

output:

possible

result:

ok single line: 'possible'

Test #24:

score: 0
Accepted
time: 136ms
memory: 8180kb

input:

200000
25587435 13688997 25587436 13688998
67822058 7043790 67822059 7043791
50756536 9728884 50756537 9728885
50605565 9752638 50605566 9752639
948172 17565746 948173 17565747
99155430 2113788 99155431 2113789
2457571 17328257 2457572 17328258
55236107 9024067 55236108 9024068
6859008 16635734 6859...

output:

impossible

result:

ok single line: 'impossible'

Test #25:

score: 0
Accepted
time: 159ms
memory: 8176kb

input:

200000
308 141674 309 141675
30411 124142 30412 124143
26864 126208 26865 126209
153801 52285 153802 52286
90521 89137 90522 89138
159641 48883 159642 48884
188626 32004 188627 32005
22527 128734 22528 128735
132574 64646 132575 64647
45592 115301 45593 115302
47431 114231 47432 114232
173312 40922 ...

output:

impossible

result:

ok single line: 'impossible'

Test #26:

score: 0
Accepted
time: 85ms
memory: 7804kb

input:

200000
56156 97395 56157 97396
75189 41275 75190 41276
87911 3766 87912 3767
50380 114426 50381 114427
34447 161405 34448 161406
45750 128079 45751 128080
36895 154185 36896 154186
82967 18345 82968 18346
83297 17369 83298 17370
50841 113065 50842 113066
61613 81307 61614 81308
81748 21939 81749 219...

output:

possible

result:

ok single line: 'possible'

Test #27:

score: 0
Accepted
time: 138ms
memory: 8120kb

input:

200000
110235 130882 110236 130883
132712 187597 132713 187598
94392 90907 94393 90908
81558 58524 81559 58525
59674 3306 59675 3307
61359 7558 61360 7559
133389 189304 133390 189305
120581 156987 120582 156988
129825 180310 129826 180311
84642 66306 84643 66307
112281 136044 112282 136045
67009 218...

output:

impossible

result:

ok single line: 'impossible'

Test #28:

score: 0
Accepted
time: 131ms
memory: 7804kb

input:

200000
140230 53637 140231 53638
142915 28531 142916 28532
137051 83364 137052 83365
141400 42696 141401 42697
144324 15354 144325 15355
128421 164046 128422 164047
126285 184020 126286 184021
141765 39283 141766 39284
136961 84199 136962 84200
142007 37021 142008 37022
137086 83034 137087 83035
128...

output:

impossible

result:

ok single line: 'impossible'

Test #29:

score: 0
Accepted
time: 143ms
memory: 8156kb

input:

200000
55205759 10901341 55205760 10901342
60674231 25887846 60674232 25887847
78521510 74798826 78521511 74798827
58210191 19135073 58210192 19135074
53049049 4990815 53049050 4990816
78791227 75537993 78791228 75537994
80659297 80657493 80659298 80657494
82535491 85799256 82535492 85799257
7105544...

output:

impossible

result:

ok single line: 'impossible'

Test #30:

score: 0
Accepted
time: 120ms
memory: 8184kb

input:

200000
69507066 51970715 69507067 51970716
86474964 98135774 86474965 98135775
67094841 45407702 67094842 45407703
75120388 67243045 75120389 67243046
80620577 82207570 80620578 82207571
58416570 21796476 58416571 21796477
77617864 74038000 77617865 74038001
61095812 29085968 61095813 29085969
70495...

output:

impossible

result:

ok single line: 'impossible'

Test #31:

score: 0
Accepted
time: 122ms
memory: 7804kb

input:

200000
115996 107127 115997 107128
130561 66339 130562 66340
145545 24378 145546 24379
123364 86492 123365 86493
136600 49428 136601 49429
94939 166093 94940 166094
95551 164379 95552 164380
109878 124258 109879 124259
149367 13674 149368 13675
142089 34056 142090 34057
145354 24913 145355 24914
127...

output:

impossible

result:

ok single line: 'impossible'

Test #32:

score: 0
Accepted
time: 143ms
memory: 31832kb

input:

200000
540875748 213117203 540875749 285258332
573214234 160023435 573214235 273675128
280235458 508389718 280235459 511266397
554777064 193046152 554777065 277526751
83500104 657941433 83500105 755185390
318772782 471268854 318772783 471312613
442363064 337243144 442363065 358157759
567076494 17302...

output:

possible

result:

ok single line: 'possible'

Test #33:

score: 0
Accepted
time: 185ms
memory: 29476kb

input:

200000
545890204 660412901 545890205 733622540
355932631 487259674 355932632 526860621
365752045 501577171 365752046 532181952
456664249 606624304 456664250 608959227
424878061 575575020 424878062 576436135
514307716 647550525 514307717 683319940
377023151 517310122 377023152 538991213
512010801 646...

output:

possible

result:

ok single line: 'possible'

Test #34:

score: 0
Accepted
time: 149ms
memory: 19648kb

input:

200000
559500610 182638644 559500611 1000000000
704740648 124658392 704740649 1000000000
453884146 216066318 453884147 1000000000
653356372 146762800 653356373 1000000000
848640316 52892288 848640317 1000000000
729790066 113246252 729790067 1000000000
184813732 264602196 184813733 1000000000
2128339...

output:

impossible

result:

ok single line: 'impossible'

Test #35:

score: 0
Accepted
time: 111ms
memory: 18976kb

input:

200000
844231074 264768268 844231075 1000000000
374772666 721808706 374772667 1000000000
369781098 719530572 369781099 1000000000
838236438 273350001 838236439 1000000000
469648506 661772182 469648507 1000000000
808973086 312607291 808973087 1000000000
418704886 699113858 418704887 1000000000
380966...

output:

possible

result:

ok single line: 'possible'

Test #36:

score: 0
Accepted
time: 150ms
memory: 28612kb

input:

200000
831659756 530292347 856949803 530292348
780834823 657223277 780843806 657223278
851668992 442238633 924994281 442238634
791449831 635090613 792361462 635090614
648550894 860906231 709444781 860906232
643939165 866436297 708526444 866436298
623751051 888742123 706408732 888742124
785915669 646...

output:

possible

result:

ok single line: 'possible'

Test #37:

score: 0
Accepted
time: 194ms
memory: 30200kb

input:

200000
686943822 697288271 701366401 697288272
710834127 861997619 759830770 861997620
709289636 998940135 829846519 998940136
526699374 130592131 578262779 130592132
516166309 104229307 575614432 104229308
650133293 521513355 650289472 521513356
540398262 166343843 582439747 166343844
661998408 572...

output:

possible

result:

ok single line: 'possible'

Test #38:

score: 0
Accepted
time: 146ms
memory: 19700kb

input:

200000
556378024 702290569 1000000000 702290570
375383152 519806407 1000000000 519806408
47917112 238326199 1000000000 238326200
566511597 713213227 1000000000 713213228
753546817 935797585 1000000000 935797586
770625277 969716995 1000000000 969716996
733522652 908465515 1000000000 908465516
7687380...

output:

possible

result:

ok single line: 'possible'

Test #39:

score: 0
Accepted
time: 150ms
memory: 20168kb

input:

200000
506610310 652006679 1000000000 652006680
730959611 234589139 1000000000 234589140
400728590 793871621 1000000000 793871622
254808340 961013447 1000000000 961013448
354741032 850465895 1000000000 850465896
672532854 378656303 1000000000 378656304
550408527 587256803 1000000000 587256804
724112...

output:

impossible

result:

ok single line: 'impossible'

Test #40:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

3
1 4 2 5
2 3 3 4
3 4 4 5

output:

possible

result:

ok single line: 'possible'

Test #41:

score: 0
Accepted
time: 1ms
memory: 5536kb

input:

3
1 5 2 6
3 1 4 2
2 4 3 5

output:

possible

result:

ok single line: 'possible'

Test #42:

score: 0
Accepted
time: 1ms
memory: 5472kb

input:

15
1 1 2 5
2 1 3 6
3 1 4 7
4 1 5 8
5 1 6 9
6 3 7 9
7 4 8 9
8 5 9 10
9 4 10 9
10 3 11 9
11 1 12 9
12 1 13 8
13 1 14 7
14 1 15 6
15 1 16 5

output:

possible

result:

ok single line: 'possible'

Test #43:

score: 0
Accepted
time: 1ms
memory: 3432kb

input:

3
1 1 2 2
9999999 9999998 10000000 9999999
9999998 9999996 9999999 9999997

output:

possible

result:

ok single line: 'possible'

Test #44:

score: 0
Accepted
time: 1ms
memory: 5540kb

input:

3
1 1 2 2
9999998 9999998 9999999 9999999
9999997 9999996 9999998 9999997

output:

possible

result:

ok single line: 'possible'

Test #45:

score: 0
Accepted
time: 1ms
memory: 5440kb

input:

3
1 1 2 2
2 2 3 3
1 3 2 4

output:

possible

result:

ok single line: 'possible'

Test #46:

score: 0
Accepted
time: 1ms
memory: 5476kb

input:

5
1 2 2 3
2 1 3 2
999999997 999999997 999999998 999999998
999999998 999999996 999999999 999999997
999999997 999999995 999999998 999999996

output:

impossible

result:

ok single line: 'impossible'

Test #47:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

5
1 2 2 3
2 1 3 2
999999996 999999995 999999997 999999996
999999997 999999994 999999998 999999995
499999999 499999997 500000000 499999998

output:

impossible

result:

ok single line: 'impossible'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

5
1 2 2 3
2 1 3 2
999999996 999999995 999999997 999999996
999999997 999999994 999999998 999999995
499999998 499999998 499999999 499999999

output:

possible

result:

ok single line: 'possible'

Test #49:

score: 0
Accepted
time: 1ms
memory: 3492kb

input:

5
999999997 2 999999998 3
999999996 1 999999997 2
2 999999995 3 999999996
1 999999994 2 999999995
500000000 499999998 500000001 499999999

output:

possible

result:

ok single line: 'possible'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3428kb

input:

4
2 1 3 2
1 2 2 3
3 2 4 3
2 3 3 4

output:

possible

result:

ok single line: 'possible'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

4
2 1 3 2
1 2 2 3
3 4 4 5
4 3 5 4

output:

possible

result:

ok single line: 'possible'

Test #52:

score: 0
Accepted
time: 1ms
memory: 5536kb

input:

4
3 1 4 2
4 2 5 3
2 4 3 5
1 3 2 4

output:

possible

result:

ok single line: 'possible'

Test #53:

score: 0
Accepted
time: 1ms
memory: 3424kb

input:

5
2 1 3 2
1 2 2 3
3 4 4 5
4 3 5 4
2 2 4 4

output:

possible

result:

ok single line: 'possible'

Test #54:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

5
3 1 4 2
4 2 5 3
2 4 3 5
1 3 2 4
2 2 4 4

output:

possible

result:

ok single line: 'possible'

Test #55:

score: 0
Accepted
time: 1ms
memory: 5472kb

input:

6
1 1 2 2
2 2 3 3
3 3 4 4
2 1 3 2
3 2 4 3
3 1 4 2

output:

possible

result:

ok single line: 'possible'

Test #56:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

6
3 1 4 2
2 2 3 3
1 3 2 4
2 1 3 2
1 2 2 3
1 1 2 2

output:

possible

result:

ok single line: 'possible'

Test #57:

score: 0
Accepted
time: 1ms
memory: 5476kb

input:

4
1 1 3 2
3 1 4 3
1 2 2 4
2 3 4 4

output:

possible

result:

ok single line: 'possible'

Test #58:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

5
1 1 3 2
3 1 4 3
1 2 2 4
2 3 4 4
2 2 3 3

output:

possible

result:

ok single line: 'possible'

Test #59:

score: 0
Accepted
time: 1ms
memory: 5536kb

input:

4
1 1 4 2
1 3 2 4
3 3 4 4
1 5 4 6

output:

possible

result:

ok single line: 'possible'

Test #60:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

4
1 1 4 2
1 3 2 4
3 3 4 4
1 6 4 7

output:

impossible

result:

ok single line: 'impossible'

Test #61:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

4
1 1 5 2
1 3 2 4
4 3 5 4
1 5 5 6

output:

impossible

result:

ok single line: 'impossible'

Test #62:

score: 0
Accepted
time: 1ms
memory: 5472kb

input:

11
1 1 2 5
1 5 3 6
2 4 7 5
8 8 9 12
4 5 5 7
4 7 6 8
5 5 6 7
6 5 7 8
3 5 4 8
3 8 8 9
7 2 8 8

output:

possible

result:

ok single line: 'possible'

Test #63:

score: 0
Accepted
time: 1ms
memory: 5468kb

input:

11
8 1 9 5
7 5 9 6
3 4 8 5
1 8 2 12
5 5 6 7
4 7 6 8
4 5 5 7
3 5 4 8
6 5 7 8
2 8 7 9
2 2 3 8

output:

possible

result:

ok single line: 'possible'

Test #64:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

3
1 1 2 2
2 3 3 4
1 5 2 6

output:

possible

result:

ok single line: 'possible'

Test #65:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

3
999999998 3 999999999 4
999999997 1 999999998 2
999999996 999999998 999999997 999999999

output:

impossible

result:

ok single line: 'impossible'

Test #66:

score: 0
Accepted
time: 0ms
memory: 3420kb

input:

3
999999998 2 999999999 3
999999997 1 999999998 2
999999996 999999998 999999997 999999999

output:

possible

result:

ok single line: 'possible'

Test #67:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

3
999999998 1 999999999 2
999999997 3 999999998 4
999999996 999999998 999999997 999999999

output:

possible

result:

ok single line: 'possible'

Test #68:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

1
0 0 1 1

output:

possible

result:

ok single line: 'possible'

Test #69:

score: 0
Accepted
time: 1ms
memory: 5468kb

input:

1
999999999 999999999 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #70:

score: 0
Accepted
time: 1ms
memory: 5528kb

input:

1
0 0 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #71:

score: 0
Accepted
time: 113ms
memory: 8124kb

input:

200000
1 149207 177011 149208
1 250625 297332 250626
1 150344 178360 150345
1 391761 464773 391762
7135 1 7136 6021
1 498613 591541 498614
1 390943 463803 390944
1 581842 690282 581843
1 835150 990803 835151
1 754416 895021 754417
1 356555 423005 356556
177276 1 177277 149432
1 451339 535455 451340
...

output:

possible

result:

ok single line: 'possible'

Test #72:

score: 0
Accepted
time: 124ms
memory: 8140kb

input:

200000
1 696969 826867 696970
938207 1 938208 790819
892676 1 892677 752441
1 190373 225850 190374
1 715182 848475 715183
1 537506 637683 537507
1 307378 364663 307379
539381 1 539382 454650
975802 1 975803 822508
1 800042 949151 800043
394619 1 394620 332630
108948 1 108949 91839
1 2720 3221 2721
1...

output:

impossible

result:

ok single line: 'impossible'

Test #73:

score: 0
Accepted
time: 90ms
memory: 7760kb

input:

200000
385175 365578 385176 365579
300614 470004 300615 470005
419784 322839 419785 322840
79247 743356 79263 743357
63977 762185 64016 762186
248897 533869 248899 533870
530082 186616 530083 186631
376213 376643 376214 376646
640957 49688 640958 49709
55344 772892 55345 772894
573983 132403 573984 ...

output:

possible

result:

ok single line: 'possible'

Test #74:

score: 0
Accepted
time: 131ms
memory: 7792kb

input:

200000
277928 441016 277929 441017
38203 737046 38215 737047
107600 651352 107601 651360
553840 100242 553841 100284
550982 103811 550983 103814
130949 622516 130950 622526
70356 697351 70359 697352
375705 320265 375706 320269
224082 507507 224087 507508
251321 473872 251322 473875
182993 558254 182...

output:

impossible

result:

ok single line: 'impossible'

Test #75:

score: 0
Accepted
time: 120ms
memory: 8152kb

input:

200000
780657 658019 780695 658020
533390 449573 533391 449600
614515 517820 614516 517980
513457 432797 513458 432801
977953 824503 978171 824504
33855 28542 33856 28543
350258 295224 350259 295238
685219 577575 685220 577576
976126 822780 976136 822781
228399 192523 228403 192524
628364 529655 628...

output:

possible

result:

ok single line: 'possible'

Test #76:

score: 0
Accepted
time: 127ms
memory: 8172kb

input:

200000
656935 553735 656937 553736
440992 371799 441090 371800
391162 330627 392245 330628
676333 548180 676334 570086
549046 462795 549058 462796
822092 692945 822093 692946
866467 730665 866843 730666
175645 147917 175646 148057
365798 308336 365824 308337
741843 625303 741844 625304
325518 274384...

output:

impossible

result:

ok single line: 'impossible'

Test #77:

score: 0
Accepted
time: 79ms
memory: 7708kb

input:

200000
370349 420874 371004 420875
110733 741488 154653 741489
424310 354235 424311 354251
605217 130816 605224 130817
125875 722788 125876 722789
464667 304396 464670 304397
495679 266097 496802 266098
427495 350301 427496 350457
523121 232208 523122 232209
52289 813663 52290 813664
268784 546302 2...

output:

possible

result:

ok single line: 'possible'

Test #78:

score: 0
Accepted
time: 120ms
memory: 7704kb

input:

200000
157232 646689 157235 646690
619387 74857 619388 74860
49339 780189 49341 780190
339101 421662 339103 421663
495550 228085 495551 228088
440715 295927 440721 295928
525976 190432 525982 190433
81000 741008 81007 741009
161986 640804 161992 640805
251773 529715 251774 529717
655313 30407 655730...

output:

impossible

result:

ok single line: 'impossible'

Test #79:

score: 0
Accepted
time: 9ms
memory: 3968kb

input:

20973
5496 3932 5500 3934
2038 9716 2092 9717
4676 5305 4677 5313
5154 4480 5162 4492
1307 10937 1308 10943
5385 4118 5386 4122
5197 2794 6176 2795
7355 808 7361 811
303 12624 304 12625
2050 9699 2051 9700
1039 11392 1041 11393
4022 6399 4023 6400
6192 2755 6195 2763
6441 2332 6452 2333
5429 4044 54...

output:

possible

result:

ok single line: 'possible'

Test #80:

score: 0
Accepted
time: 45ms
memory: 12256kb

input:

113132
799436029 399979233 799436030 400033707
800007573 137372284 800007574 662640656
530922654 400001383 530922655 400011557
35835236 399986648 35835237 400026292
251345273 400000605 251345274 400012335
799992654 367990186 799992655 432022754
614077254 399997468 614077255 400015472
800012009 25871...

output:

possible

result:

ok single line: 'possible'

Test #81:

score: 0
Accepted
time: 108ms
memory: 13448kb

input:

113132
21298 375572599 21299 424440344
2701 72720454 2702 727292489
259823 399978869 259824 400034074
388577909 400006065 388577910 400006878
423274581 400005637 423274582 400007306
6966 172738969 6967 627273974
800005326 186343405 800005327 613669538
630897802 399996578 630897803 400016365
79999631...

output:

impossible

result:

ok single line: 'impossible'

Test #82:

score: 0
Accepted
time: 129ms
memory: 8176kb

input:

200000
39445174 30184921 39445178 30184925
327727743 250636295 327727744 250636296
383245654 293091461 383246038 293091845
168192484 128638744 168192485 128638745
448020249 342624685 448020254 342624690
278245622 212797026 278245623 212797027
356799188 272867400 356799189 272867401
3779534 2911194 3...

output:

possible

result:

ok single line: 'possible'

Test #83:

score: 0
Accepted
time: 139ms
memory: 8216kb

input:

200000
230946652 230946778 230946653 230946779
226617518 226617641 226617520 226617643
141829697 141829823 141829698 141829824
266158769 266158895 266158770 266158896
162747929 162748057 162747932 162748060
315923640 315923766 315923641 315923767
316149576 316149703 316149578 316149705
239706272 239...

output:

possible

result:

ok single line: 'possible'

Test #84:

score: 0
Accepted
time: 138ms
memory: 8172kb

input:

200000
649298423 796866093 649304077 796873032
493027627 605079207 493028177 605079882
280841367 344668797 280844227 344672307
150711037 184963392 150711983 184964553
285520239 350411049 285520283 350411103
371719363 456200883 371723829 456206364
390014739 478654299 390016125 478656000
137962719 169...

output:

impossible

result:

ok single line: 'impossible'

Test #85:

score: 0
Accepted
time: 132ms
memory: 8108kb

input:

200000
343937798 343933665 343939819 343935686
651753087 651748954 651754003 651749870
41623228 41619095 41625973 41621840
310406967 310402834 310411800 310407667
50057463 50053330 50059051 50054918
246327813 246323680 246340549 246336416
338011725 338007592 338013928 338009795
427775775 427771642 4...

output:

impossible

result:

ok single line: 'impossible'

Test #86:

score: 0
Accepted
time: 127ms
memory: 8140kb

input:

200000
207097280 310645122 207097596 310645596
68355522 102532485 68357164 102534948
409792210 614687517 409792786 614688381
172557334 258835203 172558586 258837081
206018844 309027468 206021290 309031137
241874460 362810892 241875268 362812104
515366706 773049261 515371026 773055741
417799306 62669...

output:

impossible

result:

ok single line: 'impossible'

Test #87:

score: 0
Accepted
time: 1ms
memory: 5504kb

input:

5
84824278 418910089 234643448 868564319
417241321 393558766 422879110 922520137
426597549 396398302 442303689 922611039
488699915 420176764 523651705 921232998
700852378 566058023 931170340 890546929

output:

possible

result:

ok single line: 'possible'

Test #88:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

20
46164108 236987837 92514477 836030726
107223931 294849707 112567898 830024504
132556373 317194776 139906186 827701561
180814338 357067167 224092854 823550478
281260349 428725445 320564875 816063077
324334556 454763837 351128769 813329391
354271604 471202312 357522802 811598146
445502225 512909475...

output:

possible

result:

ok single line: 'possible'

Test #89:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

1000
434936 364464056 1267375 974507461
1991644 364124131 2042086 973126634
2742137 363960478 2940388 972461994
3250914 363849618 3524895 972011811
3647781 363763189 4089151 971660870
4293689 363622611 4685324 971090119
5132017 363440318 5151907 970350100
6242700 363199083 6472024 969370989
7196825 ...

output:

possible

result:

ok single line: 'possible'

Test #90:

score: 0
Accepted
time: 65ms
memory: 9372kb

input:

200000
4239 818865124 6577 853151974
9874 818866288 13419 853155879
14626 818867268 14668 853159172
17418 818867845 17975 853161107
20373 818868455 21156 853163154
23413 818869082 24087 853165261
24704 818869349 24950 853166155
25791 818869573 28219 853166908
28264 818870083 30110 853168622
30540 81...

output:

impossible

result:

ok single line: 'impossible'

Test #91:

score: 0
Accepted
time: 63ms
memory: 8004kb

input:

200000
2842 491094723 3706 830387847
4999 491096322 5490 830384935
7001 491097807 9006 830382232
9016 491099302 16679 830379511
23507 491110050 28636 830359948
29740 491114673 35022 830351533
39355 491121805 44105 830338553
44366 491125522 47910 830331789
48595 491128658 54255 830326080
62247 491138...

output:

possible

result:

ok single line: 'possible'

Test #92:

score: 0
Accepted
time: 74ms
memory: 8156kb

input:

200000
1574 21391523 2243 566238961
3547 21394630 5058 566238125
5176 21397195 6911 566237434
8975 21403178 9953 566235823
11455 21407083 16142 566234772
18396 21418013 18450 566231829
21955 21423617 26664 566230320
28177 21433415 31781 566227682
33956 21442515 34582 566225232
37008 21447321 39810 5...

output:

possible

result:

ok single line: 'possible'

Test #93:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

5
33318469 79020281 37005049 346704446
357538079 66580243 448699194 334264408
768874022 229259343 771523913 496943508
819324440 262953608 850832674 530637773
894290146 318566477 941454889 586250642

output:

possible

result:

ok single line: 'possible'

Test #94:

score: 0
Accepted
time: 1ms
memory: 5544kb

input:

20
27338524 414089751 30944154 727519324
78668278 354838943 81487537 668268516
136686048 295039017 146131309 608468590
148388281 283899541 154449354 597329114
221229792 221521907 227859391 534951480
230073098 214765481 261600234 528195054
323597074 154133290 324094966 467562863
351879404 139691649 3...

output:

possible

result:

ok single line: 'possible'

Test #95:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

1000
752701 158758957 1083950 418645552
1271287 158923616 1383446 418810211
1635215 159039068 2027996 418925663
2746918 159391228 4047083 419277823
4545829 159959435 6563065 419846030
6582093 160600161 6765834 420486756
6815322 160673383 7320960 420559978
7352262 160841822 8136049 420728417
9070300 ...

output:

possible

result:

ok single line: 'possible'

Test #96:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

5000
78447 171119645 203651 360997014
269410 171383542 273981 361260911
332768 171471086 533274 361348455
642304 171898693 647313 361776062
672529 171940439 793757 361817808
886172 172235479 892071 362112848
898858 172252996 962299 362130365
1057495 172472024 1105335 362349393
1114214 172550326 1161...

output:

impossible

result:

ok single line: 'impossible'

Test #97:

score: 0
Accepted
time: 5ms
memory: 5796kb

input:

10000
14484 326880126 130390 348928295
205761 327129050 239388 349177219
407607 327391676 468543 349439845
542814 327567565 642091 349615734
659400 327719211 671320 349767380
673224 327737191 724410 349785360
828608 327939271 883702 349987440
958348 328107976 1011088 350156145
1107527 328301930 1136...

output:

impossible

result:

ok single line: 'impossible'

Test #98:

score: 0
Accepted
time: 71ms
memory: 10708kb

input:

200000
2717 267704322 10275 337312967
10806 267700941 14064 337309586
19850 267697162 29725 337305807
29772 267693016 37570 337301661
41305 267688196 47433 337296841
47519 267685600 47934 337294245
48342 267685256 51636 337293901
52394 267683563 53053 337292208
54136 267682835 54139 337291480
54903 ...

output:

impossible

result:

ok single line: 'impossible'

Test #99:

score: 0
Accepted
time: 54ms
memory: 8144kb

input:

200000
4481 471749178 13163 961802779
20704 471749137 22178 961802738
22926 471749132 26656 961802733
27526 471749120 28097 961802721
30530 471749113 31039 961802714
39816 471749089 46258 961802690
47308 471749070 47608 961802671
51720 471749059 51748 961802660
60016 471749038 67059 961802639
74113 ...

output:

possible

result:

ok single line: 'possible'

Test #100:

score: 0
Accepted
time: 56ms
memory: 8580kb

input:

200000
3007 474716193 9696 547269918
9714 474717235 11100 547270960
12390 474717650 15932 547271375
19119 474718696 19265 547272421
21151 474719011 21406 547272736
25297 474719655 27293 547273380
30011 474720388 30423 547274113
33010 474720854 36420 547274579
37056 474721482 39316 547275207
42737 47...

output:

possible

result:

ok single line: 'possible'

Test #101:

score: 0
Accepted
time: 1ms
memory: 3420kb

input:

5
94121767 384769963 225761381 556264172
271500421 382571891 297356757 556039739
365124878 379476196 428052740 555826502
484599800 373583576 499821414 555459287
573946455 367753652 660031184 555114980

output:

possible

result:

ok single line: 'possible'

Test #102:

score: 0
Accepted
time: 0ms
memory: 5536kb

input:

20
42146630 375431302 83220591 874707713
128959993 447678773 132415551 869732496
154999193 467508393 157790558 868387799
165956013 475598434 168419478 867842333
191075905 493578238 197615442 866637302
212651121 508389874 220774914 865652913
313135275 569691068 324992855 861684245
329573597 578515531...

output:

possible

result:

ok single line: 'possible'

Test #103:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

1000
571596 101102498 1011200 797851954
1134732 101596848 1307714 797836719
1846192 102220888 2510815 797817562
4846219 104845941 4876383 797737891
5095790 105063855 5177393 797731344
5899363 105765018 6012390 797710348
6197674 106025124 6384440 797702586
6891213 106629449 7205306 797684610
7482374 ...

output:

possible

result:

ok single line: 'possible'

Test #104:

score: 0
Accepted
time: 3ms
memory: 5596kb

input:

5000
11810 160060001 198532 474529373
258160 159968328 361825 474485590
396229 159916963 784302 474461069
949205 159711349 1112469 474362979
1127507 159645085 1246045 474331392
1398813 159544292 1458615 474283369
1480530 159513941 1681626 474268913
1862318 159372186 1870729 474201432
1956591 1593371...

output:

possible

result:

ok single line: 'possible'

Test #105:

score: 0
Accepted
time: 5ms
memory: 3680kb

input:

10000
34232 4081202 87810 817060151
138502 4246856 147911 817079712
155510 4273876 222831 817082902
334671 4558464 342139 817116507
401441 4664512 505246 817129029
535214 4876956 547785 817154115
650739 5060397 686716 817175775
712295 5158132 853414 817187316
867803 5405012 874039 817216467
981381 5...

output:

possible

result:

ok single line: 'possible'

Test #106:

score: 0
Accepted
time: 65ms
memory: 8316kb

input:

200000
272 64691870 557 834787814
2344 64691566 8350 834787279
10633 64690346 11807 834785139
12057 64690136 15311 834784772
16067 64689546 16366 834783736
20853 64688841 24216 834782501
25191 64688203 28974 834781381
29884 64687512 31581 834780169
33059 64687045 37944 834779350
38545 64686238 39781...

output:

possible

result:

ok single line: 'possible'

Test #107:

score: 0
Accepted
time: 55ms
memory: 8328kb

input:

200000
3532 32938781 6087 962609722
6879 32938719 9127 962606061
16261 32938546 21758 962595801
22920 32938423 23556 962588519
30115 32938290 32211 962580650
33518 32938227 36977 962576929
38590 32938133 45272 962571382
45947 32937997 52149 962563337
52239 32937880 62097 962556456
62190 32937696 634...

output:

possible

result:

ok single line: 'possible'

Test #108:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

5
37821 184782484 37822 184999404
182453 73956210 182454 74266310
64327 164484492 64328 164646072
176440 62125712 176441 78572622
167814 70949210 167815 85439544

output:

possible

result:

ok single line: 'possible'

Test #109:

score: 0
Accepted
time: 1ms
memory: 5576kb

input:

20
93783 539287640 93784 539786726
56604 445338086 56605 473485515
72311 493802405 72312 507456906
123383 560079802 123384 591675895
15949 258551131 15950 519469248
168086 503470094 168087 808812989
135391 555384133 135392 660394333
196464 412011584 196465 975907220
50084 421340691 50085 495439389
1...

output:

possible

result:

ok single line: 'possible'

Test #110:

score: 0
Accepted
time: 2ms
memory: 5556kb

input:

5000
146783 131155951 146784 226826068
180852 57774728 180853 202530300
37266 386101661 37267 388640393
187174 43313386 187175 199381254
199097 7122973 199098 194600367
13998 439446086 13999 439467472
184891 40948366 184892 200469348
149370 129788643 149371 224547616
166689 90172068 166690 211129547...

output:

possible

result:

ok single line: 'possible'

Test #111:

score: 0
Accepted
time: 3ms
memory: 6152kb

input:

10000
151566 399916480 151567 403750937
125933 424632562 125934 430838873
35939 411528531 35940 739593779
135441 416936272 135442 417643269
61743 431184317 61744 617055700
86395 438023646 86396 525527058
108007 434422497 108008 465814705
32428 407866163 32429 758380100
139284 413333064 139285 413363...

output:

possible

result:

ok single line: 'possible'

Test #112:

score: 0
Accepted
time: 7ms
memory: 5620kb

input:

10000
70658 390900321 70659 399389333
99088 459982029 99089 462828098
148415 572701907 148416 572896474
40081 331159747 40082 376982632
24047 295381444 24048 357405770
29977 286816900 29978 308613660
161121 600270006 161122 601248670
97157 458519259 97158 466534999
187586 655761316 187587 660302730
...

output:

possible

result:

ok single line: 'possible'

Test #113:

score: 0
Accepted
time: 100ms
memory: 7736kb

input:

200000
163388 730437022 163389 878367039
2 989488192 3 991344117
73809 938140488 73810 939290998
139142 810934032 139143 897251799
176730 678455019 176731 874738434
2819 928034675 2820 987572311
122733 855187441 122734 906017086
60216 948535790 60217 948546416
46035 958180491 46036 958340207
146159 ...

output:

possible

result:

ok single line: 'possible'

Test #114:

score: 0
Accepted
time: 86ms
memory: 10420kb

input:

200000
186077 295859267 186078 301363500
161811 340009212 161812 340144821
186282 295469101 186283 301052016
147870 363548996 147871 364138889
89465 447692577 89466 478256739
152486 355902203 152487 356055716
178355 310346442 178356 313293535
176805 313205150 176806 315734438
63846 477227392 63847 5...

output:

possible

result:

ok single line: 'possible'

Test #115:

score: 0
Accepted
time: 125ms
memory: 8184kb

input:

200000
195052 538505718 195053 854030936
132888 409636292 132889 417077409
168795 487216497 168796 656480754
15313 187411790 15314 405628044
24249 204866963 24250 377910687
93519 340175808 93520 340555028
104474 361574803 104475 363444024
168256 486163639 168257 652898710
60962 276580455 60963 31894...

output:

possible

result:

ok single line: 'possible'

Test #116:

score: 0
Accepted
time: 89ms
memory: 7740kb

input:

200000
60277 581844719 60278 583292614
135556 277530291 135557 292689576
81933 495106358 81934 495331976
169834 132146615 169835 138302608
82832 491482678 82833 491680489
145825 233019195 145826 235820476
184856 68369332 184857 77287430
121577 333572518 121578 334309095
180750 85852424 180751 939648...

output:

possible

result:

ok single line: 'possible'

Test #117:

score: 0
Accepted
time: 1ms
memory: 5460kb

input:

5
410865392 255850973 410865393 263681844
811772162 658598727 811772163 662747630
939779637 777656766 939779638 799704541
466171737 315072753 466171738 315072754
208778137 14344118 208778138 101014189

output:

possible

result:

ok single line: 'possible'

Test #118:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

20
900705907 763111778 900705908 844685419
4343407 82419145 4343408 180834302
337997979 381591654 337997980 382143651
988279147 798013499 988279148 941143558
584786823 555576663 584786824 578341908
246341475 311217281 246341476 315033268
989348647 789302278 989348648 951459029
506439547 502100916 50...

output:

possible

result:

ok single line: 'possible'

Test #119:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

1000
214688352 719023386 214688353 747193541
66088620 772053969 66088621 842762690
114728160 756003790 114728161 810173329
541835628 568753663 541835629 570315988
9256728 783824298 9256729 887824253
907702216 346686203 907702217 426516860
460927424 609913897 460927425 610063958
149987648 743437967 1...

output:

possible

result:

ok single line: 'possible'

Test #120:

score: 0
Accepted
time: 5ms
memory: 6000kb

input:

5000
972695965 371803175 972695966 459216010
733733701 534985295 733733702 534996154
496589329 603596634 496589330 703529187
717402861 542866592 717402862 543445697
756271343 523414655 756271344 524029152
969258757 375263039 969258758 459193354
989328619 351906603 989328620 462479928
498815133 60447...

output:

possible

result:

ok single line: 'possible'

Test #121:

score: 0
Accepted
time: 8ms
memory: 4592kb

input:

10000
660506321 353115580 660506322 377674833
848020643 119884691 848020644 235877078
296641754 719404514 296641755 739115033
813777707 171338748 813777708 252908893
386829371 636945639 386829372 641198674
483260555 542521551 483260556 542760394
823603307 158219732 823603308 246376709
190967456 8093...

output:

possible

result:

ok single line: 'possible'

Test #122:

score: 0
Accepted
time: 122ms
memory: 29496kb

input:

200000
823380219 457248531 823380220 523913410
434550857 660792277 434550858 709199026
488228719 646281225 488228720 670032216
855352219 425732144 855352220 523457797
783616669 488923356 783616670 532002135
459786091 654508796 459786092 690247273
700332847 546510847 700332848 557698466
372738185 666...

output:

possible

result:

ok single line: 'possible'

Test #123:

score: 0
Accepted
time: 151ms
memory: 32068kb

input:

200000
674064697 430835244 674064698 441890293
438637 712541080 438638 833810517
682141685 426262609 682141686 438385940
525747437 510420199 525747438 510622598
513973917 516383301 513973918 516433016
620012569 460805837 620012570 465971828
881418097 305596643 881418098 359775494
947881 713305398 94...

output:

possible

result:

ok single line: 'possible'

Test #124:

score: 0
Accepted
time: 179ms
memory: 29768kb

input:

200000
430844957 731696407 430844958 732817190
513353185 764565760 513353186 782456065
334711127 680662721 334711128 687717046
382082945 707536374 382082946 708215211
652582737 784310903 652582738 901940474
628942579 791497918 628942580 871113301
165277053 553089371 165277054 645856322
641825651 790...

output:

possible

result:

ok single line: 'possible'

Test #125:

score: 0
Accepted
time: 1ms
memory: 5488kb

input:

5
375716583 14930099 375716584 1000000000
531009499 715254478 531009500 1000000000
568377526 0 568377527 871225811
451942078 0 451942079 415778309
531009500 0 531009501 715254489

output:

possible

result:

ok single line: 'possible'

Test #126:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

20
787084397 297862869 787084398 1000000000
834729939 139949997 834729940 1000000000
693111083 573529430 693111084 1000000000
583676923 876648866 583676924 1000000000
740237137 435988887 740237138 1000000000
602958007 830863699 602958008 1000000000
838857143 109913050 838857144 1000000000
572403785 ...

output:

impossible

result:

ok single line: 'impossible'

Test #127:

score: 0
Accepted
time: 2ms
memory: 5628kb

input:

1000
510705251 383198580 510705252 1000000000
653128811 287512148 653128812 1000000000
553747637 355621611 553747638 1000000000
863301101 119403382 863301102 1000000000
394552439 451304743 394552440 1000000000
911213477 72718667 911213478 1000000000
372639353 463326619 372639354 1000000000
179323535...

output:

impossible

result:

ok single line: 'impossible'

Test #128:

score: 0
Accepted
time: 2ms
memory: 5888kb

input:

5000
698955129 411649399 698955130 1000000000
840888577 642617902 840888578 1000000000
595601535 148116332 595601536 1000000000
839825815 643041704 839825816 1000000000
789278797 578274984 789278798 1000000000
823226891 627602382 823226892 1000000000
837940471 642599728 837940472 1000000000
78016682...

output:

possible

result:

ok single line: 'possible'

Test #129:

score: 0
Accepted
time: 8ms
memory: 4088kb

input:

10000
445144021 475459729 445144022 1000000000
685086847 732426527 685086848 1000000000
457277985 505043775 457277986 1000000000
695353639 726982287 695353640 1000000000
695515595 726409722 695515596 1000000000
653189401 720949906 653189402 1000000000
620935629 701123328 620935630 1000000000
4753049...

output:

possible

result:

ok single line: 'possible'

Test #130:

score: 0
Accepted
time: 168ms
memory: 20268kb

input:

200000
231829561 790444432 231829562 1000000000
512972701 418105224 512972702 1000000000
315963165 695874133 315963166 1000000000
673993617 147535474 673993618 1000000000
573433097 321180713 573433098 1000000000
521456469 404833813 521456470 1000000000
712598505 73002270 712598506 1000000000
3770327...

output:

impossible

result:

ok single line: 'impossible'

Test #131:

score: 0
Accepted
time: 164ms
memory: 19488kb

input:

200000
781073336 717341686 781073337 1000000000
591160838 112728209 591160839 1000000000
597518780 139390806 597518781 1000000000
685349924 442144561 685349925 1000000000
768374768 684007079 768374769 1000000000
822187664 817385999 822187665 1000000000
802005200 770142462 802005201 1000000000
684365...

output:

possible

result:

ok single line: 'possible'

Test #132:

score: 0
Accepted
time: 155ms
memory: 18688kb

input:

200000
80607010 244627399 80607011 1000000000
109064134 339424281 109064135 1000000000
36224726 84668744 36224727 1000000000
131060178 409363911 131060179 1000000000
256343646 751650647 256343647 1000000000
30486372 60568647 30486373 1000000000
194472300 594757291 194472301 1000000000
249050788 7347...

output:

impossible

result:

ok single line: 'impossible'

Test #133:

score: 0
Accepted
time: 160ms
memory: 19844kb

input:

200000
697502932 318013353 697502933 1000000000
837173980 335417033 837173981 1000000000
201395776 140215245 201395777 1000000000
173012014 124687519 173012015 1000000000
583093828 291474397 583093829 1000000000
431699860 243082808 431699861 1000000000
298281202 187797578 298281203 1000000000
165639...

output:

impossible

result:

ok single line: 'impossible'

Test #134:

score: 0
Accepted
time: 124ms
memory: 18688kb

input:

200000
181028903 820508027 181028904 1000000000
783955661 256039044 783955662 1000000000
495613937 561151857 495613938 1000000000
923793881 77743538 923793882 1000000000
226836233 794491658 226836234 1000000000
217808417 800993433 217808418 1000000000
860845037 164861115 860845038 1000000000
6832623...

output:

possible

result:

ok single line: 'possible'

Test #135:

score: 0
Accepted
time: 159ms
memory: 20112kb

input:

200000
716566600 530087934 716566601 1000000000
158253652 326089308 158253653 1000000000
856945690 539427361 856945691 1000000000
470928562 466110198 470928563 1000000000
349037620 419599457 349037621 1000000000
499579372 475622905 499579373 1000000000
419139064 447547028 419139065 1000000000
207164...

output:

impossible

result:

ok single line: 'impossible'

Test #136:

score: 0
Accepted
time: 0ms
memory: 5476kb

input:

20
484596193 408592930 484596194 408592931
383424103 568215104 426146110 568215105
579643804 135449012 662692501 135449013
566294565 210928302 600562450 210928303
524206281 321392364 532186672 321392365
578531258 123648190 675605869 123648191
504159696 365731442 507894179 365731443
493527290 3891572...

output:

possible

result:

ok single line: 'possible'

Test #137:

score: 0
Accepted
time: 1ms
memory: 5548kb

input:

20
396448483 713768628 1000000000 713768629
355757876 700087016 1000000000 700087017
125535155 626077102 1000000000 626077103
600755531 789210364 1000000000 789210365
495576432 750330492 1000000000 750330493
831753276 881284398 1000000000 881284399
238025215 660573120 1000000000 660573121
697240534 ...

output:

possible

result:

ok single line: 'possible'

Test #138:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

5
0 630006287 107555498 953833576
0 966227647 1000000000 1000000000
0 953833576 1000000000 966227647
107555498 0 1000000000 953833576
0 0 107555498 630006287

output:

possible

result:

ok single line: 'possible'

Test #139:

score: 0
Accepted
time: 2ms
memory: 5528kb

input:

7
0 0 187097086 46302099
493974893 46302099 551214780 1000000000
0 46302099 493974893 1000000000
488494670 0 551214780 46302099
187097086 0 487236028 46302099
487236028 0 488494670 46302099
551214780 0 1000000000 1000000000

output:

possible

result:

ok single line: 'possible'

Test #140:

score: 0
Accepted
time: 1ms
memory: 5540kb

input:

10
0 215016918 322941455 541077350
0 185955372 10839067 215016918
944751651 0 992081086 1000000000
0 0 10839067 185955372
322941455 215016918 636671085 541077350
636671085 0 944751651 541077350
0 541077350 944751651 683614356
992081086 0 1000000000 1000000000
0 683614356 944751651 1000000000
1083906...

output:

possible

result:

ok single line: 'possible'

Test #141:

score: 0
Accepted
time: 1ms
memory: 5484kb

input:

10
0 0 100841680 527292929
0 726898378 1000000000 1000000000
110283684 0 1000000000 527292929
699826046 527292929 857262588 531854144
100841680 0 110283684 527292929
0 527292929 68980001 726898378
198694710 527292929 699826046 726898378
699826046 531854144 857262588 726898378
857262588 527292929 100...

output:

impossible

result:

ok single line: 'impossible'

Test #142:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

7
0 1 1 2
1 4 5 5
0 0 2 1
2 0 5 1
1 2 5 4
1 1 5 2
0 2 1 5

output:

impossible

result:

ok single line: 'impossible'

Test #143:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

7
0 0 5 2
0 4 1 5
1 4 2 5
0 2 5 4
2 4 3 5
4 4 5 5
3 4 4 5

output:

impossible

result:

ok single line: 'impossible'

Test #144:

score: 0
Accepted
time: 1ms
memory: 3496kb

input:

7
0 0 2 1
0 4 3 5
0 1 2 3
2 0 3 3
3 2 5 5
3 0 5 2
0 3 3 4

output:

impossible

result:

ok single line: 'impossible'

Test #145:

score: 0
Accepted
time: 1ms
memory: 5580kb

input:

5
665979365 970969239 1000000000 971543995
665979365 971543995 911571453 1000000000
353180068 0 929981428 970969239
911571453 971543995 1000000000 1000000000
0 987555998 132247495 1000000000

output:

possible

result:

ok single line: 'possible'

Test #146:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

5
0 0 1000000000 359982397
460923986 359982397 1000000000 390373020
0 359982397 435280756 390373020
495395093 805352880 1000000000 1000000000
435280756 359982397 436722833 390373020

output:

possible

result:

ok single line: 'possible'

Test #147:

score: 0
Accepted
time: 0ms
memory: 5540kb

input:

5
0 1 3 7
0 0 2 1
3 1 4 2
3 0 4 1
2 0 3 1

output:

possible

result:

ok single line: 'possible'

Test #148:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

5
1 4 2 5
2 2 7 7
0 1 2 2
2 0 7 2
0 5 1 6

output:

possible

result:

ok single line: 'possible'

Test #149:

score: 0
Accepted
time: 1ms
memory: 5508kb

input:

7
0 0 2 7
2 1 4 2
6 5 7 6
3 4 4 5
4 0 7 4
6 6 7 7
2 0 4 1

output:

impossible

result:

ok single line: 'impossible'

Test #150:

score: -100
Wrong Answer
time: 1ms
memory: 5504kb

input:

5
2 6 3 7
3 6 4 7
6 6 7 7
4 6 5 7
1 6 2 7

output:

impossible

result:

wrong answer 1st lines differ - expected: 'possible', found: 'impossible'