#2399. 宝石

    ID: 2399 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest477来源:qoj.ac数据:公开样例最短路径树上算法

宝石

宝石

题目描述

全国青少年信息学奥林匹克竞赛 Day2(A 卷)宝石(gem) 宝石(gem) 【题目描述】 欧艾大陆上有n 座城市,城市从1 ∼n 编号,所有城市经由n −1 条无向道路互相 连通,即n 座城市与n −1 条道路构成了一棵树。 每座城市的集市上都会出售宝石,总共有m 种不同的宝石,用1 ∼m 编号。i 号 城市的集市出售的是第wi 种宝石,一种宝石可能会在多座城市的集市出售。 K 神有一个宝石收集器。这个宝石收集器能按照顺序收集至多c 颗宝石,其收集宝 石的顺序为:P1, P2, · · · , Pc。更具体地,收集器需要先放入第P1 种宝石,然后才能再放 入第P2 种宝石,之后再能放入第P3 种宝石,以此类推。其中P1, P2, · · · , Pc 互不相等。 K 神到达一个城市后,如果该城市的集市上出售的宝石种类和当前收集器中需要放 入的种类相同,则他可以在该城市的集市上购买一颗宝石并放入宝石收集器中;否则他 只会路过该城市什么都不做。 现在K 神给了你q 次询问,每次给出起点si 与终点ti,他想知道如果从si 号城市 出发,沿最短路线走到ti 号城市后,他的收集器中最多能收集到几个宝石?(在每次询 问中,收集器内初始时没有任何宝石。起点与终点城市集市上的宝石可以尝试被收集) 【输入格式】 从文件gem.in 中读入数据。 第一行包含三个正整数n, m, c,分别表示城市数,宝石种类数,收集器的容量。 第二行包含c 个正整数Pi。数据保证1 ≤Pi ≤m 且这些数互不相等。 第三行包含n 个正整数wi,表示每个城市集市上出售的宝石种类。 接下来n −1 行,每行两个正整数ui, vi,表示一条连接ui 和vi 号城市的道路。 第n + 3 行包含一个正整数q 表示询问次数。 接下来q 行,每行两个正整数si,ti 表示该次询问的起点与终点。 【输出格式】 输出到文件gem.out 中。 按输入顺序输出q 行,每行一个整数表示询问的答案。 【样例1 输入】 1 7 3 3 2 2 3 1 3 2 1 3 3 2 1 3 4 1 2 第2 页 共7 页

全国青少年信息学奥林匹克竞赛 Day2(A 卷)宝石(gem) 5 2 3 6 1 4 7 4 5 8 4 6 9 6 7 10 5 11 3 5 12 1 3 13 7 3 14 5 7 15 7 5 【样例1 输出】 1 2 2 2 3 2 4 3 5 1 【样例2】 见选手目录下的gem/gem2.in 与gem/gem2.ans。 【样例3】 见选手目录下的gem/gem3.in 与gem/gem3.ans。 【数据范围】 对于所有测试数据:1 ≤n, q ≤2 × 105,1 ≤c ≤m ≤5 × 104,1 ≤wi ≤m。 每个测试点的具体限制见下表: 测试点编号 n, q ≤ 特殊限制 1 ∼2 10 无 3 ∼5 1000 6 ∼10 2 × 105 m ≤300 11 ∼14 ui = i,vi = i + 1 15 ∼20 无 第3 页 共7 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

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