QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166190#1192. Halting ProblemSortingAC ✓585ms61628kbC++209.4kb2023-09-06 01:45:422023-09-06 01:45:42

Judging History

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

  • [2023-09-06 01:45:42]
  • 评测
  • 测评结果:AC
  • 用时:585ms
  • 内存:61628kb
  • [2023-09-06 01:45:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 1e5 + 7 ;
const int MOD = 1e9 + 7 ;
const ll inf = 1e18 + 7 ;

int n ;
ll init_val ;
struct elem {
    ll targ , spec_add , spec_move ;
    ll add , move ;
};
elem a[ MAXN ] ;
vector < int > v[ MAXN ] ;
vector < int > cycles[ MAXN ] ;
int cycle_id[ MAXN ] ;
ll cycle_len[ MAXN ] ;
ll dist_to_ori[ MAXN ] ;
int used[ MAXN ] ;

int subtree[ MAXN ] , heavy[ MAXN ] ,  lvl[ MAXN ] , lst[ MAXN ] ;
int pos[ MAXN ] , root[ MAXN ] , rv[ MAXN ] ;

void dfs ( int x , ll sm ) {
    subtree[ x ] = 1 ; 
    for ( auto y : v[ x ] ) {
        if ( cycle_id[ y ] > 0 ) { continue ; }
        dist_to_ori[ y ] = sm + a[ y ].add ;
        lvl[ y ] = lvl[ x ] + 1 ;
        lst[ y ] = x ;
        dfs ( y , sm + a[ y ].add ) ;
        subtree[ x ] += subtree[ y ] ;
        if ( subtree[ heavy[ x ] ] < subtree[ y ] ) {
            heavy[ x ] = y ;
        }
    }
}

class Tree {
public :
    vector < ll > tr[ 4 * MAXN ] ;
    void unite ( int w ) {
        int l = 2 * w , r = 2 * w + 1 ;
        int sz1 = tr[ l ].size ( ) , sz2 = tr[ r ].size ( ) ;
        int pos1 = 0 , pos2 = 0 ;
        while ( pos1 < sz1 || pos2 < sz2 ) {
            if ( pos1 == sz1 ) {
                tr[ w ].push_back ( tr[ r ][ pos2 ++ ] ) ;
            }
            else if ( pos2 == sz2 ) {
                tr[ w ].push_back ( tr[ l ][ pos1 ++ ] ) ;
            }
            else {
                if ( tr[ l ][ pos1 ] <= tr[ r ][ pos2 ] ) {
                    tr[ w ].push_back ( tr[ l ][ pos1 ++ ] ) ;
                }
                else {
                    tr[ w ].push_back ( tr[ r ][ pos2 ++ ] ) ;
                }
            }
        }
    }
    void init ( int w , int l , int r ) {
        if ( l == r ) {
            if ( cycle_id[ rv[ l ] ] == 0 ) { 
                tr[ w ].push_back ( a[ rv[ l ] ].targ + dist_to_ori[ rv[ l ] ] ) ;
            }
            else {
                tr[ w ].push_back ( a[ rv[ l ] ].targ ) ;
            }
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid ) ;
        init ( 2 * w + 1 , mid + 1 , r ) ;
        unite ( w ) ;
    }
    int getr ( int w , int l , int r , int st , int en , ll sr ) {
        if ( l > r || st > en ) { return -1 ; }
        if ( r < st || en < l ) { return -1 ; }
        if ( st <= l && r <= en ) { 
            auto it = lower_bound ( tr[ w ].begin ( ) , tr[ w ].end ( ) , sr ) ;
            if ( it == tr[ w ].end ( ) || *it != sr ) {
                return -1 ;
            }
        }
        if ( l == r ) { return l ; }
        int mid = ( l + r ) / 2 ;
        int ret = getr ( 2 * w + 1 , mid + 1 , r , st , en , sr ) ;
        if ( ret != -1 ) { return ret ; }
        return getr ( 2 * w , l , mid , st , en , sr ) ;
    }
};
Tree w ;

bool seen[ MAXN ] ;

struct cycle_elem {
    ll rem , stval , id ;
};

bool cmp ( cycle_elem p1 , cycle_elem p2 ) {
    if ( p1.rem != p2.rem ) { return p1.rem < p2.rem ; }
    if ( p1.stval != p2.stval ) { return p1.stval < p2.stval ; }
    return p1.id < p2.id ;
}
int at_pos[ MAXN ] ;
vector < cycle_elem > srt[ MAXN ] ;

bool leq ( cycle_elem p1 , cycle_elem p2 ) {
    if ( p1.rem != p2.rem ) { return p1.rem < p2.rem ; }
    if ( p1.stval != p2.stval ) { return p1.stval < p2.stval ; }
    return p1.id <= p2.id ;
}

pair < int , ll > get_nxt ( int x , ll val ) {
    ll ret = 0 ;
    int y = x ;
    while ( cycle_id[ y ] == 0 ) {
        int hh = w.getr ( 1 , 1 , n + 1 , pos[ root[ y ] ] , pos[ y ] , val + dist_to_ori[ x ] ) ;
        if ( hh == -1 ) {
            if ( lst[ root[ y ] ] == 0 ) { y = root[ y ] ; }
            else { y = lst[ root[ y ] ] ; }
        }
        else {
            int act = rv[ hh ] ;
            return { act , lvl[ x ] - lvl[ act ] } ;
        }
    }
    ret = lvl[ x ] - lvl[ y ] ;
    if ( cycle_id[ x ] == 0 ) { 
        val += dist_to_ori[ x ] ;
    }
    int wtf = x ;
    x = y ;
    if ( x == n + 1 ) {
        return { x , ret } ;
    }
    cycle_elem sr ;
    int id = cycle_id[ x ] ;
    sr.rem = sr.stval = val - dist_to_ori[ x ] ;
    if ( abs ( cycle_len[ id ] ) > 0 ) { 
        sr.rem %= abs ( cycle_len[ id ] ) ;
        sr.rem = ( sr.rem + abs ( cycle_len[ id ] ) ) % abs ( cycle_len[ id ] ) ;
    }
    else { sr.rem = 0 ; }
    sr.id = at_pos[ x ] ;
    int l , r , mid ;
    l = 0 , r = srt[ id ].size ( ) - 1 ;
    while ( l < r ) {
        mid = ( l + r ) / 2 ;
        if ( leq ( sr , srt[ id ][ mid ] ) == true ) { r = mid ; }
        else { l = mid + 1 ; }
    }
    if ( sr.rem == srt[ id ][ l ].rem && sr.stval == srt[ id ][ l ].stval ) {
        return { cycles[ id ][ srt[ id ][ l ].id ] , ret + srt[ id ][ l ].id - at_pos[ x ] } ;
    }
    if ( cycle_len[ id ] > 0 ) {
        if ( sr.rem != srt[ id ][ l ].rem ) { return { -1 , -1 } ; }
        ll full = ( ( srt[ id ][ l ].stval - sr.stval ) / cycle_len[ id ] ) % MOD ;
        return { cycles[ id ][ srt[ id ][ l ].id ] , ret + full * cycles[ id ].size ( ) - at_pos[ x ] + srt[ id ][ l ].id } ;
    }
    int lo , hi ;
    lo = 0 , hi = srt[ id ].size ( ) - 1 ;
    cycle_elem foo = { sr.rem , sr.stval + cycle_len[ id ] , MAXN } ;
    while ( lo < hi ) {
        mid = ( lo + hi ) / 2 ;
        if ( leq ( foo , srt[ id ][ mid ] ) == true ) { hi = mid ; }
        else { lo = mid + 1 ; }
    }
    l = lo ;
    -- l ;
    if ( l < 0 ) { return { -1 , -1 } ; }
    if ( sr.rem != srt[ id ][ l ].rem ) { return { -1 , -1 } ; }
    if ( cycle_len[ id ] == 0 && sr.stval != srt[ id ][ l ].stval ) { return { -1 , -1 } ; }
    sr.stval = srt[ id ][ l ].stval ;
    sr.id = -MAXN ;
    l = 0 , r = srt[ id ].size ( ) - 1 ;
    while ( l < r ) {
        mid = ( l + r ) / 2 ;
        if ( leq ( sr , srt[ id ][ mid ] ) == true ) { r = mid ; }
        else { l = mid + 1 ; }
    }
    sr.id = at_pos[ x ] ;
    sr.stval = val - dist_to_ori[ x ] ;
    if ( cycle_len[ id ] < 0 ) {
        ll full = ( ( srt[ id ][ l ].stval - sr.stval ) / cycle_len[ id ] ) % MOD ;
        return { cycles[ id ][ srt[ id ][ l ].id ] , ret + full * cycles[ id ].size ( ) - at_pos[ x ] + srt[ id ][ l ].id } ;
    }    
    else {
        ll full = 1 ;
        return { cycles[ id ][ srt[ id ][ l ].id ] , ret + full * cycles[ id ].size ( ) - at_pos[ x ] + srt[ id ][ l ].id } ;
    }
}


void solve ( ) {
    cin >> n >> init_val ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].targ >> a[ i ].spec_add >> a[ i ].spec_move >> a[ i ].add >> a[ i ].move ;
        v[ a[ i ].move ].push_back ( i ) ;
    }
    a[ n + 1 ] = { 0 , 1 , n + 1 , 1 , n + 1 } ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n + 1 ; ++ i ) {
        if ( used[ i ] > 0 ) { continue ; }
        vector < int > hist ;
        int x = i ;
        while ( used[ x ] == 0 ) {
            hist.push_back ( x ) ;
            used[ x ] = i ;
            x = a[ x ].move ;
        }
        if ( used[ x ] != i ) { continue ; }
        ++ tp ;
        while ( 1 ) {
            cycle_id[ hist.back ( ) ] = tp ;
            cycles[ tp ].push_back ( hist.back ( ) ) ;
            if ( hist.back ( ) == x ) { break ; }
            hist.pop_back ( ) ;
        }
        reverse ( cycles[ tp ].begin ( ) , cycles[ tp ].end ( ) ) ;
        ll sm = 0 ;
        for ( auto wh : cycles[ tp ] ) {
            dist_to_ori[ wh ] = sm ;
            sm += a[ wh ].add ;
        }
        cycle_len[ tp ] = sm ;
        int act = 0 ;
        for ( auto wh : cycles[ tp ] ) {
            at_pos[ wh ] = act ;
            ll md_val = a[ wh ].targ - dist_to_ori[ wh ] ;
            ll rem = md_val ;
            if ( abs ( cycle_len[ tp ] ) > 0 )  {
                md_val %= abs ( cycle_len[ tp ] ) ;
                md_val = ( md_val + abs ( cycle_len[ tp ] ) ) % abs ( cycle_len[ tp ] ) ;
            }
            else { md_val = 0 ; }
            srt[ tp ].push_back ( { md_val , rem , act } ) ;
            ++ act ;
        }
        sort ( srt[ tp ].begin ( ) , srt[ tp ].end ( ) , cmp ) ;
        srt[ tp ].push_back ( { inf , inf , n + 2 } ) ;
    }
    for ( int i = 1 ; i <= n + 1 ; ++ i ) {
        if ( cycle_id[ i ] > 0 ) {
            dfs ( i , 0 ) ;
        }
    }
    tp = 0 ;
    for ( int i = 1 ; i <= n + 1 ; ++ i ) {
        if ( heavy[ lst[ i ] ] != i ) {
            int x = i ;
            while ( x > 0 ) {
                pos[ x ] = ++ tp ;
                rv[ tp ] = x ;
                root[ x ] = i ;
                x = heavy[ x ] ; 
            }
        }
    }
    w.init ( 1 , 1 , n + 1 ) ;
    ll steps = 0 ;
    int wh = 1 ;
    ll val = init_val ;
    while ( 1 ) {
        auto [ nxt , add ] = get_nxt ( wh , val ) ;
        if ( nxt == -1 ) {
            cout << "-1\n" ;
            return ;
        }
        steps = ( steps + add ) % MOD ;
        wh = nxt ;
        if ( wh == n + 1 ) { break ; }
        if ( seen[ wh ] == true ) {
            cout << "-1\n" ;
            return ;
        }
        seen[ wh ] = true ;
        steps = ( steps + 1 ) % MOD ;
        val = a[ wh ].targ + a[ wh ].spec_add ;
        wh = a[ wh ].spec_move ;
        if ( wh == n + 1 ) { break ; }
    }
    cout << steps << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 0
5 1 2 1 1
10 1 3 2 2

output:

9

result:

ok answer is '9'

Test #2:

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

input:

3 1
0 1 4 2 3
1 0 1 1 3
3 -2 2 1 4

output:

-1

result:

ok answer is '-1'

Test #3:

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

input:

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

output:

-1

result:

ok answer is '-1'

Test #4:

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

input:

1 0
1 -1 1 1 1

output:

-1

result:

ok answer is '-1'

Test #5:

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

input:

1 0
1 1 1 0 1

output:

-1

result:

ok answer is '-1'

Test #6:

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

input:

1 0
1 1 2 1 1

output:

2

result:

ok answer is '2'

Test #7:

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

input:

1 0
1 1 1 1 2

output:

1

result:

ok answer is '1'

Test #8:

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

input:

1 0
0 1 2 1 1

output:

1

result:

ok answer is '1'

Test #9:

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

input:

100 -4970158919
-4970158919 5298982179 58 2127388448 36
3577683288 -678612796 27 -1839381517 78
1130102347 -9570160187 38 396987663 8
4537900580 -11159167057 56 -1367861269 17
668065108 5219196271 30 169500619 6
837565727 966573433 24 -923215895 3
-5911921727 10449822307 4 -147022320 18
1527090010 2...

output:

200

result:

ok answer is '200'

Test #10:

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

input:

100 -2852072278
-2852072278 2934276490 83 1241869498 84
3907419259 -3184860712 43 -1247686974 30
6773703878 -2866284619 2 321232071 76
1496218680 1028396752 48 179797821 97
3749010409 -1987850997 89 -654803031 24
2582581755 1678924232 99 1166428654 5
-3012002159 5550440136 71 998464454 70
4907802417...

output:

148

result:

ok answer is '148'

Test #11:

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

input:

100 5715351312
5715351312 1018616088 31 -882609896 77
15087800567 -6430883422 35 -35506438 72
16269144106 -8442362024 49 -1181343539 2
6883287876 3416322404 81 1784848683 34
21345976661 -11563881414 42 -1677446207 63
10833010437 -3918244480 44 -1406678909 61
23806928673 -19177067813 28 -1025065617 5...

output:

-1

result:

ok answer is '-1'

Test #12:

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

input:

100 1408568097
194625343 2399768904 3 329613627 28
559175587 -1510465941 6 -2014228830 21
2594394247 1376119565 11 -613380861 72
-2319184378 4725916701 20 1982206572 93
1507684280 -1119064583 81 230497444 28
-951290354 457429355 33 -81996003 15
-2233386417 5195637565 82 1074959300 29
1667688090 -201...

output:

-1

result:

ok answer is '-1'

Test #13:

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

input:

100 -4601788046
-4601788046 3767647315 10 1647679515 39
-2 -3150543261 42 -1203261617 91
1303883147 -7909958852 100 -1038630694 13
-4298449676 3343796523 86 1206543585 17
-5747137655 2765497642 61 1220647494 16
-4723968408 -6431105 43 425518732 4
-8471399759 3611912732 14 617770587 69
-6318067772 45...

output:

999650207

result:

ok answer is '999650207'

Test #14:

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

input:

100 2960487318
5532744360 -7499666467 83 -1312081064 17
4254392580 1002267504 49 1972263250 86
-358247787 4174762610 62 399224357 56
-6106816731 5616707581 29 62754457 67
2173817904 -3588159749 99 1056965522 2
3998435059 -3021616774 80 1465913659 84
-8079584711 12300248007 17 1143423607 22
586385085...

output:

492104710

result:

ok answer is '492104710'

Test #15:

score: 0
Accepted
time: 4ms
memory: 22192kb

input:

100 4357304816
4357304816 -4357304816 15 1330093761 61
965261297 -2732868247 95 1247351562 97
13286102111 -2484377022 91 824473325 58
7156978042 1006269731 31 1120443891 40
9990652790 -13740338410 68 -424830173 88
16175887196 -15156706618 79 -1618543279 98
8979502044 -10327590631 47 -691036482 25
10...

output:

100

result:

ok answer is '100'

Test #16:

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

input:

100 1368477310
1368477310 6567377610 44 769941067 99
4730161814 -7061136083 74 -559832838 4
5940188635 3083028396 92 253446248 42
4170328976 5116025654 24 353859448 63
10736601820 -5545533711 80 -974570433 14
6464823843 -1077285978 84 437489618 15
-1997081490 7264295396 8 -333892779 74
5267213906 47...

output:

100

result:

ok answer is '100'

Test #17:

score: 0
Accepted
time: 6ms
memory: 24652kb

input:

100 5338254142
5338254142 -8941356754 51 -215228157 6
5727310831 -5846604192 55 -1572517523 56
1786926349 3111713539 93 -962624613 27
6925090471 -8623075001 48 -1197779640 2
-627012268 2748456092 47 -515619976 28
5123025985 -4507947157 86 -513789580 38
595232967 -2079172617 75 1583255021 42
91094909...

output:

222066793

result:

ok answer is '222066793'

Test #18:

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

input:

100 -7179752042
-3428314737 -4230458910 97 845623086 2
-4539975511 4753140184 54 362683136 61
1695924068 -1002913390203 44 -1203258607 52
1530332468 -12325950485 20 -774476218 42
-12508109969 4412373901 75 1382850114 78
4277201929 -7779637052 24 -821393056 62
2972041195 -15165036555 48 -963807588 59...

output:

693411989

result:

ok answer is '693411989'

Test #19:

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

input:

100 7601566340
7601566340 -3650319787 11 798017807 87
9463779364 -699219176 28 1735153239 60
10694758115 278613487 39 -1873339403 51
6957301446 -4610234246 6 1781965238 99
3137250952 -4345807141 61 -905345122 94
2347067200 -7202268696 33 1589503439 72
4655718973 -8519622083 42 147790217 32
354054119...

output:

-1

result:

ok answer is '-1'

Test #20:

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

input:

100 4656991716
13245124902 4488433255 54 2099910504 35
13650499806 -16042231140 28 -316315528 3
3167161106 -1303812373 79 -920531869 25
7330318891 2309077348 49 -20239115 74
-2531879896 601396889 48 603812762 11
-247465036 13581649314 3 2066712488 21
-1851169803 2764245292 72 269124550 97
-174632735...

output:

-1

result:

ok answer is '-1'

Test #21:

score: 0
Accepted
time: 4ms
memory: 24548kb

input:

100 -1138240537
-1138240537 1512208636 54 1512208636 54
3295148712 3657831565 79 1361265243 99
3188732845 5710037238 52 -172771352 34
5964817499 -9745424287 75 1482997760 39
3929405151 5738323470 89 -564921263 50
5437127218 1870604445 40 1515853059 79
-4538394567 5785787928 53 635079438 22
268606059...

output:

-1

result:

ok answer is '-1'

Test #22:

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

input:

100 2609000993
2609000993 3209478665 38 2237407040 31
8575147806 -8575147806 73 573613177 47
2309125927 5809926574 61 1420566269 99
4208848765 -2232492973 90 -1246117056 39
6047166920 1700893701 75 -805986139 97
3062084837 -1222908931 76 -847290523 27
8712413705 -2834761736 51 -964353084 75
66352892...

output:

-1

result:

ok answer is '-1'

Test #23:

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

input:

100 -1013931699
-1013931699 -259693814 80 -1838784513 11
-6973455380 3015932761 51 -754486408 77
-4649893117 1980494684 52 277294013 20
-8477087169 8018050973 53 163822792 63
-6546389997 1052190197 74 -841112393 15
-1830678606 -1223127997 54 -1000738182 71
-9833604746 3792417573 98 -801148119 37
-22...

output:

-1

result:

ok answer is '-1'

Test #24:

score: 0
Accepted
time: 4ms
memory: 23856kb

input:

100 1571736460
2442116737 -6187582238 99 -2002201191 52
6104150454 -7841440623 92 26077219 34
3424294140 -2984378594 52 144263866 70
4920621959 -3961018021 8 -684848866 68
1330160279 4128863390 13 -116200584 51
3581147606 -5811487625 37 -2055272205 20
-7553882465 7331454337 58 -128539378 23
-8746356...

output:

-1

result:

ok answer is '-1'

Test #25:

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

input:

100 -3629900833
-3629900833 -2343767479 89 1151795679 32
2392146176 -2725249025 27 -995092644 9
-4380803093 2909701457 41 -1400091481 71
-3641953344 -3049359529 62 213707561 81
-6233612294 515403941 87 259943982 89
-3804158458 -4214927376 85 -998978568 96
-5142634084 -103114060 56 1859263505 93
-491...

output:

-1

result:

ok answer is '-1'

Test #26:

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

input:

100 9724843963
11091074245 -11119583138 12 -1713581181 25
-362931921 4902315220 81 334423028 12
2078130825 4679930825 16 -1374882778 87
1600815534 2398984812 44 -976060587 39
6375029966 -82065552 66 -82065552 66
-327634667 999316764426 30 1621438753 57
3244637583 -1667070583 50 1290433968 92
3548165...

output:

-1

result:

ok answer is '-1'

Test #27:

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

input:

100 -4603855697
-4603855697 -3185155475 23 842644070 63
-7513339849 8925622289 22 447920008 73
-4590933374 2669681596 29 -901291759 75
-3534864071 6786247845 31 -1680529067 50
-5438157885 1676946258 63 -342548429 77
-6621419659 4970959871 58 726985218 85
-492102339 -3567185106 21 -655449980 97
-1681...

output:

-1

result:

ok answer is '-1'

Test #28:

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

input:

100 -2651860637
-2651860637 1934743454 30 -472587328 28
-7597064217 4954863065 59 578139592 63
-3836474755 2808493495 35 725661215 90
-7649155776 7442178715 13 1931453733 16
-5084450765 1694540003 33 -433004585 72
-1754509433 -1369938532 28 -59398603 54
-4396280173 -1091647675 20 191216541 45
-41547...

output:

-1

result:

ok answer is '-1'

Test #29:

score: 0
Accepted
time: 6ms
memory: 24844kb

input:

100 7920949729
7920949729 -3200580819 87 1232520838 44
1661885138 -1651647153 23 -578650650 28
556804489 3362080829 60 -1339853204 48
-263030299 8611852811 56 1272316104 88
2033908507 -1985817947 53 1473215122 91
6228715654 -2922838734 47 1104320801 26
2615698921 5583496909 40 -1273530994 24
-391946...

output:

-1

result:

ok answer is '-1'

Test #30:

score: 0
Accepted
time: 6ms
memory: 25176kb

input:

100 -2765512123
-2135049280 13089895836 7 792925646 85
-5996796268 8817629718 63 -608386612 97
-8867847700 15914978304 43 16718603 23
-12951964679 -1450551450 64 -1450551450 64
11731973285 -17687108386 15 -1792143731 57
-16010014792 23252724050 50 28632158 40
16852813550 -16680005301 61 1798734182 1...

output:

-1

result:

ok answer is '-1'

Test #31:

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

input:

999 4269140604
4269140604 4569327974 377 -518650394 141
4318498883 1205053284 26 1434903404 567
-48702122 696469216 61 -1966997478 938
5040791809 2921073181 752 -1584955445 71
1387602775 5394620143 377 -48475329 333
2882747991 -10603881233 399 -1504391262 621
1745806981 1577594329 61 1877093438 500
...

output:

853588

result:

ok answer is '853588'

Test #32:

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

input:

999 1001586697073
29610727392 -25867171735 831 -357919231 701
0 5273370334 184 -848098426 424
1 -2127538228 865 278666897 501
2651099588 788341640728 871 -923565978 269
-827407447492 828377440717 857 -716867312 632
-433225669 -1802414795 649 757020215 705
3389121423 -2433045873 541 -1698565188 873
1...

output:

-1

result:

ok answer is '-1'

Test #33:

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

input:

999 -1000000000000
2 -999993695458 248 2 1
-6204883924 1005182086000 768 4 2
560782053 -1000484928216 756 43187453 3
0 -999745347396 338 -3 4
-201960247218 -797856412048 947 -693288368 5
2 -999540349117 739 8 6
-173095170 -999188776704 49 537852213 7
1998674752 998001325245 436 -698174846 8
0 999996...

output:

-1

result:

ok answer is '-1'

Test #34:

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

input:

999 244924636
244924636 462665972 917 -182203760 134
-3362443 999644363524 294 -279992529 59
-981922548 1001409706273 843 1888954082 972
7425238280 -6622138956 703 -1401922058 34
-1924892096 3728110615 145 1264821907 5
-676492401 -1000087283363 565 -2233521055 768
18228766509 2278114610 726 13056688...

output:

-1

result:

ok answer is '-1'

Test #35:

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

input:

999 -3419602666
-3419602666 -580330439 497 -343302480 815
-14099689425 11945780901 633 -1312015984 630
1313230229 -335356786 573 1682748342 200
-1444378399 -3149963850 694 -837095639 349
-2512838179 3404513844 45 -2044641147 414
-1495706482 14807003 515 380468802 928
-2942068259 2800916335 43 -45556...

output:

-1

result:

ok answer is '-1'

Test #36:

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

input:

999 1165755724
1165755724 -4533045546 454 139790741 391
-3305052183 -55772354 580 1017057940 271
1918449535 184303764260 698 652956528 450
-2208781234 -7430790641 273 201571270 721
2967078221 -5132419144 248 -1346660115 131
433478501 -1001992497478 455 1286632833 252
-2438249028 1179792636 184 19295...

output:

538708686

result:

ok answer is '538708686'

Test #37:

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

input:

999 1000000000000
2 -998692588450 414 -2 1
2244025826 996490535474 570 -4 2
-843765389 -999109375170 873 3 3
1778203552 997788757535 423 477820052 4
426413361 -998787495897 312 798105929 5
1406629838 998296009959 267 156854559 6
0 -1001597998275 751 0 7
0 0 521 0 8
0 0 900 0 9
-723881368 -9978078806...

output:

456831317

result:

ok answer is '456831317'

Test #38:

score: 0
Accepted
time: 4ms
memory: 24940kb

input:

999 -999985501009
1247668617 -4633987044 30 54958457 1
3 999999999994 657 5 2
640161189 1000187834899 490 -163752928 3
699173666927 -697462029045 965 1274301888 4
-1711486735 2228643317 23 1466650456 778
2341407241 996963031122 194 -715676578 848
-1788019491 -998103470603 738 -205079323 460
-3410782...

output:

-1

result:

ok answer is '-1'

Test #39:

score: 0
Accepted
time: 6ms
memory: 25348kb

input:

999 3534741360
3534741360 -1755699046 825 -1048404666 273
4752902668 -429304825 733 -1442455625 273
3759493451 -1792602774 466 -1273156757 273
4163298909 -38094686 789 -852851866 273
3134046926 742308684 988 -647710232 273
665866769 1401345751 797 1820469925 273
1241134748 -97961896 463 2069312295 2...

output:

-1

result:

ok answer is '-1'

Test #40:

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

input:

999 997495139021
-2938940592 4675983869 531 1873842295 598
1360959107 -758797048991 851 1913175060 18
-1641385059 1653291862 1 427751530 695
175774857 -1672428018 740 -811598431 63
1862762693 639274399 878 -1443330241 703
-5072651134 8895157436 414 -708407019 273
-3248534433 -681443748099 368 100046...

output:

-1

result:

ok answer is '-1'

Test #41:

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

input:

999 -999999999994
-4 4 872 10 1
-5260885389 1005260885387 654 10 2
-507339510 1000507339506 678 -1731943565 3
-147591126 999620713300 236 -177376230 4
42423639160 -1041949348572 88 -1575030957 5
691855901922 -1689939471126 212 -720952982 6
-767201702 767201702 612 1814664162 7
-1480478202 -998298597...

output:

-1

result:

ok answer is '-1'

Test #42:

score: 0
Accepted
time: 10ms
memory: 23840kb

input:

999 -404368442
-404368442 1000404368436 904 -1158878717 973
-820153286 -999041282401 193 820153283 470
-1189807499 1189807499 356 -671857358 3
-458734922 -1220129883 534 2110778041 4
267815510 -1001317726853 525 -60216335 5
1022922626 -1000089519433 150 -159702446 717
0 -998466632068 1 0 7
0 1000000...

output:

229829037

result:

ok answer is '229829037'

Test #43:

score: 0
Accepted
time: 6ms
memory: 25108kb

input:

999 -6884634540
11147779797 -15341087423 998 2039276400 172
-4015550540 27108473335 93 -1316199136 336
12273279997 -4968538610 781 1159536841 840
-3956698988 4297362895 278 -202796451 71
-2793854958 -14929189764 277 633300444 949
-1151458246 12532250890 583 -1092305935 340
997071861 -21049975691 132...

output:

-1

result:

ok answer is '-1'

Test #44:

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

input:

999 -998783206922
1320766454 -1220803988 916 1698188800 577
-6106607514 15255702890 555 -1624463141 619
-4604170280 13079031234 796 -831083967 694
6342742707 -4791253554 760 -397868029 420
1981642084 -1377093195 375 -1572981138 102
-932250553 7939097235 603 -1810622493 208
0 -3431971004 141 -5105724...

output:

-1

result:

ok answer is '-1'

Test #45:

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

input:

999 -998535996465
-1129735741 -998152874776 740 1627090148 1
2105735256 -2105735253 94 -609855556 2
3892028 -1000003892025 894 195777322 3
0 999999999999 160 0 4
6736527711 -1005680653113 919 9 5
1 999857861342 913 5 6
372205924240 -1371724595452 707 -1858835102 7
-2065340126 -997934659873 822 14135...

output:

-1

result:

ok answer is '-1'

Test #46:

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

input:

999 -1000127635725
1130363025 -1001088181636 118 247792459 977
-768453601 768453601 654 1545713626 911
0 999897277090 104 0 3
173697848 -998847490319 256 424206724 678
11568373366 -1011565758221 846 1418837717 127
-688616679 999420075422 900 -824509249 6
-563424035 396914632 334 -1901116432 7
291146...

output:

373841134

result:

ok answer is '373841134'

Test #47:

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

input:

999 609775441
3443209709 -2207793634 270 -324331758 885
-3540466056 8436163487 173 1014092373 380
-1995775933 1002949114980 680 1800764070 16
-3216982497 3313322279 364 -2129937059 583
-1975302783 -1588776658 446 59954298 310
-976423951 1507203749 521 -534903075 248
2 -997098980036 1 1371864811 390
...

output:

-1

result:

ok answer is '-1'

Test #48:

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

input:

999 2084678870
2084678870 -2475567453 925 -1031328701 857
4011343003 -1004073378694 197 1571763835 535
-247880079815 250972656664 113 -245541812 732
3366887171 -4790023703 353 -524127522 240
1409149999 -1513233865 614 -1409150003 840
4451119926 -6959911694 613 -1107049677 846
-3005805528 3480673910 ...

output:

-1

result:

ok answer is '-1'

Test #49:

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

input:

999 -999867346095
1056356294 998244292750 492 225484051 1
19563201446 980165003029 299 -10 2
-1863027856 1863027856 371 -1462414576 3
1568511339 998257273357 742 1104131123 4
51577063820 -1049795097544 433 -1781648448 5
1935019119 997416349260 44 839488151 6
-1809127618 -997129790676 814 2095592056 ...

output:

433388726

result:

ok answer is '433388726'

Test #50:

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

input:

999 -1149656453
-1149656453 1003519580176 994 -433054904 458
-287074912 -999559279219 403 1806418515 27
7347778349 993311669763 891 -436857772 990
913748898 -660910422 980 -1743197181 213
1165088296 -1001724609208 997 -1592125007 714
245265234 -5648944938 948 251192447 237
17782431 -1095856657 382 1...

output:

-1

result:

ok answer is '-1'

Test #51:

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

input:

100000 122378264123
122378264123 -234095710308 69489 -1529435292 22740
103392560231 -22159078497 90497 -1599604352 81287
65821004982 -62554772207 87001 -655783598 99511
149727429736 -308254536677 2969 306742596 66936
192097289376 25439097757 35173 -1743584674 86845
129253867365 -70080057011 13905 -1...

output:

-1

result:

ok answer is '-1'

Test #52:

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

input:

99999 -168369825181
-168369825177 171391488738 67468 -1498357056 3850
-95761873910 34744723059 7264 890829873 42677
-36450407232 61420123036 48673 904745946 56836
-21342352038 -7325996857 13630 378468103 87036
1747743035 54471099385 9516 -566291537 2582
35000368144 4198872323 89635 358793317 49445
-...

output:

-1

result:

ok answer is '-1'

Test #53:

score: 0
Accepted
time: 172ms
memory: 55844kb

input:

99999 -6833505143
-2122673849 -998180268212 35457 820539683 91825
855329473 -2037023775 59181 -1090650787 80369
-167879347 927049030 11840 1297271840 73354
4479219139 -7299786134 95670 852263131 98362
-1045985289 2271790489 25178 -1048538497 48418
-2869324543 576567649 13783 1122004061 9976
64231167...

output:

-1

result:

ok answer is '-1'

Test #54:

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

input:

100000 74946810075
74946810075 31898313753 68955 593055650 6075
81976297809 -71779693729 91762 941677965 8166
1712393218 33028984712 42903 1389476200 62104
43345358270 -11256157505 99482 -1339188203 55399
178899246768 -130173977273 60556 587420478 92732
10768336393 5403293426 25247 2012221551 77548
...

output:

-1

result:

ok answer is '-1'

Test #55:

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

input:

99999 698648290
698648290 -1431283056 67376 16600230 70490
-26845637861 28306653193 41706 -406258936 35292
19821469862 15813180443 99733 281657509 17629
19823317351 -54041723189 41145 -291051650 74111
-161236925192 55638763336 77397 -103544320 40375
94347345146 -163230591069 45687 1649786892 4320
-3...

output:

672902427

result:

ok answer is '672902427'

Test #56:

score: 0
Accepted
time: 170ms
memory: 55884kb

input:

99999 -999803865924
1469148752 -1469148752 92860 241386937 1
505652935 3077671007 70362 219871333 36022
-1162123588 -889223798 97187 681943466 75651
-598837084512 598837084512 42122 -440232742 30983
-3774541576 3231940354 15219 995710763 35364
73344520359 -1072722473973 31641 -1843323358 82026
88233...

output:

-1

result:

ok answer is '-1'

Test #57:

score: 0
Accepted
time: 162ms
memory: 51520kb

input:

99999 3268920978
3268920978 -9467351038 59947 -502608011 25563
8118785030 -6911262618 81085 2136000562 2426
-2576029086 14452024992 88166 247546469 58496
-6499720290 -246041691 98848 1346384904 2650
-484736754 -840141635 39900 1296416575 10230
3259280657 -6256059856 57570 -326360944 66506
3879362799...

output:

-1

result:

ok answer is '-1'

Test #58:

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

input:

99999 1398856203
1398856203 710621231 975 -1186423344 62309
15166869077 -15922239375 73703 1669633897 67733
2129598798 -1341976064 28136 -1917165939 62309
14080115147 -13926701243 67742 1765113705 34429
23691323458 -23251375050 75453 -1242724077 50201
2607355443 -1197460877 52452 928481664 62309
544...

output:

-1

result:

ok answer is '-1'

Test #59:

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

input:

99999 999999999999
18488825839 -20033249314 22660 -10 1
-5969295364 5533225176 86808 -99818124 62281
-3860415237 -995291638274 43044 1859260142 28604
-3187685079 -998485087937 27693 1959959374 20931
1800482120 998774406691 66945 1168063355 29073
-681641597 -1001037195841 49090 -988663283 6
232320244...

output:

-1

result:

ok answer is '-1'

Test #60:

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

input:

100000 1706094309
1706094309 -124398410323 68685 844409912 77865
-28305060560 -48178042919 79162 801711092 84047
-116637158471 -29655222805 18120 1721391280 77965
-99580078993 131727378068 85915 -451885234 46712
-42214163295 20599641872 92106 -1257957682 74548
-63465976353 -6803516484 52893 -1963424...

output:

200078738

result:

ok answer is '200078738'

Test #61:

score: 0
Accepted
time: 178ms
memory: 51348kb

input:

99999 -4631864587
-4631864587 8379760408 5746 188703891 7082
1714037297 5005776017 56038 -375909420 52888
-5824638099 11319521782 11757 1707234936 79503
-311981801 -1669314127 16082 1811094675 77443
1340303246 -2496994190 66502 -142267936 50138
1653074481 11747143461 73400 414816353 81795
-411413931...

output:

208259

result:

ok answer is '208259'

Test #62:

score: 0
Accepted
time: 177ms
memory: 58212kb

input:

99999 5742454426
5742454426 -1005742454424 48025 -1989147919 77510
-7111785411 11830297621 81021 -857873958 89475
796758619 996957075863 75910 -783985768 67573
3519540335 -962049238 98508 -2118390546 81364
856039964 996188884977 23073 -1022685265 62154
-548721709 -1000139186250 40165 1374751369 6
-2...

output:

-1

result:

ok answer is '-1'

Test #63:

score: 0
Accepted
time: 576ms
memory: 61484kb

input:

100000 -47936332513
-48475995394 -371650401046 67431 -2074309436 77796
-491059169060 442669411968 1 1183367014 7201
-295517141193 247638465863 1 737397530 70669
-142301797420 -340963247209 41710 1176429277 94214
-374808358121 149336753284 38552 386647560 98850
-194430461026 144647134098 1 -668583393...

output:

753928488

result:

ok answer is '753928488'

Test #64:

score: 0
Accepted
time: 584ms
memory: 60444kb

input:

100000 479531862398
479360638978 94578047203 99123 2013228262 25392
313462679220 -197059746392 45660 1669345780 94090
196245982113 -82651945394 45660 476020015 47882
470427966591 128449423894 89989 -659423203 87513
110092281819 4131090741 45660 -2040972199 81846
-6939822157 123763378588 45660 149268...

output:

754021976

result:

ok answer is '754021976'

Test #65:

score: 0
Accepted
time: 585ms
memory: 61628kb

input:

100000 5103410072
1252315857 -20756607765 85732 -1854854534 35251
60639762823 -82227204460 85732 -1664094286 69508
138379787835 -154783628875 65379 1460575162 22776
22728123989 -42814112235 85732 1164951383 33274
95696251913 -116749513593 85732 -421569644 60707
-168752268776 147382962848 85732 11443...

output:

765825524

result:

ok answer is '765825524'

Test #66:

score: 0
Accepted
time: 570ms
memory: 61516kb

input:

100000 -403082395922
-402589052532 -692231224 1 1211623396 21744
-120154964503 -20245627310 55006 -301585728 46829
-136654234391 -74054042845 40802 1646628139 20989
-40574035490 -362990769855 1 1467191314 17591
-174460565101 -228063701643 1 -1998739242 30721
-238118098769 -197240367497 54294 6066681...

output:

-1

result:

ok answer is '-1'

Test #67:

score: 0
Accepted
time: 569ms
memory: 61036kb

input:

100000 -409855387975
-410965772798 149847600 1 2041783677 97090
48879026999 -458893064030 1 -1440797049 13764
-176451087473 -232124395143 1 -1005030479 18655
-360336200608 -50727308628 1 -1214291194 6189
-70376901005 -366739831203 38350 -577383637 74951
-162766205118 -129455939496 7865 -1589623416 8...

output:

-1

result:

ok answer is '-1'

Test #68:

score: 0
Accepted
time: 581ms
memory: 61324kb

input:

100000 -410186426972
-411387983976 101437559102 40171 -252180650 21786
-23890507330 -241129843297 26275 1570045758 63934
-244816830601 -65970928340 40171 -575160233 68416
-178476740689 -131295775002 40171 116226414 31523
-286088858449 -26502270377 40171 -193988853 1442
-458559862364 147727670136 401...

output:

-1

result:

ok answer is '-1'

Test #69:

score: 0
Accepted
time: 176ms
memory: 55968kb

input:

100000 -24669357611
-24074691238 20616801531 11058 1614204437 64132
-14413565725 97096763079 84246 576478970 24236
73716751271 -128206240495 72248 -1078823183 24263
-127062680474 76606640344 12741 -1826286535 13424
-62586054138 47580894118 17659 1179230076 76454
-8236051603 -43328800964 32707 162266...

output:

144939170

result:

ok answer is '144939170'

Test #70:

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

input:

100000 72866030024
72866030033 173322251 24611 -1863215046 16794
132778229229 -12854484746 68753 -1379297153 19917
-29156009130 148588474859 29757 -1051714780 14895
-81329694303 320464434479 8779 -1487109176 52689
230309737915 -227567831063 2384 583951751 41918
-233453862116 417525946991 21799 -3765...

output:

300699910

result:

ok answer is '300699910'

Test #71:

score: 0
Accepted
time: 163ms
memory: 55336kb

input:

100000 17845321636
11527210039 -69605576779 26791 -1951195181 50956
-157919413445 175036632775 19151 1983822085 36652
-3054831932 16908762882 88475 2145484323 5862
7871077021 -102868254318 50387 1609916042 29726
-114546450813 122045185661 64356 -1077844428 39408
17563577436 -45244612684 86116 -82707...

output:

766427834

result:

ok answer is '766427834'

Test #72:

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

input:

100000 -7067647484
5831667574 992661548838 1 122384118 92939
-124601941722 1123095158133 1 -1808163736 58652
31545762389 966947454022 1 -2006088529 81470
-208835618393 1207328834804 1 728560734 7092
-175034960118 176846010230 1 -1057498385 75698
16097749306 982395467104 1 -1490509865 90294
101163463...

output:

-1

result:

ok answer is '-1'

Test #73:

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

input:

1000 -7844040959
-10359736676 6467263985 483 1088887179 624
-9987561191 9221351197 395 -1767761168 537
-1699940753 -4672952298 73 -1716251181 944
15687654296 -19448988085 798 -1787959616 721
7308571467 6556356198 797 -1575933526 571
-11143335221 17331995103 72 2002964327 177
17130300526 -27840633361...

output:

-1

result:

ok answer is '-1'