P21411 [HackerEarth] See Russian Translation
普及
题目描述

See Russian Translation

David is playing a video game set in a dungeon. The dungeon has n interesting points and m one way tunnels connecting those points. The i-th tunnel starts at point ai and ends at point bi and takes ci units of time to traverse. Note that it may be possible that there are two tunnels connecting the same pair of points, and even more strangely, a tunnel that goes back to the same point.

David is currently at the point labeled 0, and wishes to travel to the point n-1 using the smallest amount of time.

David discovered that some points become dangerous at some moments of time. More specifically, for each point, David found an integer oi such that point i is dangerous at all times t satisfying t = oi modulo p. The integer p is the same for every single intersection.

David needs to always be in constant motion, and can't wait at a point. Additionally, he will always be safe in a tunnel, but cannot arrive at a point at the moment it becomes dangerous.

Help David determine the fastest time he can reach his destination.

Input Format:

The first line of input will contain three space separated integers n,m,p.
The next line of input will contain n space separted integers oi.
The next m lines of input will each contain 3 integers ai, bi, ci

Output Format:

If it is impossible for David to reach point n-1, print -1. Otherwise, print the smallest amount of time it will take David to reach n-1.

Constraints:

For all subtasks:
0 ≤ ai, bi ≤ n-1
0 ≤ ci ≤ 10^9
0 ≤ oi ≤ p-1

25 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 250
2 ≤ p ≤ 50

30 pts:
2 ≤ n ≤ 100
1 ≤ m ≤ 10000
2 ≤ p ≤ 500

30 pts:
2 ≤ n ≤ 50
1 ≤ m ≤ 2500
2 ≤ p ≤ 10^9

15 pts:
2 ≤ n ≤ 1000
1 ≤ m ≤ 10000
2 ≤ p ≤ 10^9

SAMPLE INPUT
4 5 5
1 0 2 3
0 1 8
0 2 2
1 3 5
2 3 3
1 2 6

SAMPLE OUTPUT
17

Explanation

The shortest path here is 0->1->2->3.
We can't take the tunnel 0->2 immediately, since point 2 will be dangerous at time T=2.
We can't take the tunnel 1->3 after 0->1, since point 3 will be dangerous at time T=13.
Instead, this roundabout path is the only way for David to get to the exit.

输入格式

见题面

输出格式

见题面

样例输入
50 1390 427454131 281371255 327880013 348941102 26506187 251404222 176197053 218225724 103272068 418728373 320636075 87380655 48232189 216055410 123527093 14044052 364502584 406461048 403903021 421741103 105953586 26692844 280704514 377018056 202577683 82798833 423871358 348541674 328045242 324544923 348359142 164035135 396863300 111924195 369530399 57259081 374210598 117160617 98370283 136367841 324981450 332157318 223686331 330645592 231766467 72626830 57298673 228742771 86680523 21390051 30678996 26 4 644346220 4 4 448110256 1 4 503261255 23 26 447256573 23 26 501430666 41 14 284188279 23 22 725195635 4 4 948008886 0 41 900151283 0 1 484374634 22 0 268073888 14 22 858110658 4 14 229501861 22 23 24219118 26 26 586701775 23 41 805299199 14 41 39542904 4 0 668298402 23 4 715244395 3 10 915592985 1 4 379003110 1 0 18741833 22 14 799857450 0 26 425847086 23 1 58816221 41 26 12247028 4 23 324813240 4 14 921658787 22 41 968132433 41 0 324168030 41 0 581602718 41 4 8648497 0 22 558683796 22 1 817926709 26 26 257580224 41 26 928816977 26 23 802581939 26 0 496368836 22 0 8255306 41 0 438184251 26 26 544262835 41 41 609257903 1 0 889396624 41 41 727175071 22 4 464307588 23 41 773022865 26 14 274469959 0 41 156652817 14 22 961980987 4 4 788323814 26 26 592601214 4 22 515445891 22 4 860988905 1 1 826318551 22 0 583438658 14 23 104962037 1 23 105365038 0 26 771640590 0 41 401520610 14 23 279889826 41 1 237963389 0 26 817286329 1 26 970141957 4 22 522170017 1 1 245599821 41 1 353252477 4 26 528104258 26 41 590295625 41 14 63443779 22 22 873651705 1 0 720672219 4 23 92550242 41 0 497427837 26 23 579192750 26 26 135413412 1 14 234452521 41 26 960079248 1 1 653127911 26 23 217931054 14 0 123201876 1 26 506664409 1 4 8233388 41 14 843243752 4 41 237483049 4 26 858911068 22 23 851036130 4 23 299974170 10 20 366626553 14 22 590160923 22 4 712585476 1 1 761594753 0 14 263944507 0 41 522616033 22 14 682801706 26 23 705991861 4 41 291144624 23 0 510875276 26 1 293767656 0 26 297050886 1 23 104899965 1 41 610803625 26 0 82932427 0 26 151061287 1 26 566579150 1 26 561993033 14 41 370259007 14 4 325298468 1 4 434698487 1 41 476601417 1 1 962586202 23 1 875681162 4 41 701904401 1 0 549449446 26 26 531292766 26 1 911101203 1 14 847524558 1 4 247186639 22 22 861644195 26 0 412508074 45 16 776244309 23 4 879652315 14 1 597036486 26 26 462004390 4 4 82067504 26 26 355034666 1 14 868815603 14 4 131592756 4 23 121563529 26 23 104088608 4 26 310374351 14 14 995536647 26 41 59613733 22 23 889397448 0 14 378495294 23 4 572293339 41 26 741435857 26 4 152868169 26 0 472092697 0 26 896871536 0 22 772450883 1 41 66210682 22 4 946860004 26 4 905589566 0 41 847937670 0 26 246845779 1 22 455762764 23 1 995529965 17 30 614970084 0 23 365656835 1 14 546649903 41 26 710935296 1 14 683036210 23 23 275188151 26 23 720243964 0 23 686225580 23 23 92051202 4 14 91201756 26 26 385669330 0 23 12288101 1 4 192705742 14 41 592182545 41 22 650000727 23 41 813422327 4 14 154297182 1 41 895828656 23 26 693897953 1 22 307174676 41 22 509125820 4 26 961228178 14 0 77886086 1 22 371367982 23 22 282317421 0 22 326688624 22 22 875374751 23 22 612515626 0 23 80709426 41 1 12125525 14 26 623802262 1 23 958277132 1 26 948190435 0 14 320985600 22 1 683764312 1 0 461217158 23 41 4336942 14 23 262934772 4 41 571050461 0 1 452404085 1 41 378768450 41 26 226828866 41 41 497931267 22 1 154720815 26 4 590885441 26 0 13227823 4 23 94947698 14 41 75453466 22 4 393504114 26 22 634326447 14 23 599059853 23 22 296631462 4 22 763528184 32 45 372710019 26 23 490897425 21 31 534760207 2 35 452111546 4 4 418713584 41 0 917226467 41 14 998360827 4 26 749011807 23 1 975966374 0 4 230119035 26 4 923269946 26 22 440434837 14 22 836112554 4 14 329882501 0 22 500595488 22 26 809267036 0 1 214870640 4 41 966219692 41 23 543244773 26 26 399447126 41 41 181261477 4 23 878637373 4 1 153076013 0 22 757548925 14 41 328529693 14 0 757330526 14 41 678232850 26 14 313846411 41 41 462368907 26 23 551699610 1 26 850609201 0 1 138489859 1 1 49572595 26 0 383858519 41 23 725744377 1 41 898503615 0 26 44256545 0 4 445334131 22 0 923736340 0 22 216287790 1 14 840115293 4 22 248349997 22 41 540822955 23 4 825046453 23 1 443981119 33 12 701250063 9 42 864820127 0 1 812536067 14 1 545939391 22 1 366386345 22 26 773470432 14 1 794461130 4 14 683090869 22 1 646534051 41 1 878510287 0 1 389996511 41 22 260635851 26 22 42986530 26 14 996925639 23 0 891618066 26 4 859588505 14 0 466709422 41 14 726413275 26 22 150601548 22 22 988700307 22 14 87414698 41 4 141917782 14 1 780279254 4 22 315564457 22 22 785866342 23 22 172608827 41 41 13148713 14 22 251169295 26 41 201942 0 4 325452740 22 23 947412632 22 0 524914963 41 1 774341031 23 41 283275372 4 23 834817195 26 23 242087104 14 14 731541901 1 23 476772138 4 1 133967110 23 1 797299989 22 4 550908859 4 23 461030758 26 26 639146638 4 41 101781902 4 26 309048430 0 14 244402016 28 18 97119224 23 41 932133314 14 22 477910912 1 14 979385737 41 14 658026645 1 26 122571422 23 0 881088621 26 26 436544370 4 41 797725999 1 0 906922471 0 4 745173603 41 26 512663043 23 0 743019923 1 1 626240087 0 4 839782721 23 41 724248854 0 0 30041310 37 43 988084246 14 4 543083133 0 41 30079044 22 0 82277729 4 26 927808111 4 0 826707570 26 4 899528640 22 14 945403418 0 26 642803127 1 26 725532836 22 4 620238292 43 34 252810545 26 26 470146614 1 14 88397117 41 23 322157927 26 4 706037970 41 0 414118898 41 14 449390848 14 26 85658366 41 26 8038687 1 1 427190409 4 4 400246238 4 4 713659778 22 23 906386607 26 22 735299747 23 4 583170882 0 0 967680798 41 23 129116751 14 4 393581030 26 23 900502273 4 0 418079104 22 1 514130200 26 22 969599658 4 26 860426133 1 41 800771178 14 23 217985572 4 14 856797019 41 14 833805967 22 41 783120213 14 14 500124325 23 23 418147228 14 26 328768816 26 26 265090054 26 26 50452370 23 26 541604084 14 0 101745643 1 1 203155223 26 4 304329943 14 26 560638430 22 26 227458168 1 26 604177529 15 40 822072787 23 26 195721762 4 14 888627718 26 26 793955914 1 41 11190486 26 41 604834926 4 0 897144937 4 14 172734223 4 22 159830291 23 22 187158012 26 23 948915614 23 22 708507222 23 0 861405324 0 4 333402533 30 49 293985090 41 14 162611726 14 0 403217993 41 23 145260489 1 1 322154154 26 4 895184736 22 23 585966314 1 23 159228585 1 22 478301197 22 22 38666411 23 22 627600710 14 26 549455805 1 14 245254434 7 47 837961150 23 14 591113872 18 9 753794632 0 14 5826848 14 22 595614122 41 22 543898401 23 23 477458845 41 23 511970307 41 1 23734547 0 22 904785579 41 4 772886550 23 1 377916883 41 14 360513690 1 26 181490135 35 5 656547752 23 41 16898814 41 22 514836014 41 1 737464337 0 26 684184280 14 41 430646865 0 1 156192983 4 0 901877784 4 1 481793601 4 4 510579005 41 26 869701852 26 26 815675548 22 22 869687943 22 4 445160046 41 41 135413956 14 1 214613395 4 14 322492451 22 1 271798377 0 23 489227137 41 14 826844119 1 1 861265156 23 23 469678217 41 22 987944993 26 23 502451438 0 0 777392982 26 14 765970004 1 26 97736759 41 26 703331632 1 41 84928726 41 23 549498 1 1 788252948 26 14 479024470 23 22 334492641 1 26 723003291 14 1 185627974 23 26 56460937 22 14 622614951 23 4 143017771 0 41 594749746 0 41 540367265 1 22 483370168 4 1 157190907 22 41 206089890 1 14 36531636 23 14 725254103 4 41 24847494 41 41 629288122 0 26 563993292 22 41 364218655 0 0 34383152 26 1 357406803 41 26 682128609 41 0 202836511 26 1 344774803 1 14 45071833 4 4 917526283 0 23 555996219 26 41 277568860 1 22 93469223 22 26 885712463 1 22 951258516 14 4 964817106 4 23 810056900 14 26 952014473 26 0 62679524 41 14 93896094 4 0 740653520 24 37 15388240 1 1 207499380 22 41 378493712 26 1 664976239 14 22 141476193 41 23 981366290 26 0 281499346 41 1 274495090 23 1 512935230 1 23 540517010 22 1 959043207 14 0 3025862 4 1 837754281 14 22 741858096 0 41 144136057 41 14 658398481 23 1 656931086 23 14 634540736 4 14 911302948 22 23 525299403 1 4 685792561 23 23 854986233 41 1 767292383 4 4 451124617 14 22 209217749 26 23 263143670 22 14 977996480 14 23 518074160 23 26 698457892 0 23 383679727 1 41 490969349 23 22 196563595 22 26 909436982 23 23 6818819 23 1 731080166 26 23 86133480 23 22 164338503 1 26 188785662 0 22 32635324 41 0 87357983 22 0 454950781 41 1 570052538 14 14 893345425 41 22 28761551 23 4 368945637 23 1 67096178 41 41 670021781 4 23 324199439 26 26 841475493 41 26 125625545 4 0 856306588 1 26 768062750 0 4 928922895 22 1 386395874 20 46 629320848 41 23 911594171 4 23 148774392 23 4 598133019 0 23 192804406 14 1 114327472 41 14 457206049 4 41 118036933 41 22 170991388 22 23 591463692 14 26 53269551 14 1 410872572 14 14 718919769 1 22 436838351 1 1 825459114 26 0 864061612 14 0 877527563 0 0 754713581 4 4 780348706 26 26 928700293 14 0 854917808 41 23 409140292 14 26 910095521 14 0 181010319 41 0 271252145 22 26 725435039 14 1 336587667 26 26 556793675 22 26 83078199 4 26 837911709 14 23 872180091 0 14 555186494 41 22 619762673 14 14 248255805 14 4 252713172 1 0 509300819 4 22 357582458 0 23 153579214 26 1 303854660 14 4 329274730 14 23 617294241 4 23 435642760 23 1 576276065 26 41 523100126 41 23 528607097 4 22 82136552 0 22 715266892 41 26 750908143 14 22 858929449 22 22 921788257 41 41 520438454 22 1 269736642 26 4 128847128 1 0 784673962 0 14 824973002 4 41 240681253 23 0 910574731 14 0 453467988 26 14 447014873 4 1 559948500 22 26 476375081 1 26 203660730 14 26 235319240 14 0 626100484 23 22 850190566 4 1 436593358 13 33 673173696 0 22 438583704 41 1 276106141 22 26 446760464 22 1 633861564 14 1 209932060 41 14 184723664 1 0 460891555 1 14 842174243 4 0 303263792 41 23 571998839 22 14 854063109 41 41 286824055 1 41 56843716 22 41 232619017 4 26 322190367 22 41 746664717 4 14 69906411 41 41 946554165 41 22 282745178 41 23 265619061 14 26 185101004 41 14 422759475 0 23 880662967 1 1 407055110 1 4 464910757 14 41 827369487 22 41 863668474 14 23 143410579 14 41 51528885 22 41 288672316 0 4 260161231 22 4 359674158 4 26 833964842 41 41 793966122 41 1 49763253 0 4 315351436 4 4 930438419 26 41 825900946 0 26 427384513 4 26 370410414 25 38 567221535 26 41 356353244 23 22 88444861 41 23 882107699 4 22 846180584 14 0 945043826 26 41 244001660 0 4 948811240 23 41 619807101 0 23 87165452 1 26 820619042 0 14 943969873 14 22 62022489 22 41 957880499 26 0 603585650 1 22 424933693 1 41 466965354 0 14 257788038 4 4 257113845 0 41 210454794 46 13 321565034 26 26 366683107 1 41 328199042 14 4 108263260 4 23 210466450 22 26 807913463 14 0 90169952 41 23 441229423 26 26 494818531 41 14 108278917 26 41 377482893 0 26 575957782 23 0 891218800 22 22 973891652 34 28 267152033 41 14 3484132 26 41 302322563 41 0 17824973 0 14 810853752 22 1 874671120 22 1 585599766 1 23 277527144 4 1 117251625 26 41 589261427 22 23 148083452 14 22 172953992 22 1 616182330 23 41 713306578 14 26 25367127 22 26 472500658 1 41 491726666 26 41 38436083 41 23 76316270 4 22 239479750 23 1 811716483 41 41 262006430 0 26 656329069 26 41 226485776 1 22 665131884 1 1 836832297 26 22 960821092 41 4 455427656 14 26 546297556 26 26 383987431 26 0 550586716 0 22 211576104 4 41 908358783 1 14 646009368 41 26 473082514 0 22 677251395 14 14 577164503 26 14 669631509 4 23 803727911 14 22 742065818 4 23 404957566 4 22 47071406 0 41 463649207 22 4 783281134 23 23 74262633 1 22 20895991 4 4 54402647 4 23 53931649 41 1 779422558 14 14 831139579 4 1 757736098 14 23 770204836 23 23 361975164 4 4 182471232 0 26 862846885 0 14 154112556 1 0 530411888 14 1 52421765 23 23 549247781 26 14 706816020 0 14 145642953 41 23 597588165 0 41 124131505 14 1 14079612 4 26 523419482 14 26 474616574 14 4 490994407 4 4 830819790 41 26 923115395 23 0 709125749 26 22 45793743 23 4 847177148 1 1 567754686 0 23 980606487 26 26 899598667 41 1 102959629 1 22 218618242 22 4 598381720 14 26 514822691 22 26 501029493 14 0 608362388 1 23 994516241 0 23 998298323 1 41 563069608 41 26 683459271 23 22 419304839 1 22 652981980 26 1 411376943 23 0 898967347 41 1 624494668 22 14 863708429 26 22 417315619 1 14 994980320 41 0 61920929 41 41 907754343 4 14 37393016 4 23 217438347 4 23 713703644 23 0 24842517 0 41 916943881 23 1 408467474 4 14 232328102 26 22 70751167 1 4 609840047 22 4 638447820 41 26 864355257 1 1 966570907 26 1 885955583 1 1 750122764 14 41 52552105 22 4 865625909 14 23 5320883 26 4 182772004 41 22 718424173 0 0 883030498 22 0 205783975 22 41 621442164 4 41 323821086 0 0 775094026 26 22 526012689 22 26 528819342 0 23 900876222 31 48 47691635 4 14 310972829 26 23 445717140 22 0 598287775 26 23 539964728 4 4 944583746 22 41 734723150 1 0 969807812 41 4 229252587 1 4 117518502 14 14 162745668 40 19 201131809 22 26 340694983 22 41 150268284 14 0 128985760 48 7 508195778 23 22 38904494 22 26 590416851 14 22 414736764 4 41 833488853 23 23 4703230 1 14 558282 1 14 220022726 1 1 759087096 14 4 177273141 23 41 90960916 23 26 126405501 14 26 328817171 23 23 802673905 41 14 56130221 14 22 663528985 22 23 903007714 4 14 81559393 26 22 947962042 26 41 168586864 22 0 556585117 14 41 530029073 41 22 867124075 4 26 652285094 14 41 530614869 4 14 697152591 26 41 926165906 4 23 723845494 14 14 454644697 4 26 172082578 4 22 82821438 22 23 998118729 1 41 560157803 23 0 46955254 14 4 454509838 1 14 384224698 1 1 401018360 1 23 753602780 0 1 279629988 4 0 697320821 14 4 540393804 14 26 863966003 4 1 245785857 14 1 264763606 4 1 597281308 0 23 876645882 14 14 87541125 23 1 819202480 14 22 46069137 0 26 642373560 26 0 346012676 4 41 68783932 1 14 349916702 0 14 526882703 0 0 604762745 14 23 904280672 41 22 429318578 41 4 377528903 0 14 558655975 23 0 348785038 4 4 119558643 4 23 561715648 41 1 572205391 1 0 990314810 23 26 240110294 14 26 433194449 14 26 518152723 22 4 984308180 8 24 946249643 0 26 914937157 0 23 499840095 4 22 658255452 26 41 271925219 0 22 621751137 1 22 163191495 0 4 391399447 41 1 951114068 41 26 200053021 26 26 406028507 4 1 500872825 1 26 221787964 26 22 294942145 4 41 818037574 41 0 226915158 41 14 887511638 22 4 970685937 4 23 444187874 26 14 678251066 23 41 711455215 1 14 634801799 22 26 624887019 4 1 505237546 26 4 699328689 41 41 968140865 22 4 232184070 12 44 711396214 4 14 862272305 41 1 279344094 22 0 351651620 1 0 699157051 23 0 489345447 14 26 491231684 23 4 742312955 4 14 916339202 22 41 422171055 4 1 656816093 26 23 192468460 23 1 645535536 0 41 946146935 14 41 611220314 41 26 812279165 22 26 470762396 0 1 478642801 4 26 397197407 0 23 562678611 14 4 452418078 23 14 993929379 41 0 117520734 14 1 280036249 41 26 985032131 1 1 776748716 4 41 981601594 0 22 628150469 41 4 553848571 14 22 777396632 1 22 244253618 23 23 544609986 4 23 935608886 41 1 404979388 26 26 600418962 14 14 286726779 1 4 220442720 0 1 418339225 26 41 76102344 26 1 762263389 41 0 920946507 23 23 647408471 41 4 195098965 4 22 644540234 26 0 545807586 38 15 227951533 4 23 845085196 14 4 500685280 23 26 659601733 26 4 258043994 0 14 989525335 39 2 451236666 4 22 237615196 14 1 833695298 44 36 471397967 41 4 949822348 23 41 65814413 14 0 476513791 41 22 141735280 41 14 678238262 0 0 834596431 4 0 881802502 41 1 725384123 0 26 609688208 41 4 271363539 41 0 996606646 22 22 327937137 23 41 858005150 26 0 637500523 1 22 661394180 14 1 378600797 41 1 208708468 41 4 283573537 0 0 115382755 23 41 315100537 0 22 56415354 41 1 108349629 23 26 43110990 23 1 459350494 4 4 967083641 5 27 151666865 41 26 661502207 26 1 118190282 41 22 651917717 6 29 556879859 22 14 40678664 41 1 369541329 27 8 945565932 0 23 866548372 26 14 135516269 41 14 321211924 14 41 119600362 22 4 105771357 4 26 38241920 4 41 957585560 0 14 729869765 0 1 748718093 4 14 796729376 26 0 966848793 0 22 370287644 41 23 374697466 0 1 35308619 1 4 754535805 14 22 426016673 41 23 727722673 22 4 812209726 41 4 268002663 0 14 37465530 4 41 268696013 0 0 19252235 23 23 814862471 22 22 338565537 14 4 574315562 1 0 758897898 0 14 209592810 14 1 646554444 22 26 765046586 26 0 252277107 4 41 461007779 22 41 594465247 23 0 708068971 1 41 361025682 41 41 574365572 4 22 686200486 42 25 948033497 1 23 105973861 1 26 909424863 22 22 405288995 4 4 950408258 41 23 158961664 1 1 626309721 0 22 340170991 1 26 449298048 23 23 591407594 14 23 367890774 1 1 2877781 26 23 192385857 0 14 546099721 1 0 502456808 23 14 433063214 14 21 274877666 1 23 291855273 41 4 757080706 41 1 792345012 22 1 167258341 23 23 582475300 14 22 192410053 14 26 63277058 4 22 132623274 23 23 161526649 14 41 947502951 23 41 480313786 0 0 256769585 41 41 407318080 4 14 692399437 41 0 102518795 14 22 54660097 4 0 474914457 0 22 569894895 4 1 508953435 14 4 803715018 23 22 397367452 4 1 121197149 14 41 497262209 47 3 791856145 22 4 649196376 41 0 565009662 14 26 586848276 14 41 684520915 0 22 461817138 41 1 250760472 14 4 388451704 41 26 669509960 4 22 20083676 0 0 796746825 26 0 877226738 14 41 924866835 41 1 813144940 41 1 718213467 0 26 472218611 4 0 156309494 4 0 258528925 23 23 275506964 26 1 502534471 4 4 479835479 22 23 791550769 0 1 795925534 0 14 36077918 26 0 398493888 14 1 213349124 41 0 556846123 22 23 366175445 23 0 466109625 41 26 816258510 22 41 784973545 1 41 428347052 22 0 591712959 23 0 782639402 4 23 486214781 41 4 19010105 41 1 984072110 0 1 993840717 22 41 640035360 0 0 194780463 4 0 354974513 41 4 86233254 22 0 832806926 14 23 348446779 0 1 360776913 1 4 558771212 14 4 397973980 41 0 996981751 23 0 46307124 1 26 240764421 14 23 235992674 22 23 230976372 26 4 669134259 23 22 540526050 14 22 243027599 26 0 75264458 23 23 67166254 4 23 832530677 22 1 674614930 22 14 516600204 26 14 981262771 41 41 819178686 4 22 330717684 26 4 904219509 26 0 967300554 23 23 932512328 41 4 294470762 41 26 244042098 22 23 728483898 26 22 962023249 14 23 243075964 0 4 904454821 4 4 949945298 4 4 123760029 14 0 879072349 4 1 65991553 22 23 343865644 23 23 474768108 0 4 255645803 4 1 978197966 41 22 531537731 26 22 267693622 26 26 480424993 26 0 35788482 23 23 149148092 41 4 677820898 23 23 23247411 22 0 359287838 26 41 738612879 4 0 437095011 41 0 575253354 41 4 646212248 41 4 18809496 41 23 234045381 14 1 268815619 14 23 390187209 22 4 329253358 22 26 65625793 4 4 277249951 41 14 846107231 22 23 20962557 22 0 753819116 23 26 785394056 1 22 100967587 1 23 905012576 22 4 413518723 1 14 673953933 4 41 117771877 0 23 773349782 22 23 807716128 1 23 372698305 23 26 846580716 23 22 546407345 14 26 452401113 4 41 726121130 26 23 672869738 0 22 301860128 14 22 343116520 22 26 974076205 22 4 264948144 4 0 365322441 23 4 553328532 23 4 770453923 1 0 467758068 22 14 147162041 41 0 496414235 14 23 755289763 0 1 696501170 41 23 698487426 1 0 568882412 22 41 123146311 4 23 268427058 1 14 501926983 1 23 441909726 4 26 318395931 0 14 302690692 22 1 284283172 4 14 660197662 1 4 795992983 14 26 681950062 1 0 465847199 1 1 777361085 14 22 723955824 41 41 802573672 1 4 699584522 23 4 134051287 0 14 496876522 14 14 479400189 23 0 857745013 14 23 58849869 26 41 854409739 23 4 516199612 4 41 615789870 26 23 247621293 14 14 342646029 14 0 549930401 14 14 773142808 0 0 733815020 26 22 795741396 41 1 179882823 26 0 507528225 41 4 138986588 0 26 361244712 14 0 77297967 19 32 5905989 26 26 213321383 23 14 130650999 26 41 682430959 41 4 478327704 22 26 694858250 22 23 158881161 22 22 349372410 4 1 713446474 0 14 403977116 4 1 728885821 26 23 943331450 41 22 434664306 22 0 156270618 1 22 386323191 14 4 340137654 0 14 470836745 14 26 748986109 0 26 355425516 1 41 116152632 41 14 433274428 0 4 644991486 26 14 375949865 1 23 229400981 23 4 280180940 0 23 284660797 0 22 808896810 0 22 371635850 41 4 24523165 4 22 43965780 23 23 293363238 41 1 396693567 41 0 3217143 0 14 364483096 23 4 408053757 1 26 306407897 26 22 30288245 26 26 248424010 1 1 977587488 14 23 132783145 26 0 132198060 22 23 508935234 14 0 407275832 11 6 169560855 23 22 63115276 1 41 75362241 23 1 775685527 23 41 523809121 23 4 249130053 4 23 442362626 1 14 342492510 0 0 808962118 4 1 593755194 14 14 676249845 14 14 21205469 0 41 964330627 23 23 157926223 26 4 236357956 26 41 362784058 26 4 568485362 22 23 147018665 4 23 100444355 14 14 704876859 26 41 164881986 4 14 79607154 41 1 584924642 26 14 803693808 22 14 222828835 23 1 420025984 4 1 612596075 14 26 67918215 26 26 905519680 1 1 525081930 14 1 524856134 1 41 604334194 23 14 188908170 4 4 738120688 41 22 840435858 14 14 28763725 14 23 817070474 14 26 304123887 23 23 876103061 36 11 785861244 41 23 748218551 14 1 595000819 26 26 207257675 4 26 909346129 41 22 39096376 1 41 122460651 41 14 918603124 1 41 256065522 22 1 53783769 26 22 254257608 29 39 403972116 14 41 539906974 22 14 936699837 4 41 308904273 1 1 177425013 4 41 139963010 41 14 642022821 0 23 856434779 1 4 20906969 0 23 615139823 41 23 71435214 1 26 191061283 0 14 297113223 41 22 608295012 22 1 785403224 41 0 299858405 41 1 240137226 4 4 89282583 14 22 252693923 23 26 661416988 14 1 459807395 23 14 447909358 14 26 575631532 0 22 742088900 16 17 852049013 4 26 824752589 22 14 462085219 0 26 128382751 23 41 975637811 0 1 850425698 41 22 600476717 1 41 224541414 22 14 622738922 22 26 626734211 4 14 12079574 4 23 228495740 23 14 855983016 1 41 327054909 4 22 72598972 26 22 501194271 41 1 513496158 26 1 389906403 0 22 920927983 22 4 659682969 26 1 73339363 1 0 549093384 26 4 547345831 14 14 150306828 22 1 985092881 0 0 462318111 23 26 748818275 14 1 131100497 0 0 104937116 23 26 404211860 26 1 765285000 23 14 911629002 4 23 742729043 41 4 812161325 22 4 33517481 23 4 229871089 41 22 471063135 23 22 399518858 4 23 422326052 0 1 393971679 14 0 442366306 0 4 617061609 22 26 526877128 26 0 531899946 23 14 594709680 14 1 926429513 23 41 266182436 41 0 110683068 22 41 584914001 4 14 843165925 23 22 499115019
样例输出
40636561179