#2357. 字符串问题

    ID: 2357 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest401来源:qoj.ac数据:公开样例字符串并查集

字符串问题

字符串问题

题目描述

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 字符串问题(string) 【题目背景】 Yazid 和Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基 本概念。 对于一个字符串S ,我们定义|S | 表示S 的长度。 接着,我们定义该串的子串S (L, R) 表示由S 中从左往右数,第L 个字符到第R 个字符依次连接形成的字符串,特别地,如果L < 1 或R > |S | 或L > R,则S (L, R) 表 示空串。 我们说两个字符串相等,当且仅当它们的长度相等,且从左至右各位上的字符依次 相同。 我们说一个字符串T 是S 的.前.缀,当且仅当S (1, |T|) = T。 两个字符串S, T 相加S + T 表示的是在S 后紧挨着写下T 得到的长度为|S | + |T| 的字符串。 【题目描述】 现有一个字符串S 。 Tiffany 将从中划出na 个子串作为A 类串,第i 个(1 ≤i ≤na)为Ai = S (lai, rai)。 类似地,Yazid 将划出nb 个子串作为B 类串,第i 个(1 ≤i ≤nb)为Bi = S (lbi, rbi)。 现额外给定m 组支配关系,每组支配关系(x, y) 描述了第x 个A 类串.支.配第y 个 B 类串。 求一个.长.度.最.大的目标串T,使得存在一个串T 的分割T = t1 +t2 +· · ·+tk(k ≥0) 满足: • 分割中的每个串ti 均为A 类串:即存在一个与其相等的A 类串,不妨假设其为 ti = Aidi。 • 对于分割中所有相邻的串ti, ti+1(1 ≤i < k),都有存在一个Aidi 支配的B 类串, 使得该B 类串为ti+1 的前缀。 方便起见,你只需要输出这个最大的长度即可。 特别地,如果存在无限长的目标串(即对于任意一个正整数n,都存在一个满足限 制的长度超过n 的串),请输出−1。 【输入格式】 从文件string.in 中读入数据。 单个测试点中包含多组数据,输入的第一行包含一个非负整数T 表示数据组数。 接下来依次描述每组数据,对于每组数据: 第4 页 共9 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) • 第1 行一个只包含小写字母的字符串S 。 • 第2 行一个非负整数na,表示A 类串的数目。接下来na 行,每行2 个用空格 隔开的整数。 – 这部分中第i 行的两个数分别为lai, rai,描述第i 个A 类串。 – 保证1 ≤lai ≤rai ≤|S |。 • 接下来一行一个非负整数nb,表示B 类串的数目。接下来nb 行,每行2 个用空 格隔开的整数。 – 这部分中第i 行的两个数分别为lbi, rbi,描述第i 个B 类串。 – 保证1 ≤lbi ≤rbi ≤|S |。 • 接下来一行一个非负整数m,表示支配关系的组数。接下来m 行,每行2 个用 空格隔开的整数。 – 这部分中每行的两个整数x, y,描述一对(x, y) 的支配关系,具体意义见 【题目描述】。 – 保证1 ≤x ≤na,1 ≤y ≤nb。保证所有支配关系两两不同,即不存在两组支 配关系的x, y .均相同。 【输出格式】 输出到文件string.out 中。 依次输出每组数据的答案,对于每组数据: • 一行一个整数表示最大串长。特别地,如果满足限制的串可以是无限长的,则请 输出−1。 【样例1 输入】 3 abaaaba 2 4 7 1 3 1 3 4 1 2 1 abaaaba 2 第5 页 共9 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 4 7 1 3 1 7 7 1 2 1 abbaabbaab 4 1 5 4 7 6 9 8 10 3 1 6 10 10 4 6 5 1 2 1 3 2 1 3 3 4 1 【样例1 输出】 7 -1 13 【样例1 解释】 对于第1 组数据,A 类串有aaba 与aba,B 类串有aa,且A2 支配B1。我们可 以找到串abaaaba,它可以拆分成A2 + A1,且A1 包含由A2 所支配的B1 作为前缀。 可以证明不存在长度更大的满足限制的串。 对于第2 组数据,与第1 组数据唯一不同的是,唯一的B 类串为a。容易证明存 在无限长的满足限制的串。 对于第3 组数据,容易证明abbaabbaaaabb 是最长的满足限制的串。 第6 页 共9 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试字符串问题(string) 【样例2】 见选手目录下的string/string2.in 与string/string2.ans。 【样例3】 见选手目录下的string/string3.in 与string/string3.ans。 【样例3 解释】 这个测试点满足【子任务】中提到的|Ai| ≥|Bj| 的限制。 【子任务】 na nb |S | 测试点 m |Ai| ≥|Bj| 其他限制 ≤100 ≤100 ≤104 1 ≤104 保证 保证所有|Ai|, |Bj| ≤100 ≤1000 ≤1000 ≤2 × 105 2∼3 ≤2 × 105 无 = 1 ≤2 × 105 4 = nb ≤2 × 105 5∼6 ≤2 × 105 保证所有rai + 1 = lai+1 7∼8 无 9∼10 不保证 为了方便你的阅读,我们把.测.试.点.编.号放在了表格的中间,请你注意这一点。 表格中的|Ai| ≥|Bj| 指的是.任.意B 类串的长度不超过.任.意A 类串的长度。 对于所有测试点,保证:T ≤100,且对于测试点内所有数据,|S |, na, nb, m 的.总.和 分别不会超过.该.测.试.点.中.对.应的.单.组.数.据.的.限.制的10 倍。比如,对于第1 组测试点, 就有∑na ≤10 × 100 = 1000 等。特别地,我们规定对于测试点4,有T ≤10。 对于所有测试点中的每一组数据,保证:1 ≤|S | ≤2×105,na, nb ≤2×105,m ≤2×105 【提示】 十二省联考命题组温馨提醒您: .数.据.千.万.条,.清.空.第.一.条。 .多.测.不.清.空,.爆.零.两.行.泪。 第7 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1
7
-1
13

样例 2

2
ccacbbbabbbbbccbcaaaabaacaabaacbbbbcbcabcabccbaaccbcbcccbcacccbbbaaabbbababacacabccbaabccbbaaabcbbbabcccaabbaaabcbabbabbbcccabbbbabbbbaaaabaccbbbccbbbccbabcbaccabbbccbbbbbbccacbbbacabaacbacabcbabacbccabccccccacccaaabbcbbcbcbcbbcaabcaccbcacccbbabaabaabbbacbcbaaaabbabacaabccacabcbaaacbaacababbacaaabaabaccacbcabccbcbaaabcccabacaabcbbbaaacabccbabcccccacacacbcaacbccbaaaaacaacbaabbccabcabaccbcccabcbcccbbcccbcabbcbcbbcbcabacabacbacbccaacabcacbaacccaaacabaaaccbbbababbaaabcaacbcacbacbccbabbbaccabbacabacbaaccacbcccbbcacbacccbbcbcbbbccbcccbcabcbbaccbbbccaaaabbacabbaacbcbaccccacbcbaccabccacbcbaabaabaacabaccaaaccccbcccabbaabababccbbaabcbbcbaacaccbccbbbaabbabbbbbccbbccccaabcbcccabbabbbaacbbbbacaaacbbacabbcabbcabbcbcbbbacbabcccccccaaaaabbbbcbbccbacaccbbbaacabbaacbaacacbcabccacaacbaaacabbcacbaaacabcccaacabcabcbcccaacbaaaccccacaacbbcaabaabcbbabccbbacbcccaccbbcbbccaccbcbacbccccbcbbbbcabaabcacccccbbbabccbbbbcccbccbaaabbcacbaaacbccbabbaabbbcbcacacaaacbacacbbcaabcccbbaabcacbbcccccccaacbccbabacbbaacabcbabac
1000
24 359
17 414
326 723
139 903
217 718
352 717
912 973
135 276
355 978
472 642
711 973
314 820
499 940
166 680
553 895
730 931
341 979
358 675
776 948
593 771
414 432
656 973
44 78
107 983
809 877
101 784
300 842
359 749
98 755
263 822
313 786
94 498
178 668
530 577
114 280
569 907
164 212
4 876
733 931
726 760
477 698
49 330
651 892
627 920
190 980
631 733
752 771
692 759
521 577
256 418
607 702
365 620
455 679
222 546
635 854
61 720
87 587
469 798
227 710
40 780
177 180
30 229
914 919
252 264
231 939
733 940
177 706
326 437
314 332
436 976
217 778
369 951
726 831
553 971
314 633
704 742
160 279
127 228
21 801
246 511
154 877
604 665
40 693
569 746
218 927
256 566
285 882
544 685
79 916
133 308
295 933
21 396
425 904
146 617
779 829
90 212
286 522
182 354
485 847
515 677
116 306
107 496
474 859
261 330
326 881
368 713
390 576
121 750
669 700
72 652
202 822
40 774
600 647
515 575
396 979
75 991
32 120
84 625
33 341
665 682
155 339
495 819
360 583
210 955
88 561
308 721
228 491
469 785
211 496
810 848
65 708
42 217
789 838
519 884
111 826
227 481
581 672
176 839
74 303
225 851
566 697
197 385
270 836
483 594
235 744
595 797
272 960
137 727
354 640
694 920
275 865
600 688
121 485
795 906
223 690
145 845
658 746
28 180
182 919
151 244
693 789
67 522
145 429
11 496
411 577
659 978
222 324
338 869
548 586
416 806
333 398
321 768
641 687
601 866
647 686
636 773
288 900
330 510
76 636
59 465
131 862
298 799
182 540
237 876
243 917
385 688
486 734
146 626
359 749
803 915
280 298
157 937
340 736
31 507
146 220
174 244
245 259
232 504
235 657
38 529
270 406
332 603
326 743
429 478
71 951
410 558
256 518
707 736
241 823
839 986
167 258
705 917
186 648
338 411
48 912
331 726
145 943
737 798
539 916
421 628
97 918
143 757
382 570
76 139
242 816
532 764
119 992
156 442
42 438
179 418
710 719
118 144
305 692
512 994
448 599
765 997
55 992
222 450
93 674
490 736
684 916
33 228
8 137
314 811
105 720
707 896
838 975
221 841
202 264
908 956
9 408
10 586
317 712
322 603
61 648
167 575
753 762
516 956
200 878
192 312
656 980
816 853
360 479
128 850
264 618
320 328
65 712
257 366
72 403
350 900
843 998
67 869
348 632
122 944
462 610
352 905
164 679
638 964
106 785
95 834
27 606
145 576
85 237
788 936
4 443
4 35
239 339
152 482
161 248
358 948
413 801
199 248
132 487
68 441
675 981
379 528
538 560
101 689
552 922
273 769
505 947
196 961
64 642
96 963
562 865
268 341
498 893
323 864
78 161
621 927
31 768
12 605
626 722
391 478
24 236
275 999
355 452
321 554
139 877
725 783
735 787
442 812
225 484
37 632
432 967
394 486
98 487
237 494
368 638
273 645
413 535
334 845
535 833
26 536
354 480
785 787
819 851
496 994
133 450
545 938
383 993
728 840
96 244
259 725
146 472
591 618
234 290
13 544
685 811
490 567
155 305
104 220
59 884
747 760
108 368
411 765
84 577
605 935
37 92
344 856
817 877
170 349
349 376
86 156
68 907
210 294
41 578
103 317
187 602
281 403
293 632
92 766
194 748
470 703
236 493
331 345
380 712
342 418
330 563
419 579
212 234
99 294
105 184
123 518
694 898
650 929
133 534
327 953
108 692
447 651
8 674
186 825
176 945
457 610
298 820
34 659
642 753
384 737
119 308
570 654
201 407
254 779
542 566
587 682
69 121
299 617
98 394
23 127
210 671
434 967
12 58
736 750
623 929
228 718
275 385
38 47
96 493
345 363
236 318
149 994
528 839
375 491
864 922
508 752
462 795
45 444
176 766
171 341
722 856
153 890
300 576
173 229
422 544
88 478
120 483
9 309
225 857
382 822
244 284
72 454
618 816
662 662
339 395
6 189
58 834
281 836
553 568
748 906
552 877
559 704
104 128
623 868
612 797
158 677
124 286
423 428
545 788
456 672
174 297
240 504
349 785
256 536
43 488
409 537
730 735
202 908
383 610
220 834
532 879
439 928
555 962
356 823
537 991
103 256
108 586
134 624
191 623
201 273
554 890
271 438
138 215
37 407
748 923
158 528
308 323
449 549
92 357
234 717
344 819
179 743
323 643
100 553
786 835
316 745
121 713
291 541
66 428
20 644
365 858
519 900
77 449
324 919
278 530
483 523
271 921
715 954
142 312
319 711
101 501
667 813
130 814
88 505
308 564
635 639
158 790
440 477
218 399
192 892
382 490
172 988
253 265
351 413
261 618
370 726
539 652
165 247
187 615
88 995
341 995
550 989
17 852
271 622
145 493
853 916
502 805
202 477
144 693
45 560
681 813
330 930
332 535
370 551
446 869
631 677
672 931
458 904
568 794
510 525
116 578
108 950
573 891
17 839
62 374
167 465
181 193
242 959
334 792
128 245
448 497
140 464
481 892
686 818
118 805
273 725
651 830
112 753
420 530
581 961
409 524
95 415
169 372
823 977
564 595
68 615
303 526
305 603
192 675
421 471
209 510
299 851
116 804
640 875
411 795
508 554
281 853
81 222
389 904
28 68
555 861
17 647
336 696
64 347
572 730
32 479
145 846
48 755
752 752
697 969
395 541
64 450
299 894
89 313
133 184
797 884
317 682
589 946
469 939
389 492
10 28
543 841
259 665
293 946
54 774
318 968
247 302
796 998
211 985
402 661
56 516
14 279
123 643
269 441
683 860
29 859
151 900
88 159
214 703
676 780
331 728
297 764
138 425
703 765
45 804
610 933
765 927
445 940
496 763
715 842
301 637
186 884
44 400
109 632
40 161
178 204
619 858
106 719
703 917
410 577
314 348
419 478
209 394
435 627
622 849
440 660
105 844
601 641
322 554
322 839
132 781
420 782
111 251
259 663
75 322
199 398
600 637
403 666
122 256
318 632
127 651
504 708
161 540
78 921
675 988
619 872
103 702
332 455
267 575
668 755
46 499
293 492
59 456
97 692
83 519
338 541
506 563
882 987
817 834
597 869
692 940
367 942
378 627
282 687
141 767
710 987
141 730
28 110
83 584
531 611
568 633
383 657
160 998
8 181
919 936
315 531
245 576
321 980
30 628
162 571
533 973
595 988
171 261
110 656
49 596
12 542
133 187
58 971
187 971
221 377
334 978
175 690
244 388
389 750
167 539
367 807
167 507
108 181
414 635
262 432
326 392
27 189
278 857
139 142
478 487
155 908
298 399
23 931
180 364
127 897
381 728
140 329
132 338
792 793
674 891
523 813
316 438
93 108
78 743
165 595
206 253
107 591
70 840
590 647
163 401
222 764
99 459
390 427
491 985
398 846
212 710
325 681
100 297
257 362
301 520
115 389
325 851
252 296
279 571
153 180
343 910
9 635
556 854
665 858
284 441
651 976
421 621
417 783
217 626
131 574
515 921
342 611
395 593
219 588
179 480
26 619
449 730
185 506
163 655
215 723
627 950
547 836
243 529
200 669
649 839
697 944
645 958
821 855
877 970
288 459
463 764
165 585
103 904
831 851
70 567
292 475
157 668
164 413
499 532
43 659
746 964
242 834
546 983
317 835
523 533
37 682
26 278
560 748
182 609
72 246
369 460
233 423
389 958
57 237
180 392
469 733
576 791
552 664
165 635
398 920
126 315
436 967
186 978
326 734
125 895
397 493
816 945
330 398
16 736
668 843
468 632
239 978
404 979
247 881
83 731
410 939
429 667
693 907
502 599
628 734
393 397
117 950
750 770
693 936
368 848
443 457
411 891
733 743
119 577
223 923
70 919
313 356
366 432
203 417
276 568
451 612
759 926
390 677
450 882
386 620
35 456
394 725
792 984
79 787
481 538
255 591
75 457
178 782
594 826
3 391
743 883
331 418
103 394
235 943
715 768
522 916
500 836
100 730
565 777
95 942
478 657
80 813
391 938
894 916
227 349
216 433
563 706
553 872
55 283
415 471
773 954
17 459
354 896
763 838
5 168
304 714
571 823
225 341
270 666
692 859
946 986
71 736
738 740
45 480
85 411
176 778
43 259
145 317
50 140
587 766
701 737
134 276
5 483
659 791
314 533
421 649
336 878
564 978
190 191
179 350
28 526
84 144
24 465
176 574
710 966
37 432
546 703
364 690
194 804
717 858
757 896
343 647
156 843
82 267
150 348
445 582
137 473
40 628
367 786
161 578
606 688
288 621
305 501
312 782
438 983
96 688
60 935
402 909
798 817
254 511
438 710
530 627
142 552
128 410
656 844
484 962
372 710
483 744
8 725
24 801
919 998
235 415
485 916
414 932
265 493
170 563
716 921
196 755
713 935
567 720
547 824
420 586
778 983
185 283
441 644
55 104
160 990
43 69
160 303
47 127
104 364
269 288
27 553
56 537
349 849
656 867
496 541
111 485
776 829
420 622
72 72
69 340
1000
324 795
378 665
133 618
169 648
433 836
888 975
744 780
160 527
336 601
562 912
651 661
34 311
552 710
14 594
322 400
165 402
273 606
418 760
94 684
474 799
751 885
232 574
762 868
291 489
726 896
223 813
191 861
43 157
111 379
560 713
477 857
55 508
373 842
220 443
398 665
305 437
443 794
94 949
160 769
82 157
442 737
86 710
154 473
201 803
373 698
216 569
125 397
273 580
248 929
96 394
83 628
174 555
555 861
598 815
69 674
332 947
301 845
667 726
65 545
517 841
180 691
220 522
28 164
363 601
260 378
750 773
882 957
305 809
639 813
360 716
199 959
209 996
168 859
848 853
116 496
799 902
82 958
285 940
105 263
207 274
230 596
589 635
402 943
215 705
561 898
102 981
720 783
597 827
75 491
99 539
315 916
309 749
20 815
247 386
468 566
376 660
905 977
172 521
243 987
22 126
146 616
370 516
101 949
335 900
309 421
560 732
551 702
417 708
459 629
439 489
21 273
267 858
267 521
289 334
124 880
228 314
265 427
138 190
201 877
680 745
15 377
623 762
124 887
636 674
501 746
33 379
199 436
567 995
285 394
701 809
736 876
131 755
196 228
27 883
555 969
381 578
319 753
712 732
286 598
107 657
110 625
147 715
234 544
413 834
302 317
597 670
307 586
410 546
57 652
694 973
588 625
94 348
488 610
338 818
43 315
40 553
322 967
174 767
190 285
235 669
319 347
653 953
18 134
678 841
832 836
609 884
52 690
4 742
299 810
420 533
260 910
39 380
167 318
567 723
15 527
15 305
26 672
38 81
280 397
176 520
76 905
54 903
55 666
1 672
583 691
875 954
207 465
102 845
17 129
378 492
342 835
807 814
384 636
206 864
72 772
591 663
276 347
191 853
253 642
442 995
99 230
669 969
439 937
659 870
157 884
580 762
100 195
877 979
592 656
486 763
230 519
318 596
97 498
79 880
499 691
597 922
803 807
290 444
189 372
453 975
807 892
444 457
367 712
429 612
222 744
363 817
140 171
463 534
473 760
406 715
626 925
119 735
530 802
87 996
581 648
628 761
425 509
690 888
50 79
282 341
215 286
616 868
214 637
61 775
59 710
7 713
482 983
314 834
113 807
38 528
272 433
312 532
591 835
695 909
338 515
113 475
118 632
128 441
575 618
101 814
38 548
965 984
771 786
11 180
752 942
377 941
663 937
509 676
92 100
43 328
793 928
486 728
189 244
658 994
106 541
533 553
364 697
819 860
111 651
223 361
502 752
484 656
225 775
228 743
67 742
261 532
197 819
455 839
91 882
566 983
311 698
245 762
388 446
154 182
747 935
34 780
571 780
347 861
7 771
407 444
148 606
454 918
129 544
237 838
260 960
560 732
422 575
77 233
131 334
245 865
17 331
277 886
465 865
391 906
105 149
293 476
623 735
154 596
425 954
525 657
294 861
254 427
175 962
350 437
599 811
85 917
260 906
201 397
702 705
750 803
230 454
36 608
741 863
375 861
96 272
123 900
523 802
579 855
273 998
605 848
515 697
555 720
269 534
132 433
147 203
141 456
268 711
201 917
124 358
419 478
93 288
148 691
130 470
245 502
220 860
638 856
242 406
304 843
308 462
651 887
520 647
128 289
588 609
589 992
78 910
70 421
413 888
115 456
227 731
714 943
63 170
790 829
68 385
548 804
790 813
475 555
172 853
113 240
732 820
132 494
241 628
682 928
133 569
91 178
214 567
751 925
705 980
120 247
372 449
743 980
521 636
833 911
549 799
869 883
196 472
318 814
111 171
92 420
513 840
251 946
146 956
407 518
170 185
424 681
46 784
488 620
582 851
491 788
271 818
333 919
651 887
351 957
241 703
82 227
544 710
328 611
19 533
189 623
47 779
761 863
192 753
192 514
219 244
340 887
428 637
420 601
104 258
8 714
727 945
273 469
425 523
595 972
605 887
498 559
131 256
314 947
122 620
674 853
4 354
771 827
192 795
562 660
140 481
261 545
684 917
619 929
225 987
173 811
242 833
22 814
392 925
60 315
505 603
77 347
319 656
710 887
403 690
702 716
395 461
237 595
729 988
78 284
499 700
4 851
524 551
40 651
340 646
884 940
52 921
18 950
618 640
899 992
619 806
815 943
76 433
179 236
326 748
552 924
25 969
188 1000
703 789
407 979
60 428
504 694
284 514
811 906
908 979
96 583
659 725
92 395
306 522
134 599
410 567
477 687
725 931
148 522
478 609
36 474
985 1000
703 779
726 884
335 513
35 602
172 244
347 374
529 725
334 888
200 991
756 798
436 542
95 728
637 914
509 583
361 974
340 759
179 577
468 540
96 225
198 592
57 726
36 118
50 696
128 391
217 727
41 890
269 905
648 697
286 335
315 615
420 898
729 877
227 272
548 771
101 459
355 540
534 870
295 591
73 971
5 751
147 299
211 605
151 160
398 901
350 858
655 684
312 747
775 948
197 636
470 554
398 982
158 621
275 652
45 646
168 740
93 965
493 829
543 766
547 780
101 875
335 658
295 791
270 888
737 761
325 959
146 816
156 643
812 844
208 719
37 454
264 753
401 858
591 853
858 932
115 313
688 741
473 992
342 395
329 382
436 775
529 851
535 760
261 514
514 974
288 813
406 685
599 662
272 516
386 537
108 435
176 455
150 776
354 972
237 850
257 723
384 565
239 476
516 656
242 779
11 382
291 879
514 892
621 928
644 699
236 661
125 700
257 582
485 659
347 605
892 971
824 961
557 861
710 713
506 787
315 725
480 523
3 656
298 360
358 471
667 761
502 774
696 862
76 714
377 482
100 813
522 982
574 997
437 722
729 984
16 959
346 535
48 888
45 766
25 112
281 720
48 971
153 916
631 750
656 882
3 965
137 175
27 848
124 973
681 686
171 525
94 508
76 212
206 527
251 516
611 790
718 926
545 914
372 928
312 630
342 894
25 271
72 883
163 933
318 849
56 456
512 646
439 968
282 466
171 283
409 721
215 579
612 616
291 723
874 935
640 831
134 597
218 622
258 499
188 306
353 705
36 600
705 736
332 338
749 787
98 693
628 815
342 496
198 931
224 706
641 642
132 776
18 622
151 380
220 736
168 327
165 278
502 995
22 844
247 847
668 955
102 325
108 637
751 860
533 969
120 816
173 237
63 698
507 793
480 768
100 606
326 947
668 917
557 602
7 610
483 823
325 592
325 531
284 834
345 632
87 767
141 403
200 952
238 578
565 975
292 969
673 732
502 679
419 538
147 237
115 747
581 992
388 781
573 994
42 134
494 828
58 540
645 660
491 808
877 901
168 363
468 513
403 587
520 995
549 835
301 669
546 686
208 516
468 791
53 395
208 703
87 797
498 881
120 348
279 765
65 547
67 541
216 639
215 590
468 470
144 808
156 586
490 806
881 922
750 772
812 926
407 950
230 802
171 970
655 818
98 792
96 681
238 988
188 630
528 712
946 952
748 816
681 971
101 344
233 700
481 678
489 765
434 822
90 917
219 730
293 370
110 817
206 777
775 851
198 833
472 603
410 587
195 310
464 948
729 936
589 907
258 768
331 898
276 805
199 935
78 670
304 887
434 544
715 764
36 451
319 471
318 380
453 653
698 871
341 792
229 485
294 767
415 683
526 766
876 940
193 847
13 579
570 639
700 878
113 168
313 689
105 861
703 993
119 673
476 628
868 908
737 808
325 414
526 570
253 768
155 649
112 578
216 729
120 470
98 733
189 392
737 738
74 735
356 535
752 928
127 605
105 331
21 224
207 605
822 942
385 960
108 946
443 516
41 632
42 721
829 911
681 817
200 250
424 957
45 824
137 201
596 787
462 924
402 999
238 328
341 448
312 405
93 233
204 986
299 682
188 550
515 778
300 429
34 517
414 765
211 400
540 873
829 842
453 966
66 966
60 438
9 372
161 906
441 883
556 978
558 563
301 639
391 820
487 754
177 783
45 709
599 833
753 993
131 498
640 894
660 955
171 757
273 561
148 417
160 791
68 916
319 594
51 580
292 693
818 922
416 961
554 777
162 208
48 753
235 500
238 395
227 487
100 860
93 128
35 988
416 440
489 868
159 297
99 840
346 961
684 917
399 919
645 897
36 862
170 441
291 415
7 503
487 868
258 599
329 869
2 264
55 872
559 651
443 673
342 403
62 470
112 871
570 977
116 519
506 630
45 88
419 685
716 881
25 234
120 772
475 865
575 665
612 760
306 696
155 202
20 685
611 975
377 742
112 908
539 670
206 757
163 406
307 778
37 561
98 454
229 379
489 815
46 618
848 998
498 744
320 590
496 884
488 750
386 446
336 922
180 950
394 562
466 477
82 445
130 704
131 639
379 924
302 324
86 762
496 574
295 415
666 864
81 582
674 693
259 808
503 857
548 600
21 110
52 418
428 580
658 972
577 938
743 967
3 711
1 298
556 937
708 782
325 505
76 80
140 923
348 413
599 995
62 922
219 549
536 624
263 919
6 310
238 395
508 741
99 548
110 530
329 391
300
606 723
138 815
914 747
905 182
110 347
718 102
561 236
891 464
642 364
324 395
724 910
664 874
396 28
363 530
82 927
35 359
250 951
69 38
366 942
508 653
746 702
285 975
987 419
665 140
652 579
712 693
415 874
823 868
989 330
397 353
858 760
48 490
216 594
911 290
134 900
683 274
956 97
63 350
750 751
481 894
619 835
532 612
392 804
747 925
670 148
348 584
685 64
543 884
163 960
722 727
30 570
546 464
241 809
936 278
726 755
821 90
848 33
940 814
972 239
946 865
572 387
964 787
503 306
454 770
25 702
627 840
218 388
926 483
357 921
316 244
599 5
819 443
610 944
899 15
590 776
568 124
363 613
433 613
621 396
216 177
851 327
270 865
198 789
155 799
579 878
430 515
150 207
463 799
91 252
567 178
977 243
704 66
198 333
351 138
321 48
962 19
224 943
871 567
470 451
163 913
328 610
844 159
853 718
572 873
832 345
706 588
763 220
966 15
426 479
313 719
385 66
783 494
634 186
58 646
39 24
876 347
640 475
625 422
434 822
518 213
693 652
106 272
936 447
159 775
514 144
237 584
823 912
372 172
670 381
427 577
244 305
146 338
367 5
336 466
656 82
770 663
349 24
729 307
250 151
631 183
28 970
469 592
137 997
452 643
696 699
342 948
433 898
40 986
320 282
143 15
955 352
11 507
917 721
276 472
518 801
720 425
177 508
999 211
67 28
163 149
275 329
463 948
554 846
434 271
511 376
216 474
551 722
790 765
568 35
127 548
121 889
720 690
424 935
213 534
751 450
774 56
924 105
753 757
755 930
733 661
986 690
776 942
568 669
150 354
107 571
286 203
990 787
747 766
595 737
276 805
626 506
344 975
830 857
626 498
440 931
412 641
379 836
323 304
283 28
791 916
946 164
765 520
649 466
827 841
223 341
424 115
305 754
830 533
142 988
268 96
982 738
636 701
86 963
445 211
211 445
510 872
561 50
672 175
302 220
439 384
880 831
101 597
23 972
267 624
224 407
700 634
351 550
48 270
921 10
98 604
139 834
462 914
955 138
627 197
513 779
664 389
433 203
607 262
663 397
915 955
127 932
959 213
945 906
876 273
430 365
70 15
297 504
356 886
589 767
402 782
638 379
156 5
414 342
530 579
576 353
835 601
89 177
527 180
383 49
325 32
113 504
845 999
521 571
339 761
258 221
312 933
794 578
663 765
901 667
505 679
147 332
902 32
479 778
433 44
205 304
334 288
728 736
298 577
149 214
295 701
271 432
651 510
984 530
300 599
96 79
242 319
765 697
960 147
544 801
537 464
135 306
643 966
301 464
35 632
458 878
77 759
152 845
573 510
411 449
671 521
ababaabccbaabccbcbcbabccccbcacbabababbccbbbaccbcacbbacaababaaccbbaaabcccbcaaaaccacbbcababcbbabaacccbcaabacaaaabacabbbaccbcbaccbccaaacccbacaccaacccbccaccbccbbbaacbaccaacbcacbcaaccaaaabcbcaabccbbaacaacbaaacbbaababcacbacaaccccccabbbbacbccabcbbabaabcbbabccccbccccaaabbcaabaccbaaacabcccbcaaacabbacbccbbababbacbcbaccbbbaacabbbcbaabcabbbabbcccabbbcbbbccccbccbacabbbccbcabcbbaaabababaabaabbbbbccbabccbacaabbcbabbccaccbcbabcaaabccacbabbcccbbcbbaaaabaacbacbaacaacaacbaacbbbaaacbcabaacbbcbacabbcbbbabcbcbbbbbaaacaabcaaabaccbccbcaababcbbccbcbcbaaabababbacbcababcbcbcaaccccbacccbbaacabaaccccacbbcbccaaaaabaababbcccbaabcabcabaccbbbbcabaccabbababcacbcccaabaaacbaacababaacccbbbcacccbabcaccbabbcbabbcbccabcbaabbbbbcabcbccbbcaccabaaabaabbacaabbacccbabbcbcaccbbcbaaacbbbabaaabbaaabbbcabbcabccaccbcccbbccccccbbbbccbabacbacbccbbbbaccbbcbaaacbabbbbaacbacbbabacbbbbcbbccabcbbabbcaaabacacbbbcaccaaccaaaccccabaccccabcaabccacbbcbbbcacaabcabbcbbcbacbacabbabbabbcabacabaacaacbccbbacbbccaacccbaabbccaccabbbbcaccacbabacbaabbabcabb
1000
624 1000
516 573
288 339
221 804
373 798
36 250
635 942
301 314
481 778
432 587
34 121
447 776
207 334
211 638
518 554
322 349
188 955
50 340
11 882
111 140
418 515
341 375
347 600
344 469
248 940
427 550
212 579
73 350
221 235
673 791
50 952
48 226
71 639
649 668
298 526
257 863
662 840
637 798
143 411
263 619
360 833
559 808
190 234
154 682
106 539
377 691
116 384
9 766
14 130
535 615
362 890
79 262
18 780
13 876
89 623
286 385
121 833
461 678
490 689
94 906
456 830
345 658
98 752
195 229
211 566
207 260
282 364
243 913
4 280
246 284
107 416
358 820
52 238
37 264
105 650
440 728
104 145
409 568
114 488
193 715
455 884
39 378
335 474
261 551
339 911
550 835
677 856
242 276
194 780
320 886
385 590
148 586
222 473
506 512
86 301
369 371
437 619
719 803
230 398
536 765
301 369
561 825
170 738
451 749
545 710
370 803
359 928
483 855
746 790
699 940
143 903
25 327
600 924
800 949
442 604
447 506
172 206
735 939
4 597
203 480
749 753
369 489
110 956
798 836
549 847
201 856
4 240
53 714
667 927
561 642
483 718
270 528
104 133
671 916
565 944
350 646
60 252
87 704
644 918
143 561
846 893
261 338
836 976
154 368
303 425
103 828
728 771
302 397
391 455
546 571
449 453
186 284
242 766
234 695
27 562
351 749
328 965
149 573
143 198
774 962
137 159
179 587
421 896
449 850
623 687
173 210
379 666
359 992
120 501
197 565
248 861
490 580
70 123
28 941
283 461
650 671
480 999
449 818
597 875
572 680
467 491
26 975
376 874
169 349
60 107
574 611
462 961
259 937
38 739
264 277
51 658
687 894
178 863
165 886
374 820
443 731
60 880
309 392
515 898
41 892
465 996
33 462
307 548
26 414
60 960
146 547
361 818
130 227
106 665
762 771
229 584
19 495
256 697
393 847
32 902
254 791
676 910
536 940
785 785
60 701
569 888
656 961
107 274
438 883
33 877
502 891
565 849
383 407
657 732
138 793
207 319
58 168
63 938
736 974
37 316
93 603
139 207
708 871
115 805
437 563
59 312
876 876
774 795
41 132
30 618
242 461
416 930
584 728
623 872
420 683
609 627
188 961
188 690
72 329
46 870
499 863
359 872
306 535
790 941
813 944
244 342
142 622
38 639
289 788
463 962
85 242
188 767
116 722
765 999
257 545
200 235
29 451
149 400
61 608
582 831
224 806
54 677
112 809
212 465
80 682
191 242
291 849
26 892
218 524
565 961
262 770
936 948
316 678
436 904
616 635
658 917
484 837
99 576
183 320
608 669
688 990
3 643
437 484
696 878
131 983
246 420
194 857
39 863
172 890
411 929
133 279
422 523
531 547
750 780
145 916
21 476
596 886
1 334
257 971
453 795
463 765
499 590
217 257
341 749
57 470
552 669
224 519
325 773
5 14
621 659
323 928
429 783
165 496
384 805
64 717
399 567
574 694
531 873
270 520
570 839
37 701
388 634
151 813
220 952
347 888
236 592
32 354
165 630
22 73
147 365
139 266
277 572
16 216
204 909
35 819
536 586
195 758
186 599
780 832
655 735
52 744
37 795
558 843
61 277
218 967
147 414
859 984
386 766
649 722
319 546
38 85
36 840
349 454
855 949
117 122
613 850
102 864
256 323
541 884
140 778
192 690
207 838
279 336
168 890
870 901
677 983
378 801
823 986
823 859
162 887
199 348
144 721
660 861
26 922
199 690
849 888
732 894
618 805
13 197
605 676
625 927
411 575
393 536
149 929
111 683
325 801
151 284
316 359
873 957
102 614
256 281
333 628
378 528
708 754
270 693
460 672
412 991
68 790
418 736
164 955
168 968
66 995
254 303
865 971
450 723
827 985
92 406
560 751
110 964
3 719
788 895
401 410
407 588
460 922
280 800
78 491
103 369
352 804
99 125
339 411
745 948
227 703
194 890
618 673
12 532
267 567
462 684
149 888
77 204
288 389
175 604
91 298
245 358
160 677
306 453
462 976
66 764
379 652
633 837
21 617
279 681
177 871
793 894
502 821
260 759
624 887
55 59
317 510
154 544
716 801
878 881
626 982
89 832
226 377
385 551
113 893
542 719
280 419
122 416
761 828
326 862
24 92
526 936
192 555
275 802
251 684
856 868
303 362
114 147
96 855
395 648
93 414
223 627
403 416
9 730
314 681
274 640
283 312
234 621
536 869
135 996
54 789
336 761
512 770
252 398
328 833
328 615
204 595
17 822
234 677
317 775
268 921
76 329
93 832
102 388
434 615
476 680
39 951
480 794
46 597
13 316
807 827
290 888
37 908
38 509
300 508
431 955
335 900
734 800
224 915
276 808
89 581
60 741
375 588
365 895
529 683
12 565
200 457
316 939
120 248
35 68
159 704
252 355
735 814
46 294
150 710
477 500
128 934
67 766
409 576
794 959
282 627
250 922
63 465
96 947
128 158
216 841
21 381
95 924
294 685
588 788
273 286
105 121
502 746
38 951
56 945
155 270
172 562
440 895
18 884
139 596
129 153
551 893
403 528
400 637
215 918
852 948
128 853
648 681
33 611
441 716
518 970
284 847
169 870
76 232
133 430
788 833
6 893
667 843
228 660
236 865
332 758
579 892
73 509
171 329
343 474
70 905
584 968
472 696
86 289
545 625
373 601
230 244
149 990
50 366
181 677
904 964
37 551
726 845
53 622
244 655
634 934
2 307
34 249
109 393
39 881
135 274
37 660
470 603
297 320
490 822
255 618
197 907
156 502
52 816
108 238
390 720
865 985
388 875
22 527
804 899
425 808
150 173
337 842
99 909
440 539
589 739
230 511
565 639
575 853
127 445
358 541
41 820
430 687
56 756
178 958
102 150
83 414
353 821
37 446
216 719
388 953
553 918
64 590
779 787
524 813
351 529
329 815
728 978
339 423
615 789
289 740
121 721
86 292
228 237
397 869
751 784
373 479
63 248
526 886
428 890
93 477
618 687
297 960
832 867
279 571
209 910
83 464
458 801
884 990
332 347
67 678
531 835
428 574
33 133
854 889
411 722
13 635
205 891
138 225
20 148
97 554
144 360
759 937
597 921
480 867
284 498
171 979
358 673
162 763
635 976
268 563
541 781
142 235
438 527
526 603
152 738
396 498
429 693
762 798
494 861
70 397
494 528
386 625
885 931
7 94
81 752
585 707
464 510
41 390
406 753
526 756
476 988
586 801
142 842
26 622
19 376
23 132
389 795
123 835
552 914
194 747
159 735
185 228
232 545
976 992
57 62
215 942
251 440
382 692
91 886
642 655
521 605
103 357
318 948
651 780
44 223
68 437
198 828
347 921
794 975
88 645
465 490
563 609
826 912
645 822
458 469
433 546
403 759
154 377
415 440
307 606
184 541
238 558
82 515
435 988
82 871
402 724
902 967
117 673
185 532
209 877
701 970
143 207
340 486
67 888
454 863
137 375
850 998
181 976
287 698
258 510
108 953
106 697
218 819
201 385
326 839
247 803
119 235
218 648
182 189
55 412
208 724
268 716
269 694
199 333
30 501
447 910
27 470
535 789
554 640
174 763
587 710
257 832
433 713
342 497
65 414
89 642
478 671
127 662
150 169
585 687
291 898
551 752
226 842
187 718
456 885
515 992
16 81
428 621
75 90
189 224
153 878
469 870
717 811
494 860
290 344
494 525
106 829
775 855
253 448
9 800
673 892
182 755
550 577
76 400
423 955
560 956
393 702
85 302
394 713
208 294
263 992
184 947
159 833
155 960
13 255
137 653
322 409
472 873
216 241
38 298
589 880
645 846
683 872
222 996
642 822
250 935
209 691
847 995
146 926
77 775
396 405
28 603
449 965
336 868
188 842
380 787
307 574
496 972
70 986
882 920
913 927
118 804
817 904
146 644
549 803
300 398
322 836
462 758
591 591
296 322
231 458
194 229
218 544
261 624
268 389
334 716
348 604
559 876
767 784
227 518
266 677
101 984
50 206
723 817
864 948
253 590
270 866
173 852
96 494
434 790
268 536
486 804
556 741
512 867
551 846
104 121
239 511
207 726
41 968
86 755
359 616
515 660
543 620
921 989
186 435
625 858
299 349
732 765
143 229
412 749
461 598
86 482
606 622
672 985
430 563
95 163
567 888
29 329
206 557
163 697
245 291
892 972
597 868
1 696
733 996
226 468
426 936
784 795
446 843
445 999
164 939
381 513
24 742
40 672
439 465
220 761
446 832
179 834
278 292
83 445
12 947
20 79
481 489
356 818
372 571
165 446
102 389
313 357
122 295
69 487
580 964
85 937
124 572
352 604
385 446
174 329
391 527
413 576
325 549
148 978
280 795
110 728
384 918
219 983
379 863
399 885
933 976
237 261
954 955
218 424
535 719
32 286
306 868
164 796
136 458
893 903
559 879
239 544
34 597
831 971
907 982
403 452
112 775
284 996
124 818
66 120
206 249
522 867
578 951
23 914
110 981
83 613
44 325
1000
11 220
536 661
350 431
708 909
143 604
154 586
354 586
556 857
309 1000
227 819
338 997
582 955
732 782
471 635
196 658
54 161
206 235
382 983
708 978
107 505
84 295
147 684
536 928
144 352
177 275
631 698
178 631
635 991
278 328
165 731
345 530
740 846
112 589
765 957
146 600
567 733
317 566
855 970
499 906
565 757
434 556
639 723
529 773
35 158
357 558
471 845
156 541
279 491
73 739
607 903
597 937
169 593
128 637
347 372
391 501
650 815
89 255
499 973
493 806
203 939
255 868
263 567
45 548
40 80
636 847
314 806
108 769
24 61
28 46
891 994
352 702
199 551
285 992
27 753
411 664
133 419
618 834
755 898
364 511
205 815
550 663
479 512
478 574
70 345
562 606
37 570
740 956
732 868
546 721
280 975
201 723
453 771
176 758
108 119
25 117
74 139
31 186
357 734
213 618
685 912
40 696
620 796
120 244
162 943
397 607
176 678
584 759
67 163
526 637
585 797
431 461
213 631
855 982
93 961
396 982
298 921
934 980
734 783
624 635
672 767
10 867
109 478
103 517
430 508
510 987
517 705
284 830
357 893
429 464
392 670
460 948
543 942
882 883
44 669
667 736
205 247
322 631
390 505
154 912
853 935
48 882
519 846
102 158
274 370
311 821
619 721
283 581
219 522
370 512
480 875
522 579
163 978
91 596
35 485
561 697
653 661
165 663
31 954
380 690
5 560
104 375
90 246
15 514
435 960
156 820
663 779
313 607
28 48
319 462
684 746
267 944
305 454
494 713
4 111
387 624
85 526
861 974
597 965
298 529
125 970
448 977
29 554
722 723
214 771
358 497
617 889
193 782
551 651
205 512
494 734
42 63
108 667
164 213
404 669
890 966
426 991
343 572
882 968
91 705
408 708
310 388
794 850
547 666
368 858
140 936
163 422
854 986
383 618
627 798
118 600
33 317
103 345
727 912
693 989
234 315
75 106
510 784
157 992
83 305
199 985
385 619
292 536
10 816
1 400
41 873
26 183
6 361
372 401
450 731
180 917
320 528
801 971
172 560
426 465
418 579
99 930
742 753
314 716
381 721
167 591
391 526
491 935
719 769
30 322
364 568
336 548
185 435
271 921
155 601
359 639
262 953
76 258
715 840
201 260
351 571
189 484
220 470
91 989
18 250
535 673
566 839
254 624
93 709
140 846
355 546
110 201
775 838
574 928
682 855
234 640
121 824
236 902
513 808
205 575
624 809
221 442
504 904
212 530
93 997
565 796
675 910
839 991
184 722
67 936
12 462
232 572
183 659
403 982
59 717
263 431
150 826
656 955
594 820
215 780
280 643
852 867
179 411
265 498
426 960
300 929
142 853
194 954
17 524
99 826
505 809
330 763
447 858
588 928
563 761
502 896
576 607
176 954
538 971
479 846
149 407
267 419
297 486
292 582
202 399
633 950
329 437
259 687
120 267
653 926
299 601
702 921
625 955
697 762
827 995
204 586
292 667
263 926
575 853
154 443
8 630
119 232
217 900
158 839
285 323
749 796
20 451
520 933
217 729
210 744
210 239
392 891
14 166
376 625
620 967
381 914
343 471
439 517
680 884
312 342
445 705
97 955
339 366
54 884
367 555
735 872
81 340
259 284
7 548
490 657
197 998
124 290
299 901
481 647
230 278
413 768
113 797
169 683
619 772
505 842
425 636
255 433
31 108
225 375
646 990
653 894
96 710
572 590
234 736
147 958
136 999
333 788
888 991
515 1000
106 981
128 555
70 626
346 935
525 869
3 348
75 771
375 433
141 533
48 701
317 754
54 906
602 810
33 218
127 931
121 815
161 495
265 960
111 407
207 544
251 265
537 947
20 575
241 642
725 963
309 768
466 884
15 93
439 812
192 459
162 326
485 556
59 871
323 473
16 310
315 798
463 688
6 393
496 784
53 807
798 841
308 383
64 678
645 929
686 765
368 640
898 964
44 613
378 749
446 463
276 675
837 902
575 893
358 426
856 905
571 936
111 322
197 515
300 644
525 977
150 599
282 706
357 450
308 547
802 931
252 480
372 702
526 772
202 273
257 981
452 901
371 748
149 279
218 615
326 510
253 279
626 950
359 766
396 853
208 555
288 709
643 885
599 839
176 239
446 477
217 984
60 841
126 291
226 887
21 651
94 283
310 891
191 214
217 851
308 441
209 930
122 805
471 508
87 582
103 922
836 906
463 708
3 879
183 505
167 689
349 953
244 973
491 766
575 822
42 262
25 978
577 681
617 922
438 532
41 444
370 599
653 764
92 887
29 331
757 930
493 859
785 808
609 625
226 479
224 333
187 272
404 638
190 345
678 714
162 166
248 328
328 727
624 919
448 616
369 496
25 857
551 699
25 545
308 657
638 727
516 820
438 581
62 565
352 576
234 957
56 676
482 922
161 434
4 955
531 871
638 693
863 980
356 834
557 731
373 605
152 344
130 946
184 689
98 997
776 873
187 893
143 766
575 802
163 713
10 357
52 320
904 967
490 760
662 710
845 991
236 820
529 536
272 746
534 726
58 505
336 975
386 744
476 488
824 944
265 786
315 391
452 686
48 484
396 579
555 800
141 185
431 793
98 797
102 188
189 600
342 924
546 968
155 836
199 202
212 317
301 843
369 687
480 934
629 975
769 976
33 243
713 828
356 870
175 475
131 944
455 582
112 459
123 896
135 997
381 830
142 958
15 389
42 204
648 849
737 988
53 764
570 669
30 437
517 792
116 216
304 598
753 920
431 469
137 298
615 773
72 180
122 918
622 926
91 443
677 859
281 783
350 401
261 383
142 255
277 318
326 638
359 933
40 380
77 571
41 166
141 168
715 910
226 853
299 527
629 875
143 566
685 760
366 957
112 706
155 259
240 322
121 855
17 897
593 819
306 716
274 520
407 778
380 681
817 981
521 797
176 211
614 931
444 895
314 634
97 953
148 401
742 789
114 897
470 477
105 938
369 476
178 824
746 820
128 815
388 892
955 981
430 539
548 950
823 932
151 669
410 515
568 985
480 854
507 793
25 629
757 905
946 996
637 987
235 458
147 595
389 398
83 589
226 494
65 103
320 742
13 684
486 754
610 697
464 978
772 934
732 878
244 604
222 827
656 660
546 843
722 977
141 436
734 974
209 216
426 915
56 281
184 618
242 571
551 908
514 942
655 808
217 719
319 376
358 543
72 213
570 845
534 664
417 943
697 919
12 528
447 639
158 281
78 358
635 705
169 792
38 138
441 823
78 977
125 943
722 722
735 790
378 874
81 125
85 844
117 339
675 734
177 982
215 839
515 527
309 536
78 446
60 621
763 949
691 702
58 501
475 737
274 463
57 449
337 908
37 822
138 493
315 604
206 942
68 698
349 832
103 793
334 472
128 629
61 232
479 949
286 618
236 306
129 260
463 882
824 1000
258 933
256 787
129 757
48 424
325 492
201 758
87 965
159 534
367 715
240 936
155 886
462 536
231 482
683 778
333 813
334 844
106 435
531 706
194 238
750 891
613 849
387 947
375 707
474 536
40 857
703 954
631 640
444 997
50 348
935 980
210 587
278 308
407 798
576 581
161 427
152 632
209 467
697 803
321 385
30 774
751 795
37 394
271 688
17 58
162 643
974 993
384 737
71 680
73 422
336 874
666 895
95 878
316 607
152 447
38 182
640 652
128 252
492 960
290 863
266 554
59 475
641 864
365 931
562 792
625 865
163 531
411 693
279 816
690 875
866 885
35 556
326 468
205 619
819 843
470 983
462 691
304 360
591 650
582 746
517 630
248 719
249 774
450 919
905 927
870 995
179 539
55 565
157 984
232 990
686 944
156 670
149 510
388 577
290 948
100 614
572 693
210 235
577 932
105 874
89 788
189 209
593 681
683 704
320 479
67 314
498 546
229 557
73 379
949 974
438 459
602 964
210 228
336 893
357 532
85 803
121 744
182 343
448 484
181 399
852 881
74 925
346 461
95 516
387 791
550 813
113 369
742 934
189 994
542 562
460 696
222 759
384 962
748 881
197 414
300 826
216 618
4 85
183 480
266 668
479 856
32 796
251 557
74 513
456 919
72 541
419 848
532 985
81 168
210 789
709 948
85 789
171 794
445 970
123 284
800 810
361 560
504 583
39 494
556 568
376 709
585 929
74 375
12 251
378 652
218 554
57 211
72 152
180 482
54 559
468 976
470 667
187 678
635 994
641 734
145 446
597 603
340 669
619 634
284 533
195 470
415 691
683 722
226 638
607 709
742 888
428 634
38 947
167 807
696 707
196 267
192 867
107 462
285 965
175 919
621 713
123 678
139 991
73 258
301 396
723 796
304 784
360 990
579 903
157 741
274 458
157 343
112 218
644 972
265 596
107 562
806 864
94 770
20 391
16 96
374 855
689 728
381 446
92 608
308 618
310 581
246 800
426 445
167 179
7 829
186 913
611 935
134 968
274 465
514 796
264 834
555 935
503 729
723 855
871 912
476 688
540 942
841 897
171 933
391 692
507 908
661 764
385 547
300
698 544
382 866
552 548
748 193
610 176
1 98
478 909
707 887
859 692
255 873
244 310
651 83
388 906
644 493
868 937
756 652
559 102
603 919
895 370
457 557
846 924
582 378
378 621
710 913
605 624
269 474
128 16
410 252
164 501
3 262
885 990
645 456
316 162
725 943
567 186
56 293
279 814
252 302
149 720
57 174
873 709
424 913
385 391
926 723
899 759
212 894
400 536
671 769
548 207
31 549
286 607
710 827
776 626
310 49
291 129
79 428
427 684
221 768
26 749
706 690
276 270
685 6
55 99
430 892
572 962
996 597
398 847
398 564
318 708
82 160
985 190
29 958
959 938
680 203
640 510
627 207
604 653
576 28
999 690
151 910
216 502
714 373
85 476
348 293
701 305
155 895
697 945
558 448
56 700
124 887
621 768
308 660
47 472
675 388
581 634
925 369
780 743
315 406
382 3
45 600
929 324
772 880
713 647
278 926
138 757
455 991
623 509
145 303
512 724
688 833
988 911
821 114
651 89
724 534
965 864
268 971
5 409
778 154
700 764
410 884
315 770
196 408
305 818
343 946
164 948
660 408
784 877
570 390
89 865
633 9
575 158
341 888
245 620
305 175
846 795
85 174
389 406
382 862
654 563
193 411
815 284
28 92
221 687
432 447
908 17
934 194
678 394
133 325
935 362
662 307
387 890
628 192
661 420
875 588
149 284
300 380
348 24
322 746
151 563
804 539
502 679
487 206
352 216
23 237
21 622
243 923
887 675
730 318
766 915
565 502
351 752
51 715
40 53
51 829
178 643
185 540
947 871
48 192
880 308
32 91
692 53
956 899
727 187
884 700
125 532
138 993
129 677
90 283
246 966
523 314
299 91
244 776
857 708
69 613
626 114
747 757
47 65
783 46
989 365
76 110
910 541
60 849
480 949
94 135
820 655
957 20
21 145
944 881
370 402
9 457
330 197
581 70
299 824
71 865
799 943
153 272
620 745
200 753
558 572
322 149
187 405
543 608
899 295
361 645
74 5
746 343
916 363
769 761
308 493
224 231
520 307
12 430
108 685
26 678
25 320
107 416
978 915
20 938
387 531
84 295
119 1
506 83
244 62
995 476
221 437
165 477
348 350
787 220
522 315
598 899
540 811
540 564
491 317
207 29
689 62
429 986
731 107
367 722
447 210
408 274
523 323
380 742
7 940
322 190
273 385
976 925
923 931
153 252
827 583
822 93
743 943
590 108
450 102
443 623
728 813
75 207
2 235
911 143
654 193
852 88
926 882
827 143
875 426
967 358
102 686
235 815
810 41
725 136
10 871
307 503
395 361
608 751
773 225
923 971
827 144
949 983
532 771
749 102
246 68
249 445
2273
-1