QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90009#1212. Navigationyouwike100 ✓44ms7640kbC++14676b2023-03-21 22:20:052023-03-21 22:20:06

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 40ms
memory: 7564kb

input:

100000 94560 16294 1
91913 94560
94560 69503
94560 39684
47595 94560
94560 96623
8011 94560
94560 15498
94560 92403
94560 84183
94560 44035
39994 94560
82975 94560
94560 30698
94560 17596
93175 94560
12253 94560
94560 60807
94560 16111
35848 94560
94560 19061
94560 25435
64721 94560
94560 79086
9548...

output:

1 94560 0 99999
91913 69503 39684 47595 96623 8011 15498 92403 84183 44035 39994 82975 30698 17596 93175 12253 60807 16111 35848 19061 25435 64721 79086 95487 98059 93865 84074 47584 77418 15271 82666 57858 21726 62847 90603 40247 64714 59668 13698 15586 58276 57618 20231 16177 77966 44363 69669 679...

input:

1 94560 0 99999
91913 69503 39684 47595 96623 8011 15498 92403 84183 44035 39994 82975 30698 17596 93175 12253 60807 16111 35848 19061 25435 64721 79086 95487 98059 93865 84074 47584 77418 15271 82666 57858 21726 62847 90603 40247 64714 59668 13698 15586 58276 57618 20231 16177 77966 44363 69669 679...

output:

16294

result:

ok 

Test #2:

score: 10
Accepted
time: 8ms
memory: 5868kb

input:

100000 48333 48333 1
927 22305
87188 22305
22305 75567
22305 9347
22305 35901
84454 22305
22305 5403
95165 22305
22305 24449
22305 69669
67307 22305
22305 58710
22305 27193
22305 24006
22305 8159
22305 54726
22305 92239
22305 68605
10968 22305
98683 22305
22305 53333
56288 22305
22305 68487
22305 24...

output:

1 48333 0 1
22305 
1 

input:

1 48333 0 1
22305 
1 

output:

48333

result:

ok 

Test #3:

score: 10
Accepted
time: 8ms
memory: 6056kb

input:

100000 88397 36060 1
36060 49481
36060 89888
46104 36060
36060 6545
36060 10332
91103 36060
99366 36060
36060 91493
28482 36060
36060 50154
61776 36060
36060 86147
36060 26865
36060 59538
3007 36060
45932 36060
87940 36060
27557 36060
84830 36060
99039 36060
36060 56978
36060 67947
45731 36060
36060...

output:

1 88397 0 1
36060 
0 

input:

1 88397 0 1
36060 
0 

output:

36060

result:

ok 

Test #4:

score: 10
Accepted
time: 24ms
memory: 7484kb

input:

100000 38698 38698 1
37846 38698
38698 89559
78769 38698
38698 89020
7513 38698
38698 32101
38698 29025
12438 38698
18470 38698
38698 90109
38698 30769
38698 39527
10263 38698
65118 38698
38698 22415
64062 38698
97159 38698
69847 38698
39786 38698
51210 38698
43668 38698
36191 38698
38698 56728
3869...

output:

1 38698 0 99999
37846 89559 78769 89020 7513 32101 29025 12438 18470 90109 30769 39527 10263 65118 22415 64062 97159 69847 39786 51210 43668 36191 56728 64359 44538 82307 93616 84397 75820 2706 10140 87937 22018 42078 40298 19458 74608 59490 1552 75615 96884 9114 93872 4401 32423 44319 51612 90701 9...

input:

1 38698 0 99999
37846 89559 78769 89020 7513 32101 29025 12438 18470 90109 30769 39527 10263 65118 22415 64062 97159 69847 39786 51210 43668 36191 56728 64359 44538 82307 93616 84397 75820 2706 10140 87937 22018 42078 40298 19458 74608 59490 1552 75615 96884 9114 93872 4401 32423 44319 51612 90701 9...

output:

38698

result:

ok 

Test #5:

score: 10
Accepted
time: 2ms
memory: 6076kb

input:

100000 8245 84923 1
67623 27621
14268 21660
76847 23001
8526 89835
60294 27885
97998 3107
41202 81214
89046 77360
59880 37584
257 27165
98520 84969
86067 72018
56406 64542
8276 24019
2025 20508
41774 84036
98730 17060
95258 43701
9237 70504
60680 4981
37431 88381
35493 76263
67579 96557
38708 14317
...

output:

1 8245 1 1
84923 
0 

input:

1 8245 1 1
84923 
0 

output:

84923

result:

ok 

Test #6:

score: 10
Accepted
time: 6ms
memory: 6056kb

input:

100000 30244 30244 1
73878 14577
56095 37561
47600 77453
5775 66825
58458 94915
99798 36060
47365 16824
9669 42255
33430 40025
41498 48308
18806 35743
41949 2837
90413 81335
23192 16889
45568 74622
4612 60078
69326 26499
28615 69807
86447 94951
28921 39587
92130 49914
84613 67964
64759 79721
1311 61...

output:

1 30244 0 2
40964 19929 
0 1 

input:

1 30244 0 2
40964 19929 
0 1 

output:

30244

result:

ok 

Test #7:

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

input:

100000 96539 83473 1
70154 43134
32826 38352
57782 12788
92705 47501
35880 88824
40402 10256
10743 19914
43415 24282
51931 26190
22666 11483
99042 17829
96021 53017
54819 93863
51864 66957
87319 62434
6849 62344
78818 23795
96092 34357
94603 43233
12795 54707
98761 8205
77768 51553
32961 14830
5637 ...

output:

1 96539 0 2
83473 27443 
0 1 

input:

1 96539 0 2
83473 27443 
0 1 

output:

83473

result:

ok 

Test #8:

score: 10
Accepted
time: 8ms
memory: 5904kb

input:

100000 52817 52817 1
45829 28937
87621 46779
27742 44527
29132 94788
34866 83250
10067 22616
59505 47012
96094 630
61678 67600
71656 43018
34904 61814
76991 78179
94102 12730
40366 90348
7717 42472
68347 67300
14803 29352
26557 92986
20554 25074
36744 72498
39260 58715
67267 83312
35596 27056
93664 ...

output:

1 52817 0 1
115 
1 

input:

1 52817 0 1
115 
1 

output:

52817

result:

ok 

Test #9:

score: 10
Accepted
time: 6ms
memory: 5952kb

input:

100000 14195 67017 1
23788 47378
57548 95872
97584 25942
19288 20314
42260 30765
82001 68266
13774 72423
74387 24887
97 22922
15715 60006
90877 24174
89741 84096
73666 89510
16870 8055
39058 61116
15682 37838
84083 621
97991 8584
31526 9971
46740 96764
77084 70018
24790 67667
59099 77893
24595 18088...

output:

1 14195 0 1
57259 
1 

input:

1 14195 0 1
57259 
1 

output:

57259

result:

ok 

Test #10:

score: 10
Accepted
time: 8ms
memory: 6076kb

input:

100000 15020 75552 1
70212 19873
39566 51824
72068 30734
50469 52341
45274 22005
90199 3889
1305 93887
96152 44487
15814 30459
52217 65619
29437 28937
28822 60432
27605 9636
524 23527
32956 39952
54216 21069
89870 31269
60600 27898
5414 73324
63840 15129
68618 55508
43871 27794
45462 2089
22374 1384...

output:

1 15020 0 2
40787 12325 
1 1 

input:

1 15020 0 2
40787 12325 
1 1 

output:

40787

result:

ok 

Test #11:

score: 10
Accepted
time: 6ms
memory: 5920kb

input:

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

output:

1 2 1 1
5 
0 

input:

1 2 1 1
5 
0 

output:

5

result:

ok 

Test #12:

score: 10
Accepted
time: 2ms
memory: 6004kb

input:

100000 58067 15674 1
45725 64183
5112 87153
28531 75803
48435 53630
61953 75534
79055 50510
20726 41197
91397 92746
20005 71460
98204 69227
83560 88464
17860 67373
72068 35569
97241 18507
34920 71359
48876 67590
39953 65012
84674 8583
98702 53186
19391 62209
57431 16010
60098 46021
60100 18974
97335...

output:

1 58067 0 2
89366 28752 
1 1 

input:

1 58067 0 2
89366 28752 
1 1 

output:

89366

result:

ok 

Test #13:

score: 10
Accepted
time: 2ms
memory: 5908kb

input:

100000 33281 11995 1
58672 48908
38754 14558
64582 60186
43413 61411
77625 73219
45168 68139
3177 6625
17478 56482
55459 13182
90092 28171
10030 53095
48280 36296
74392 91035
36886 95781
14685 9181
10482 68116
18181 62605
3072 47176
57688 75503
92342 44915
71384 17845
48150 80905
95302 13169
72420 7...

output:

1 33281 1 2
30431 93535 
1 1 

input:

1 33281 1 2
30431 93535 
1 1 

output:

30431

result:

ok 

Test #14:

score: 10
Accepted
time: 2ms
memory: 6068kb

input:

100000 23253 50284 1
33036 8532
16987 23157
24725 11750
82213 25644
19245 26175
33859 72475
84407 19947
54564 86881
9302 71494
54009 18493
13106 61118
57915 16567
43573 81856
69334 73709
92627 10167
45965 79107
39970 26375
29530 62766
31976 46163
79866 68397
18112 264
40637 12599
62736 21658
60811 2...

output:

1 23253 0 1
72220 
1 

input:

1 23253 0 1
72220 
1 

output:

72220

result:

ok 

Test #15:

score: 10
Accepted
time: 2ms
memory: 6060kb

input:

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

output:

1 2 1 1
5 
0 

input:

1 2 1 1
5 
0 

output:

5

result:

ok 

Test #16:

score: 10
Accepted
time: 6ms
memory: 5868kb

input:

100000 36431 60397 1
17885 95203
62729 35705
17294 50767
52699 82966
52217 24958
82268 43809
51951 88691
3904 35519
47307 51267
69107 53308
96124 58039
480 16881
55918 23129
14004 75060
6440 82509
7484 36128
79431 30923
73398 4082
95871 70336
65848 45640
49823 95127
76767 60115
55027 31892
19212 101...

output:

1 36431 0 5
24830 16000 85236 56668 9570 
1 1 0 1 1 

input:

1 36431 0 5
24830 16000 85236 56668 9570 
1 1 0 1 1 

output:

56668

result:

ok 

Test #17:

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

input:

100000 26991 25105 1
58880 63047
77935 8208
42959 23874
5121 162
30393 86480
78919 38651
15722 8497
6062 2695
11535 61738
14477 16623
30718 50568
71363 57805
79766 92541
10360 58480
9400 89934
85167 59557
24898 24876
20432 3759
53940 92777
48098 72434
90917 40502
21115 66931
80982 1561
27599 41918
6...

output:

1 26991 1 7
983 90216 7275 87818 17497 31675 83454 
0 1 0 0 0 1 1 

input:

1 26991 1 7
983 90216 7275 87818 17497 31675 83454 
0 1 0 0 0 1 1 

output:

87818

result:

ok 

Test #18:

score: 10
Accepted
time: 2ms
memory: 6056kb

input:

100000 55178 17512 1
56702 62074
68613 42359
56090 39239
57168 29611
272 92025
97759 40414
36943 99724
68466 21366
92995 53699
94219 47642
38376 45625
88060 92007
49559 67247
51449 35521
19174 9476
29935 7655
31613 82776
98618 18916
53659 38484
64359 38434
58797 62692
31652 86882
98669 35675
34567 4...

output:

1 55178 1 4
18334 73508 552 39167 
0 0 0 0 

input:

1 55178 1 4
18334 73508 552 39167 
0 0 0 0 

output:

73508

result:

ok 

Test #19:

score: 10
Accepted
time: 4ms
memory: 5928kb

input:

2 2 2 1
2 1

output:

1 2 0 1
1 
1 

input:

1 2 0 1
1 
1 

output:

2

result:

ok 

Test #20:

score: 10
Accepted
time: 6ms
memory: 5928kb

input:

2 1 1 1
2 1

output:

1 1 0 1
2 
0 

input:

1 1 0 1
2 
0 

output:

1

result:

ok 

Test #21:

score: 10
Accepted
time: 2ms
memory: 5964kb

input:

3 1 1 1
3 1
1 2

output:

1 1 0 2
3 2 
0 0 

input:

1 1 0 2
3 2 
0 0 

output:

1

result:

ok 

Test #22:

score: 10
Accepted
time: 6ms
memory: 6020kb

input:

3 1 3 1
2 3
1 2

output:

1 1 0 1
2 
1 

input:

1 1 0 1
2 
1 

output:

2

result:

ok 

Test #23:

score: 10
Accepted
time: 6ms
memory: 5928kb

input:

3 3 3 1
3 1
1 2

output:

1 3 0 1
1 
1 

input:

1 3 0 1
1 
1 

output:

3

result:

ok 

Test #24:

score: 10
Accepted
time: 2ms
memory: 5968kb

input:

3 1 3 1
1 2
3 2

output:

1 1 0 1
2 
1 

input:

1 1 0 1
2 
1 

output:

2

result:

ok 

Test #25:

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

input:

3 1 1 1
3 2
3 1

output:

1 1 0 1
3 
0 

input:

1 1 0 1
3 
0 

output:

1

result:

ok 

Subtask #2:

score: 15
Accepted

Test #26:

score: 15
Accepted
time: 30ms
memory: 7620kb

input:

100000 57165 10261 2
57165 48992
57165 19387
71033 57165
13350 57165
52013 57165
39911 57165
31569 57165
57165 57655
47865 57165
57165 61895
79639 57165
35978 57165
47454 57165
76859 57165
57165 45447
31140 57165
57165 67169
57165 95791
57165 60405
57165 80905
57165 55354
57165 95642
8667 57165
8827...

output:

2 57165 0 99999
48992 19387 71033 13350 52013 39911 31569 57655 47865 61895 79639 35978 47454 76859 45447 31140 67169 95791 60405 80905 55354 95642 8667 88274 721 61541 31467 62158 93646 5791 37673 90967 70822 50373 6922 9211 12493 55791 99612 86337 52418 27225 13284 54010 57405 99213 36389 5528 532...

input:

2 57165 0 99999
48992 19387 71033 13350 52013 39911 31569 57655 47865 61895 79639 35978 47454 76859 45447 31140 67169 95791 60405 80905 55354 95642 8667 88274 721 61541 31467 62158 93646 5791 37673 90967 70822 50373 6922 9211 12493 55791 99612 86337 52418 27225 13284 54010 57405 99213 36389 5528 532...

output:

10261

result:

ok 

Test #27:

score: 15
Accepted
time: 2ms
memory: 5900kb

input:

100000 20690 20690 2
97025 11592
8829 11592
11592 95625
11592 30832
11592 71951
11592 59839
11592 58624
65454 11592
46862 11592
86426 11592
11592 2542
11592 43812
59361 11592
11592 89769
84488 11592
11592 97510
77985 11592
11592 74093
20808 11592
22285 11592
11592 78659
11592 69395
51936 11592
10374...

output:

2 20690 0 1
11592 
1 

input:

2 20690 0 1
11592 
1 

output:

20690

result:

ok 

Test #28:

score: 15
Accepted
time: 8ms
memory: 5916kb

input:

100000 65054 52134 2
52134 74093
74895 52134
19206 52134
4235 52134
52134 74265
52134 96316
52134 22349
52134 81235
24872 52134
52134 18500
65129 52134
4289 52134
52134 41502
52134 62507
52134 58062
52134 9319
52134 9898
52134 98743
52134 73792
62834 52134
71095 52134
52134 50084
16065 52134
68492 5...

output:

2 65054 0 1
52134 
0 

input:

2 65054 0 1
52134 
0 

output:

52134

result:

ok 

Test #29:

score: 15
Accepted
time: 24ms
memory: 7612kb

input:

100000 77363 77363 2
1124 77363
77363 76872
77363 55161
82007 77363
68938 77363
51460 77363
77363 89625
77363 19141
77363 93908
77363 60862
84152 77363
77363 14422
77363 63469
77363 60128
77363 23779
56985 77363
77363 44495
77363 70405
33650 77363
48283 77363
57092 77363
37217 77363
53815 77363
7921...

output:

2 77363 0 99999
1124 76872 55161 82007 68938 51460 89625 19141 93908 60862 84152 14422 63469 60128 23779 56985 44495 70405 33650 48283 57092 37217 53815 79212 18151 21576 9156 40524 58866 61012 13634 47074 71660 61247 9905 35741 62260 39549 6514 48989 68201 6118 63298 59900 55307 44090 11614 32131 3...

input:

2 77363 0 99999
1124 76872 55161 82007 68938 51460 89625 19141 93908 60862 84152 14422 63469 60128 23779 56985 44495 70405 33650 48283 57092 37217 53815 79212 18151 21576 9156 40524 58866 61012 13634 47074 71660 61247 9905 35741 62260 39549 6514 48989 68201 6118 63298 59900 55307 44090 11614 32131 3...

output:

77363

result:

ok 

Test #30:

score: 15
Accepted
time: 0ms
memory: 5928kb

input:

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

output:

2 3 0 1
2 
0 

input:

2 3 0 1
2 
0 

output:

2

result:

ok 

Test #31:

score: 15
Accepted
time: 6ms
memory: 5888kb

input:

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

output:

2 1 0 1
4 
0 

input:

2 1 0 1
4 
0 

output:

1

result:

ok 

Test #32:

score: 15
Accepted
time: 6ms
memory: 5868kb

input:

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

output:

2 5 0 2
2 3 
1 1 

input:

2 5 0 2
2 3 
1 1 

output:

5

result:

ok 

Test #33:

score: 15
Accepted
time: 2ms
memory: 5924kb

input:

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

output:

2 1 1 2
2 3 
1 0 

input:

2 1 1 2
2 3 
1 0 

output:

3

result:

ok 

Test #34:

score: 15
Accepted
time: 6ms
memory: 6052kb

input:

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

output:

2 1 1 1
3 
0 

input:

2 1 1 1
3 
0 

output:

3

result:

ok 

Test #35:

score: 15
Accepted
time: 0ms
memory: 5920kb

input:

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

output:

2 4 0 2
5 2 
1 1 

input:

2 4 0 2
5 2 
1 1 

output:

5

result:

ok 

Test #36:

score: 15
Accepted
time: 8ms
memory: 5928kb

input:

100000 23979 85431 2
8021 56912
10503 76689
26288 92632
41590 89656
71614 4680
7052 49719
48777 44360
80643 3019
65567 53937
80417 64878
78820 29084
73618 24522
960 99774
95415 28446
14225 66907
47234 73704
69540 62019
30668 80360
60924 72272
94562 40783
19263 5431
35087 44496
29324 1281
67978 46994...

output:

2 23979 0 1
18244 
0 

input:

2 23979 0 1
18244 
0 

output:

18244

result:

ok 

Test #37:

score: 15
Accepted
time: 0ms
memory: 5960kb

input:

100000 36733 60881 2
80147 86156
11060 43885
84196 46747
45664 69729
74702 74185
79268 43010
71671 83489
87442 24603
20842 5103
24802 66423
42617 63554
33374 87119
9497 70888
88187 54274
48989 30887
36322 85447
7844 88469
16844 30626
6941 40029
29312 12959
14222 51508
87906 2694
41789 24242
32143 91...

output:

2 36733 1 2
91096 34972 
0 0 

input:

2 36733 1 2
91096 34972 
0 0 

output:

91096

result:

ok 

Test #38:

score: 15
Accepted
time: 6ms
memory: 5952kb

input:

100000 21792 41596 2
57591 85046
79384 35600
56379 34895
30404 45347
42934 4689
89254 66623
17070 40703
17167 14829
44625 61964
14889 5744
90305 20067
44701 41016
89462 44682
9527 29698
5391 36085
92431 20049
73079 61362
6013 68598
40983 43057
20230 55766
47032 4811
90941 74757
17767 73835
35944 453...

output:

2 21792 0 1
23369 
1 

input:

2 21792 0 1
23369 
1 

output:

23369

result:

ok 

Test #39:

score: 15
Accepted
time: 8ms
memory: 6068kb

input:

100000 64043 14342 2
85792 63229
95339 30162
25490 40989
47150 73365
6714 73468
26342 35008
10055 18738
45745 62797
19975 65166
77799 67471
30653 96512
79035 74183
26358 11632
82402 78556
66140 30359
24658 70730
62076 23875
8677 79098
57019 15823
52575 63548
81858 87224
56859 4937
58780 25703
33335 ...

output:

2 64043 0 2
68157 85647 
0 1 

input:

2 64043 0 2
68157 85647 
0 1 

output:

85647

result:

ok 

Test #40:

score: 15
Accepted
time: 4ms
memory: 6072kb

input:

100000 75553 39217 2
11676 82599
10716 10773
27906 95464
2744 30185
62413 98466
41025 41487
42277 79707
60525 84299
9085 14108
19427 12181
32546 21837
76311 96550
59576 36407
15781 16981
78641 11880
37063 66249
51153 32078
13718 38586
68036 97478
59698 44246
58377 55325
17917 29044
72063 79955
61158...

output:

2 75553 0 1
87033 
1 

input:

2 75553 0 1
87033 
1 

output:

87033

result:

ok 

Test #41:

score: 15
Accepted
time: 6ms
memory: 5964kb

input:

100000 21917 59250 2
13148 63090
12649 50271
3310 86136
20232 38587
44316 6107
46029 56537
4615 41678
70126 41892
31662 90178
34847 86090
43955 68556
54719 73987
87604 18071
3634 11565
92296 55240
57131 17570
89995 95646
42613 24657
94268 13510
99171 60222
99920 63245
66092 66115
63629 65740
2694 52...

output:

2 21917 1 2
43084 76779 
0 1 

input:

2 21917 1 2
43084 76779 
0 1 

output:

43084

result:

ok 

Test #42:

score: 15
Accepted
time: 0ms
memory: 5948kb

input:

100000 10599 64793 2
68263 64737
92774 70343
61521 55518
31393 41312
67062 38539
27583 7834
38108 68148
28467 21316
51609 6806
96835 55941
63136 63774
73593 28975
91965 70437
60187 92076
12545 67161
24818 84837
31796 2012
78675 4189
41557 5875
82947 65487
672 3006
64244 60913
11777 61744
28507 3176
...

output:

2 10599 0 4
40969 38121 55244 65315 
1 0 0 0 

input:

2 10599 0 4
40969 38121 55244 65315 
1 0 0 0 

output:

40969

result:

ok 

Test #43:

score: 15
Accepted
time: 8ms
memory: 6008kb

input:

100000 36428 90052 2
3635 46478
76825 1950
71310 3150
91655 59406
53063 3113
41419 28809
24424 55601
93522 52928
57446 35409
29244 51473
24470 47107
74040 70180
87398 98190
55205 67625
75879 73400
58664 43024
3241 56042
13644 63181
78417 15719
76619 14788
65584 29933
7844 2021
21036 3787
71465 58842...

output:

2 36428 0 2
62766 58860 
0 1 

input:

2 36428 0 2
62766 58860 
0 1 

output:

58860

result:

ok 

Test #44:

score: 15
Accepted
time: 0ms
memory: 5948kb

input:

100000 93814 13980 2
12879 95970
88657 43515
35152 35369
54031 66011
83539 14492
51534 69335
24994 75741
66405 81259
48790 2777
13626 67544
72836 7107
27112 14714
58045 91668
97716 76443
34048 36880
48347 73335
46773 10460
58962 12863
76197 98841
87073 82940
29007 97806
76323 26628
21738 15794
82484...

output:

2 93814 1 6
90841 33901 91307 90206 73677 35168 
0 0 0 0 1 0 

input:

2 93814 1 6
90841 33901 91307 90206 73677 35168 
0 0 0 0 1 0 

output:

73677

result:

ok 

Test #45:

score: 15
Accepted
time: 6ms
memory: 5932kb

input:

100000 89302 22103 2
13951 37836
89725 17201
99662 93122
98984 79006
97838 61737
8622 66857
42301 78812
31431 90998
1099 83426
81995 3812
16664 64387
98474 23209
98974 69592
54292 26495
42272 2981
93307 21292
61871 88562
9015 60574
14507 2176
71767 45973
5750 7623
36489 23847
6517 55616
35684 56849
...

output:

2 89302 0 2
60102 45141 
0 1 

input:

2 89302 0 2
60102 45141 
0 1 

output:

60102

result:

ok 

Test #46:

score: 15
Accepted
time: 6ms
memory: 5960kb

input:

2 2 2 2
2 1

output:

2 2 0 1
1 
1 

input:

2 2 0 1
1 
1 

output:

2

result:

ok 

Test #47:

score: 15
Accepted
time: 4ms
memory: 5916kb

input:

2 2 1 2
1 2

output:

2 2 0 1
1 
0 

input:

2 2 0 1
1 
0 

output:

1

result:

ok 

Test #48:

score: 15
Accepted
time: 8ms
memory: 5916kb

input:

3 3 3 2
1 3
3 2

output:

2 3 0 2
1 2 
1 1 

input:

2 3 0 2
1 2 
1 1 

output:

3

result:

ok 

Test #49:

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

input:

3 2 3 2
1 2
2 3

output:

2 2 1 2
1 3 
0 0 

input:

2 2 1 2
1 3 
0 0 

output:

3

result:

ok 

Test #50:

score: 15
Accepted
time: 2ms
memory: 5932kb

input:

3 2 2 2
1 3
3 2

output:

2 2 0 1
3 
0 

input:

2 2 0 1
3 
0 

output:

2

result:

ok 

Test #51:

score: 15
Accepted
time: 6ms
memory: 5912kb

input:

3 1 3 2
2 3
3 1

output:

2 1 1 1
3 
0 

input:

2 1 1 1
3 
0 

output:

3

result:

ok 

Test #52:

score: 15
Accepted
time: 8ms
memory: 6056kb

input:

3 3 1 2
2 3
1 2

output:

2 3 0 1
2 
0 

input:

2 3 0 1
2 
0 

output:

2

result:

ok 

Subtask #3:

score: 20
Accepted

Test #53:

score: 20
Accepted
time: 2ms
memory: 5932kb

input:

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

output:

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

input:

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

output:

1

result:

ok 

Test #54:

score: 20
Accepted
time: 4ms
memory: 5904kb

input:

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

output:

3 5 0 1
4 
0 

input:

3 5 0 1
4 
0 

output:

4

result:

ok 

Test #55:

score: 20
Accepted
time: 0ms
memory: 6072kb

input:

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

output:

3 2 1 1
4 
0 

input:

3 2 1 1
4 
0 

output:

4

result:

ok 

Test #56:

score: 20
Accepted
time: 8ms
memory: 6652kb

input:

50000 34879 23464 3
34879 15963
18721 34879
34879 10106
18364 34879
34879 23006
15487 34879
48356 34879
29325 34879
49428 34879
34879 33232
34879 11053
25243 34879
1729 34879
28816 34879
34879 28832
6766 34879
38567 34879
16292 34879
34879 12983
34879 39259
34879 12547
38228 34879
10922 34879
35635 ...

output:

3 34879 0 49999
15963 18721 10106 18364 23006 15487 48356 29325 49428 33232 11053 25243 1729 28816 28832 6766 38567 16292 12983 39259 12547 38228 10922 35635 35095 29959 12379 32853 14075 47835 35673 37166 32219 26253 17599 2709 46140 16178 29606 48367 20875 30557 37853 306 48005 19363 12031 26274 9...

input:

3 34879 0 49999
15963 18721 10106 18364 23006 15487 48356 29325 49428 33232 11053 25243 1729 28816 28832 6766 38567 16292 12983 39259 12547 38228 10922 35635 35095 29959 12379 32853 14075 47835 35673 37166 32219 26253 17599 2709 46140 16178 29606 48367 20875 30557 37853 306 48005 19363 12031 26274 9...

output:

23464

result:

ok 

Test #57:

score: 20
Accepted
time: 8ms
memory: 5920kb

input:

50000 23915 16691 3
5730 47713
5730 30001
5730 37173
5730 48062
5730 47318
25627 5730
38604 5730
5554 5730
28931 5730
5730 4971
8248 5730
2646 5730
5611 5730
42980 5730
5730 11640
5730 5440
15681 5730
41594 5730
5730 3925
24489 5730
28880 5730
5730 22654
5730 40596
5730 42786
35298 5730
33116 5730
5...

output:

3 23915 1 1
5730 
1 

input:

3 23915 1 1
5730 
1 

output:

5730

result:

ok 

Test #58:

score: 20
Accepted
time: 2ms
memory: 5920kb

input:

50000 21541 21500 3
21500 28433
40076 21500
21500 44511
23826 21500
38374 21500
13185 21500
33217 21500
21500 29688
21500 41527
21500 36460
46072 21500
21500 3314
49915 21500
21500 111
25720 21500
7768 21500
48085 21500
38431 21500
44557 21500
41668 21500
21500 44992
21500 6887
21500 20065
21500 222...

output:

3 21541 0 1
21500 
0 

input:

3 21541 0 1
21500 
0 

output:

21500

result:

ok 

Test #59:

score: 20
Accepted
time: 6ms
memory: 5908kb

input:

50000 46350 23808 3
41775 4812
41775 25985
7373 41775
41775 21281
34476 41775
29680 41775
41775 31678
41775 45771
41775 7651
15726 41775
23964 41775
5022 41775
41775 35007
43947 41775
41775 7035
41775 40944
41775 7621
41775 24012
38543 41775
23389 41775
41775 5274
41775 16534
41775 29419
16250 41775...

output:

3 46350 0 1
41775 
0 

input:

3 46350 0 1
41775 
0 

output:

41775

result:

ok 

Test #60:

score: 20
Accepted
time: 2ms
memory: 5864kb

input:

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

output:

3 8 0 1
2 
0 

input:

3 8 0 1
2 
0 

output:

2

result:

ok 

Test #61:

score: 20
Accepted
time: 0ms
memory: 5948kb

input:

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

output:

3 2 1 3
5 8 4 
1 1 0 

input:

3 2 1 3
5 8 4 
1 1 0 

output:

4

result:

ok 

Test #62:

score: 20
Accepted
time: 0ms
memory: 6056kb

input:

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

output:

3 4 1 1
3 
1 

input:

3 4 1 1
3 
1 

output:

3

result:

ok 

Test #63:

score: 20
Accepted
time: 8ms
memory: 6080kb

input:

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

output:

3 2 0 3
7 1 6 
1 1 0 

input:

3 2 0 3
7 1 6 
1 1 0 

output:

7

result:

ok 

Test #64:

score: 20
Accepted
time: 2ms
memory: 6080kb

input:

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

output:

3 2 0 1
5 
1 

input:

3 2 0 1
5 
1 

output:

5

result:

ok 

Test #65:

score: 20
Accepted
time: 6ms
memory: 5948kb

input:

99998 87386 58198 3
85465 2972
82055 13745
90944 2989
22869 2304
83782 38621
75141 77939
16283 28026
37731 94249
69186 67502
32120 24562
13030 45973
51269 5775
71907 93802
43291 61040
31976 48691
86121 90698
67358 96244
25898 5756
92398 19735
68317 57405
85257 19812
37326 11401
27210 8208
90462 2661...

output:

3 87386 0 1
58198 
0 

input:

3 87386 0 1
58198 
0 

output:

58198

result:

ok 

Test #66:

score: 20
Accepted
time: 6ms
memory: 5892kb

input:

99998 97510 72855 3
84732 41538
54532 86688
55775 44754
92474 21130
99372 64772
75367 98020
13008 63796
65345 89495
9008 13825
33954 87101
43847 80979
10344 91037
77587 75389
82456 72826
89024 65686
4341 62555
8148 54141
30503 2594
70755 74647
19061 81455
46427 6657
87560 318
54163 78148
99060 77195...

output:

3 97510 0 1
73397 
0 

input:

3 97510 0 1
73397 
0 

output:

73397

result:

ok 

Test #67:

score: 20
Accepted
time: 4ms
memory: 6080kb

input:

99998 87597 71679 3
23321 99432
61011 75568
59562 83016
28506 18917
33527 71746
7668 6679
4148 3070
16461 73797
45092 28402
6791 48043
50597 41294
63374 95417
52317 15407
33787 37709
50384 81996
16094 38940
68650 55035
70481 13519
30578 42978
87862 99595
26819 47356
94615 83775
23100 27960
57129 980...

output:

3 87597 1 3
76112 6155 22434 
0 0 1 

input:

3 87597 1 3
76112 6155 22434 
0 0 1 

output:

22434

result:

ok 

Test #68:

score: 20
Accepted
time: 2ms
memory: 6068kb

input:

99998 90556 3982 3
55569 37718
50806 80524
18312 16562
65488 70341
65803 15799
69221 66636
94816 50449
29315 85891
13143 51588
29882 18556
17493 49983
3241 92131
87771 95128
35908 43452
83063 33469
64934 36806
94216 95699
67165 88310
16894 30338
5035 64482
87157 88194
96602 60827
91326 18976
60833 9...

output:

3 90556 0 1
23629 
0 

input:

3 90556 0 1
23629 
0 

output:

23629

result:

ok 

Test #69:

score: 20
Accepted
time: 0ms
memory: 5900kb

input:

99998 79909 92565 3
88859 84427
14618 17244
68129 57886
36300 47030
21219 46420
17014 62101
42591 37059
56911 34226
67342 32924
39482 57723
43236 40208
95154 89528
72024 11170
61343 10776
72798 79510
60837 74393
77740 90999
79375 71014
47551 21020
90125 59504
53401 87460
12124 68259
12707 98804
9067...

output:

3 79909 1 3
2667 43399 1784 
0 0 1 

input:

3 79909 1 3
2667 43399 1784 
0 0 1 

output:

1784

result:

ok 

Test #70:

score: 20
Accepted
time: 6ms
memory: 5924kb

input:

69270 24085 61128 3
68199 15118
41658 15267
9633 662
5510 22366
62291 2403
23878 4021
17026 49991
12290 50837
26282 58833
53945 34220
15973 56296
45991 24116
45537 9328
45147 7621
47998 33099
9943 53203
13997 34315
4339 62106
22599 4580
3324 27707
9191 13150
44334 45282
47725 60279
43121 46517
17049...

output:

3 24085 1 3
61617 61128 33673 
1 0 1 

input:

3 24085 1 3
61617 61128 33673 
1 0 1 

output:

61128

result:

ok 

Test #71:

score: 20
Accepted
time: 0ms
memory: 6052kb

input:

69242 44332 10146 3
7883 18552
22727 26244
42839 22642
48750 58513
51736 27694
23205 9163
24370 38130
14210 46890
63155 26346
45294 36378
15751 4424
49130 43898
61347 1001
41674 58717
66016 44970
38743 66446
24709 27021
51092 53673
44510 20006
12395 41842
37670 53434
31110 25993
19277 2095
68701 465...

output:

3 44332 0 1
10146 
0 

input:

3 44332 0 1
10146 
0 

output:

10146

result:

ok 

Test #72:

score: 20
Accepted
time: 0ms
memory: 6064kb

input:

69258 37183 21844 3
3568 19492
62947 13375
29040 11955
984 42825
58469 45573
17197 56454
40105 66996
4160 17103
29841 68049
17352 57751
43188 51283
43016 39259
41341 24053
15422 7336
24991 41096
35832 22801
10128 53059
68207 17482
26030 30889
23120 49376
9297 21384
22185 33840
24171 20500
64556 4013...

output:

3 37183 1 1
35243 
1 

input:

3 37183 1 1
35243 
1 

output:

35243

result:

ok 

Test #73:

score: 20
Accepted
time: 2ms
memory: 6068kb

input:

69366 49894 57697 3
41375 50675
5007 58149
30125 3057
10096 44436
1842 655
57308 55350
36790 52159
55813 65365
53158 37328
23393 66362
2863 21626
41648 46091
52983 51494
13659 45191
68934 51324
4164 12544
6386 36506
43204 36426
44958 12916
47344 54643
2000 60200
60097 6311
3330 51286
50029 2148
8220...

output:

3 49894 0 3
56550 14390 68184 
1 1 0 

input:

3 49894 0 3
56550 14390 68184 
1 1 0 

output:

56550

result:

ok 

Test #74:

score: 20
Accepted
time: 8ms
memory: 6008kb

input:

69096 42739 4789 3
45282 12652
19052 39449
39681 54466
58966 66221
10473 61777
45144 3043
17824 34338
51894 55281
57207 24668
48379 793
67072 18461
68641 26473
31867 54409
47374 67677
14372 63964
62273 32200
45887 5410
55232 25958
56211 39709
33916 41331
2446 18606
10186 17392
18371 51156
39950 5453...

output:

3 42739 1 1
68533 
0 

input:

3 42739 1 1
68533 
0 

output:

68533

result:

ok 

Test #75:

score: 20
Accepted
time: 0ms
memory: 5928kb

input:

66930 59153 4676 3
7004 63609
34687 41913
52475 61106
57593 42098
38408 53442
51388 61176
40543 864
4073 14219
18096 46890
35719 143
39285 45392
45738 43859
44755 14930
34845 18122
18534 5172
23170 54575
60980 49730
25633 61907
58461 62508
31935 49777
33946 23367
50628 49547
25596 16214
11696 8731
3...

output:

3 59153 0 7
61024 44979 8322 4676 13312 13675 58179 
0 1 1 0 1 1 1 

input:

3 59153 0 7
61024 44979 8322 4676 13312 13675 58179 
0 1 1 0 1 1 1 

output:

4676

result:

ok 

Test #76:

score: 20
Accepted
time: 2ms
memory: 5952kb

input:

66645 33740 19280 3
22952 17674
57654 51266
52631 16942
33688 61469
66429 64852
62593 47804
8182 25604
40402 54504
60635 52831
41262 47572
29798 35663
56971 17441
12090 13348
58974 41728
34426 64779
43708 27398
43913 40917
25131 4781
12973 28015
16867 5639
23702 26232
13229 6005
55144 2552
37300 496...

output:

3 33740 0 11
130 30573 60524 16664 40440 4203 42589 57057 51159 15371 3165 
1 1 0 1 0 0 0 0 0 1 1 

input:

3 33740 0 11
130 30573 60524 16664 40440 4203 42589 57057 51159 15371 3165 
1 1 0 1 0 0 0 0 0 1 1 

output:

4203

result:

ok 

Test #77:

score: 20
Accepted
time: 4ms
memory: 5888kb

input:

66912 33116 25964 3
29784 58144
20167 50174
32902 34332
13567 133
37516 26556
55743 10732
49002 9731
47341 39096
49774 2730
66822 49778
51823 10164
60512 8347
35533 3933
25236 44672
9180 2050
10723 45618
712 57593
1871 37226
28487 41243
27882 46326
8535 32858
5745 58678
46769 11497
1561 57203
30760 ...

output:

3 33116 0 10
4688 25964 40131 54651 37821 27712 7993 45835 11686 22318 
1 0 0 0 0 1 1 0 1 1 

input:

3 33116 0 10
4688 25964 40131 54651 37821 27712 7993 45835 11686 22318 
1 0 0 0 0 1 1 0 1 1 

output:

25964

result:

ok 

Test #78:

score: 20
Accepted
time: 6ms
memory: 5952kb

input:

66783 48029 29954 3
7718 14264
45180 47413
8493 27266
37538 61463
6405 8648
23708 57722
37760 48280
45105 49745
23646 48674
6758 1070
23966 36538
61481 45780
45507 40154
51777 18045
62854 53383
39920 7330
50383 57786
62531 29427
64040 8284
49258 35428
55482 15248
44014 19572
31460 16102
8190 59801
2...

output:

3 48029 0 7
49633 54745 60922 3783 62409 5397 14145 
0 0 0 1 0 0 1 

input:

3 48029 0 7
49633 54745 60922 3783 62409 5397 14145 
0 0 0 1 0 0 1 

output:

5397

result:

ok 

Test #79:

score: 20
Accepted
time: 2ms
memory: 6068kb

input:

66859 56605 21424 3
7483 3312
4771 37748
28062 14410
15499 49955
3172 50112
14102 50403
61621 45960
49260 45959
37977 32725
21951 59361
66693 18627
17571 4199
16817 52300
36674 55981
50020 60334
15318 28522
60048 42857
21720 4136
52341 15061
50117 63392
56652 55241
36794 35309
18237 41763
60354 2319...

output:

3 56605 1 3
27942 32024 35717 
0 0 1 

input:

3 56605 1 3
27942 32024 35717 
0 0 1 

output:

35717

result:

ok 

Test #80:

score: 20
Accepted
time: 8ms
memory: 5880kb

input:

67022 62574 27512 3
24697 30781
921 56134
14879 7954
45803 8914
20815 34159
37545 53425
23144 8131
25636 22299
58066 59170
3687 21694
38489 23801
34186 9970
25110 49832
42470 62659
25187 19669
25433 66075
17057 28374
25238 12479
63457 37055
14651 8277
52314 38714
58275 8078
37531 57698
8142 40981
31...

output:

3 62574 1 6
17480 4358 8403 40742 66549 19018 
0 1 0 0 1 0 

input:

3 62574 1 6
17480 4358 8403 40742 66549 19018 
0 1 0 0 1 0 

output:

4358

result:

ok 

Test #81:

score: 20
Accepted
time: 6ms
memory: 5964kb

input:

2 2 1 3
1 2

output:

3 2 0 1
1 
0 

input:

3 2 0 1
1 
0 

output:

1

result:

ok 

Test #82:

score: 20
Accepted
time: 2ms
memory: 5916kb

input:

4 4 1 3
4 2
1 4
3 4

output:

3 4 0 3
2 1 3 
1 0 1 

input:

3 4 0 3
2 1 3 
1 0 1 

output:

1

result:

ok 

Test #83:

score: 20
Accepted
time: 8ms
memory: 5960kb

input:

4 4 3 3
2 3
3 1
3 4

output:

3 4 0 1
3 
0 

input:

3 4 0 1
3 
0 

output:

3

result:

ok 

Test #84:

score: 20
Accepted
time: 0ms
memory: 6068kb

input:

4 3 1 3
3 1
3 2
3 4

output:

3 3 0 3
1 2 4 
0 1 0 

input:

3 3 0 3
1 2 4 
0 1 0 

output:

1

result:

ok 

Subtask #4:

score: 55
Accepted

Test #85:

score: 55
Accepted
time: 2ms
memory: 5944kb

input:

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

output:

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

input:

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

output:

4

result:

ok 

Test #86:

score: 55
Accepted
time: 6ms
memory: 5916kb

input:

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

output:

4 2 0 1
5 
0 

input:

4 2 0 1
5 
0 

output:

2

result:

ok 

Test #87:

score: 55
Accepted
time: 6ms
memory: 6056kb

input:

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

output:

4 5 0 1
4 
0 

input:

4 5 0 1
4 
0 

output:

4

result:

ok 

Test #88:

score: 55
Accepted
time: 6ms
memory: 5960kb

input:

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

output:

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

input:

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

output:

5

result:

ok 

Test #89:

score: 55
Accepted
time: 42ms
memory: 7640kb

input:

100000 26342 56884 4
26342 46282
85015 26342
78181 26342
26342 55212
26342 56473
26342 22060
26342 25078
26342 20025
29747 26342
26342 28742
46830 26342
26342 18889
98909 26342
92001 26342
20688 26342
54802 26342
26342 29222
76143 26342
26342 85266
26342 6260
26342 60268
4638 26342
90626 26342
26342...

output:

4 26342 1 99999
46282 85015 78181 55212 56473 22060 25078 20025 29747 28742 46830 18889 98909 92001 20688 54802 29222 76143 85266 6260 60268 4638 90626 80630 8026 12054 8992 66581 51929 62991 26344 67091 55918 67863 7398 56054 22280 6765 60156 35722 12177 21618 88262 8990 7486 40474 57382 2382 66829...

input:

4 26342 1 99999
46282 85015 78181 55212 56473 22060 25078 20025 29747 28742 46830 18889 98909 92001 20688 54802 29222 76143 85266 6260 60268 4638 90626 80630 8026 12054 8992 66581 51929 62991 26344 67091 55918 67863 7398 56054 22280 6765 60156 35722 12177 21618 88262 8990 7486 40474 57382 2382 66829...

output:

56884

result:

ok 

Test #90:

score: 55
Accepted
time: 2ms
memory: 6060kb

input:

100000 36685 36685 4
86808 73933
23292 86808
33903 86808
86808 30988
86808 4206
16014 86808
510 86808
86808 2790
86808 62671
20557 86808
28298 86808
86808 1116
86808 55337
16168 86808
86014 86808
86808 57562
90844 86808
86808 25307
86808 73347
69249 86808
86808 32186
29405 86808
18521 86808
86808 97...

output:

4 36685 0 1
86808 
0 

input:

4 36685 0 1
86808 
0 

output:

36685

result:

ok 

Test #91:

score: 55
Accepted
time: 6ms
memory: 5900kb

input:

100000 94080 34977 4
65924 34977
34977 83276
34977 28485
34977 41621
34977 23965
34977 76619
81500 34977
34977 16670
6636 34977
34977 39380
5810 34977
34977 65506
77687 34977
13399 34977
45787 34977
80 34977
12209 34977
78417 34977
78584 34977
50703 34977
11564 34977
27694 34977
13949 34977
34977 48...

output:

4 94080 0 1
34977 
0 

input:

4 94080 0 1
34977 
0 

output:

34977

result:

ok 

Test #92:

score: 55
Accepted
time: 44ms
memory: 7560kb

input:

100000 93693 93693 4
93693 8880
93693 25095
93693 17270
93693 23374
46524 93693
93693 939
93693 92315
81734 93693
93693 28617
93693 25260
4700 93693
89576 93693
93693 37135
93693 79749
7531 93693
44970 93693
93693 23833
8268 93693
93693 56152
45070 93693
8450 93693
93693 94919
54151 93693
24886 9369...

output:

4 93693 0 99999
8880 25095 17270 23374 46524 939 92315 81734 28617 25260 4700 89576 37135 79749 7531 44970 23833 8268 56152 45070 8450 94919 54151 24886 92293 16629 9001 83139 57305 77922 52332 53621 54791 33073 34064 22480 95184 89332 54573 4188 22018 92480 29139 42520 41864 84356 52187 75688 24772...

input:

4 93693 0 99999
8880 25095 17270 23374 46524 939 92315 81734 28617 25260 4700 89576 37135 79749 7531 44970 23833 8268 56152 45070 8450 94919 54151 24886 92293 16629 9001 83139 57305 77922 52332 53621 54791 33073 34064 22480 95184 89332 54573 4188 22018 92480 29139 42520 41864 84356 52187 75688 24772...

output:

93693

result:

ok 

Test #93:

score: 55
Accepted
time: 2ms
memory: 5904kb

input:

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

output:

4 3 0 1
1 
0 

input:

4 3 0 1
1 
0 

output:

1

result:

ok 

Test #94:

score: 55
Accepted
time: 6ms
memory: 5928kb

input:

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

output:

4 3 0 1
4 
0 

input:

4 3 0 1
4 
0 

output:

3

result:

ok 

Test #95:

score: 55
Accepted
time: 12ms
memory: 5948kb

input:

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

output:

4 1 0 2
5 3 
0 0 

input:

4 1 0 2
5 3 
0 0 

output:

1

result:

ok 

Test #96:

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

input:

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

output:

4 2 0 2
5 1 
0 0 

input:

4 2 0 2
5 1 
0 0 

output:

1

result:

ok 

Test #97:

score: 55
Accepted
time: 2ms
memory: 6084kb

input:

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

output:

4 5 1 1
1 
1 

input:

4 5 1 1
1 
1 

output:

1

result:

ok 

Test #98:

score: 55
Accepted
time: 10ms
memory: 6064kb

input:

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

output:

4 4 1 2
1 2 
0 1 

input:

4 4 1 2
1 2 
0 1 

output:

2

result:

ok 

Test #99:

score: 55
Accepted
time: 4ms
memory: 5952kb

input:

100000 23888 95634 4
61184 6521
17651 26583
70465 8469
83683 37139
90541 94542
20527 88348
1087 98871
51684 35441
10023 1184
97680 43661
38876 15646
86791 94288
87477 49815
95192 90460
21603 62501
2704 57119
67517 67611
3257 98756
74158 52962
39718 12115
23665 16245
4470 66828
49706 95479
74318 8547...

output:

4 23888 1 1
95634 
0 

input:

4 23888 1 1
95634 
0 

output:

95634

result:

ok 

Test #100:

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

input:

100000 51059 51059 4
85833 27487
96543 6131
73366 64252
18501 32986
19870 48223
77204 60797
11349 10039
47339 35882
19570 31316
36866 39413
49467 78258
40875 92416
20184 94908
66385 58327
64474 65861
76722 12874
24403 49745
79379 13366
74210 74660
64142 68125
45741 22943
81593 14346
22455 26901
9624...

output:

4 51059 0 2
70246 56777 
0 0 

input:

4 51059 0 2
70246 56777 
0 0 

output:

51059

result:

ok 

Test #101:

score: 55
Accepted
time: 2ms
memory: 5948kb

input:

100000 22080 45672 4
83880 34877
63161 94429
33236 56192
76617 85924
36115 93334
37402 95435
93028 33138
32595 35663
78692 52319
14667 4812
30920 65425
96471 76240
721 33590
61285 88812
24040 9262
44632 64864
98564 86132
89276 81938
93349 48210
20937 98655
77501 79659
72053 68922
75339 38219
52597 6...

output:

4 22080 1 2
31254 45672 
1 0 

input:

4 22080 1 2
31254 45672 
1 0 

output:

45672

result:

ok 

Test #102:

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

input:

100000 47400 47400 4
8469 21181
78547 64951
71756 28403
61162 84762
581 41701
34743 71172
88401 75236
10648 45602
67946 25716
46220 37965
43084 452
30485 49348
21642 45870
34282 97012
47687 41711
84600 33655
50902 27105
9210 67184
85444 16101
43363 69991
92127 27044
88458 25611
94613 4066
45654 6652...

output:

4 47400 0 1
35823 
1 

input:

4 47400 0 1
35823 
1 

output:

47400

result:

ok 

Test #103:

score: 55
Accepted
time: 8ms
memory: 5928kb

input:

100000 71354 89044 4
99050 73932
66027 33749
58595 78089
85956 9017
32113 80500
65198 8908
7972 66542
33945 67925
26119 77925
69016 63754
32531 61052
86969 55795
12762 77836
3217 41289
90935 68852
84938 39476
79667 41219
73628 20275
40615 24758
67687 17989
596 40452
79207 11767
57047 41034
68391 501...

output:

4 71354 1 1
59046 
1 

input:

4 71354 1 1
59046 
1 

output:

59046

result:

ok 

Test #104:

score: 55
Accepted
time: 6ms
memory: 6056kb

input:

100000 28613 16541 4
49857 85364
64622 96576
79392 27674
91842 29971
73747 19142
93692 41609
57366 73882
10608 6620
89760 20038
36979 79858
18507 61482
12983 69523
36235 9425
11972 68526
32120 28010
97653 28306
31314 67298
53867 43622
5784 72774
11718 71581
7053 27673
83075 71666
23356 16977
56694 8...

output:

4 28613 0 2
42962 33238 
1 0 

input:

4 28613 0 2
42962 33238 
1 0 

output:

42962

result:

ok 

Test #105:

score: 55
Accepted
time: 4ms
memory: 6080kb

input:

100000 90204 17447 4
61283 85024
75259 98868
75156 86300
78107 92275
33297 5190
12279 16080
38018 44089
43267 12341
26094 44304
35 34470
15811 19395
93334 38688
19181 25964
65838 32667
50741 35511
49795 26144
59512 21840
45180 33800
63723 81590
63761 18031
78226 70467
98557 76879
12534 31553
38306 1...

output:

4 90204 1 1
22590 
1 

input:

4 90204 1 1
22590 
1 

output:

22590

result:

ok 

Test #106:

score: 55
Accepted
time: 6ms
memory: 5952kb

input:

100000 2919 26226 4
18738 56102
31842 80151
1840 81768
61884 58405
72036 23984
56768 65400
276 29131
75663 51413
20895 31958
19154 54159
37151 4501
88584 64733
36534 50464
37603 96927
43305 62049
19279 39861
77265 3379
57369 28254
23775 52887
49027 42856
75922 8136
21589 24374
41531 23936
42582 2222...

output:

4 2919 1 2
3298 83542 
1 0 

input:

4 2919 1 2
3298 83542 
1 0 

output:

83542

result:

ok 

Test #107:

score: 55
Accepted
time: 6ms
memory: 5904kb

input:

100000 1056 60225 4
42468 24968
56903 94907
7378 79467
18236 565
55161 59757
46139 65843
13296 75074
66166 54726
44963 35535
5313 31018
59677 52140
82028 87263
51435 94850
14813 25931
56986 6109
97251 32751
95886 77014
73201 56852
53162 29139
48479 17976
65059 56005
14844 39225
81879 4552
13631 7791...

output:

4 1056 1 3
44563 37478 60225 
1 1 0 

input:

4 1056 1 3
44563 37478 60225 
1 1 0 

output:

60225

result:

ok 

Test #108:

score: 55
Accepted
time: 6ms
memory: 5884kb

input:

100000 48689 48689 4
11433 96311
90323 57830
65373 47173
55644 33942
18547 6091
40362 81161
774 52402
77256 81755
63848 13984
20067 86745
45073 49490
29188 62058
43713 33979
58253 73938
17651 69687
93437 17985
70484 94597
41188 4914
15808 99202
21637 57019
95840 69143
90792 75071
5980 40083
66025 74...

output:

4 48689 0 3
43777 53322 76369 
1 0 0 

input:

4 48689 0 3
43777 53322 76369 
1 0 0 

output:

48689

result:

ok 

Test #109:

score: 55
Accepted
time: 6ms
memory: 5956kb

input:

100000 57645 36998 4
34614 49924
48424 62061
8215 18365
96629 10326
16106 9005
29177 743
92185 81532
97278 58217
34729 11385
19584 55890
77169 10025
9850 80390
5434 28250
67850 42275
80106 72569
74448 3714
44689 85793
47000 55887
33825 66296
48891 620
96514 57273
9708 64250
88238 27684
6976 16696
57...

output:

4 57645 0 3
5811 36998 28256 
1 0 1 

input:

4 57645 0 3
5811 36998 28256 
1 0 1 

output:

36998

result:

ok 

Test #110:

score: 55
Accepted
time: 2ms
memory: 6060kb

input:

100000 77346 74482 4
71889 30622
5219 43425
44345 31946
68262 24799
79864 90997
76442 99259
21889 12170
800 81205
41586 43713
57321 38564
30645 42279
3800 40954
14447 49437
89761 98215
30718 83529
60072 60315
76894 44660
642 57840
90380 47347
54031 8701
90986 27229
94247 27155
84446 66508
57646 9727...

output:

4 77346 1 2
51754 78260 
0 0 

input:

4 77346 1 2
51754 78260 
0 0 

output:

78260

result:

ok 

Test #111:

score: 55
Accepted
time: 4ms
memory: 5908kb

input:

100000 88506 91240 4
22391 61158
78152 13946
94607 34103
8587 15379
84077 92442
77412 55039
76983 79596
22488 51680
2952 22403
13947 14750
8613 50407
65404 69410
19471 50262
83891 20069
82719 4599
51863 28210
74593 95709
88293 56134
12745 80974
60377 39591
42091 70662
42012 28387
95721 65678
73294 2...

output:

4 88506 0 2
57658 5721 
0 1 

input:

4 88506 0 2
57658 5721 
0 1 

output:

57658

result:

ok 

Test #112:

score: 55
Accepted
time: 6ms
memory: 5928kb

input:

100000 28344 83312 4
91072 4081
38456 94088
34498 52475
4387 93371
71876 40675
38313 29676
32319 64514
30207 23586
96811 33809
90363 7493
11475 86867
64351 49067
20977 63409
44866 12234
66339 258
54101 58022
60601 48552
91385 45353
20951 51578
44339 21420
73500 46075
2414 2660
67170 24341
78481 5741...

output:

4 28344 1 2
43961 54170 
0 1 

input:

4 28344 1 2
43961 54170 
0 1 

output:

43961

result:

ok 

Test #113:

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

input:

100000 8565 3303 4
91449 5305
5875 71835
98269 94199
9016 84711
45041 84589
64779 91175
24306 30667
69536 44976
53370 72127
11683 95299
59074 14982
39762 38356
12642 29867
42477 40373
29961 17787
3781 9427
48501 29594
54122 35376
62430 85147
70139 18954
8423 60760
75112 85634
54216 26017
3321 94283
...

output:

4 8565 0 9
8322 47891 64843 3303 73195 51593 99579 38272 65812 
1 0 0 0 0 0 0 0 0 

input:

4 8565 0 9
8322 47891 64843 3303 73195 51593 99579 38272 65812 
1 0 0 0 0 0 0 0 0 

output:

3303

result:

ok 

Test #114:

score: 55
Accepted
time: 10ms
memory: 5952kb

input:

100000 21799 21799 4
62278 13919
95157 3942
21362 1478
72056 99626
724 47557
21602 69434
54133 65970
67185 2863
71420 87468
24914 51002
68035 27010
68103 59553
28275 84354
21120 99462
2149 65357
51466 95290
96495 83794
93627 68584
43309 3797
73633 90175
11365 26746
6950 75010
40998 67053
39552 15598...

output:

4 21799 0 6
2378 41643 2519 50070 99415 80003 
1 0 1 0 0 0 

input:

4 21799 0 6
2378 41643 2519 50070 99415 80003 
1 0 1 0 0 0 

output:

21799

result:

ok 

Test #115:

score: 55
Accepted
time: 6ms
memory: 6072kb

input:

100000 43017 1012 4
24447 41631
14504 10020
84627 68443
81775 29221
46626 77875
18310 23982
53762 98531
47320 32033
72641 29655
11823 49551
32391 52596
4960 36014
96800 12544
58627 68341
40457 40203
9375 77581
71670 73820
46120 4281
62666 8274
29639 33537
49241 87295
1131 35515
80529 57254
28456 321...

output:

4 43017 0 10
3583 14185 48517 1012 30233 20843 72299 50342 57155 17392 
1 1 0 0 1 1 0 0 0 1 

input:

4 43017 0 10
3583 14185 48517 1012 30233 20843 72299 50342 57155 17392 
1 1 0 0 1 1 0 0 0 1 

output:

1012

result:

ok 

Test #116:

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

input:

100000 33508 60021 4
27381 96611
81414 86961
50135 55871
22625 44708
4461 33992
26221 23133
94224 88842
21063 22891
70638 3525
91326 44791
70047 47926
62211 43703
69475 35891
11130 42047
58535 54943
72337 33505
47873 64491
77160 35663
53486 9997
53935 7587
51158 95004
76854 12930
93168 58435
25750 3...

output:

4 33508 1 6
21547 30492 91592 29635 2275 183 
0 0 1 0 1 0 

input:

4 33508 1 6
21547 30492 91592 29635 2275 183 
0 0 1 0 1 0 

output:

2275

result:

ok 

Test #117:

score: 55
Accepted
time: 8ms
memory: 6004kb

input:

100000 61085 27993 4
18722 6728
80833 55267
23481 46813
4004 79457
3980 16776
81242 37192
2550 72066
15353 38308
1485 70893
90855 87462
47607 30866
46959 7112
81782 76191
26526 90461
33244 89340
59308 2001
69193 75785
9153 70350
91416 76662
52362 56088
50934 8695
72480 49507
32037 18003
25416 74785
...

output:

4 61085 0 5
40651 97467 37721 60192 47213 
0 0 1 1 1 

input:

4 61085 0 5
40651 97467 37721 60192 47213 
0 0 1 1 1 

output:

40651

result:

ok 

Test #118:

score: 55
Accepted
time: 8ms
memory: 5960kb

input:

100000 71830 69192 4
60687 33394
44778 45869
24045 12118
21154 10426
61417 49457
1380 16847
89862 11755
11103 26517
37177 72799
7762 78893
82872 53718
77829 7074
95154 11528
23001 92762
95074 75575
54263 60499
39325 70606
42555 25138
77740 10230
11216 74527
26172 82039
94978 84614
86159 25852
26460 ...

output:

4 71830 1 3
3398 68368 91447 
1 0 1 

input:

4 71830 1 3
3398 68368 91447 
1 0 1 

output:

3398

result:

ok 

Test #119:

score: 55
Accepted
time: 6ms
memory: 5968kb

input:

2 1 1 4
2 1

output:

4 1 0 1
2 
0 

input:

4 1 0 1
2 
0 

output:

1

result:

ok 

Test #120:

score: 55
Accepted
time: 6ms
memory: 5904kb

input:

2 2 1 4
1 2

output:

4 2 0 1
1 
0 

input:

4 2 0 1
1 
0 

output:

1

result:

ok 

Test #121:

score: 55
Accepted
time: 6ms
memory: 5872kb

input:

3 3 3 4
1 2
3 1

output:

4 3 0 1
1 
1 

input:

4 3 0 1
1 
1 

output:

3

result:

ok 

Test #122:

score: 55
Accepted
time: 6ms
memory: 6072kb

input:

3 2 3 4
3 2
2 1

output:

4 2 1 2
3 1 
0 0 

input:

4 2 1 2
3 1 
0 0 

output:

3

result:

ok 

Test #123:

score: 55
Accepted
time: 2ms
memory: 5968kb

input:

3 1 1 4
3 2
2 1

output:

4 1 0 1
2 
0 

input:

4 1 0 1
2 
0 

output:

1

result:

ok 

Test #124:

score: 55
Accepted
time: 2ms
memory: 5952kb

input:

3 3 1 4
1 3
1 2

output:

4 3 0 1
1 
0 

input:

4 3 0 1
1 
0 

output:

1

result:

ok 

Test #125:

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

input:

3 3 1 4
3 1
3 2

output:

4 3 0 2
1 2 
0 1 

input:

4 3 0 2
1 2 
0 1 

output:

1

result:

ok 

Extra Test:

score: 0
Extra Test Passed