have to done in c language and has to be done C language. I need solution with the solution video and with the commands that need to run.
A2.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 2 (100%) In this assignment, you practice algorithm design, expression, analysis, and implementation. The analysis includes both theoretical analysis and empirical analysis. For the following two questions, please design algorithms, and express them in the pseu- docode that we are using (in the textbook and lecture slides), and then implement your algo- rithms in the C programming language. For each question, you are required to submit both your design in pseudocode and implementation in C, as well as algorithm analysis and comparison. 1. Counting Inversions (40%) Let A[0..n− 1] be an array of n distinct numbers. A pair of array elements (A[i], A[j]) is called an inversion if A[i] > A[j] for i < j.="" 1.1="" design="" a="" brute="" force="" algorithm="" to="" count="" the="" number="" of="" inversions="" in="" an="" array,="" analyze="" the="" number="" of="" repetitions="" of="" its="" basic="" operation,="" and="" determine="" the="" efficiency="" class.="" 1.2="" design="" a="" recursive="" divide-and-conquer="" algorithm="" of="" θ(n="" log="" n)="" to="" count="" the="" number="" of="" inversions="" in="" an="" array,="" set="" up="" a="" recurrence="" to="" analyze="" the="" number="" of="" repetitions="" of="" its="" basic="" operation="" of="" the="" best="" case,="" and="" determine="" the="" efficiency="" class.="" use="" the="" master="" theorem="" to="" verify="" the="" efficiency="" class="" you="" determine.="" 1.3="" implement="" the="" two="" algorithms,="" and="" test="" them="" by="" using="" data="" a2="" q1.txt,="" which="" includes="" 50,000="" integers.="" your="" programs="" are="" required="" to="" display="" the="" numbers="" of="" inversions="" and="" execution="" time.="" compare="" the="" two="" algorithms="" in="" execution="" time="" and="" theoretical="" analysis.="" a="" different="" file="" of="" the="" same="" size="" (same="" number="" of="" integers)="" will="" be="" used="" to="" grade="" your="" programs.="" your="" programs="" should="" prompt="" to="" enter="" a="" file="" name.="" 2.="" finding="" shortest="" path="" around="" (60%)="" let="" s="" be="" a="" set="" of="" points="" in="" a="" 2-dimensional="" plane.="" the="" convex="" hull="" of="" set="" s="" is="" the="" smallest="" convex="" set="" containing="" s.="" (please="" find="" more="" about="" the="" convex="" hull="" problem,="" especially="" the="" definition="" of="" extreme="" point,="" on="" pages="" 109-113="" in="" the="" textbook.)="" it="" is="" assumed="" that="" not="" all="" the="" points="" in="" s="" are="" on="" a="" straight="" line.="" the="" points="" in="" the="" convex="" hull="" can="" be="" viewed="" as="" fence="" posts="" that="" support="" a="" fence="" surrounding="" all="" the="" points="" in="" s.="" let="" s1="" and="" s2="" be="" two="" points="" in="" the="" hull.="" a="" path="" from="" s1="" to="" s2="" is="" a="" sequence="" 1="" of="" points="" in="" the="" hull.="" by="" viewing="" points="" in="" the="" hull="" as="" fence="" posts,="" we="" may="" consider="" a="" path="" as="" a="" sequence="" of="" posts="" holding="" a="" fence="" segment.="" the="" problem="" of="" finding="" shortest="" path="" around="" is="" to="" find="" the="" shortest="" path="" from="" s1="" to="" s2="" that="" cannot="" cross="" inside="" the="" fenced="" area,="" but="" it="" goes="" along="" the="" fence.="" from="" s1="" to="" s2,="" there="" are="" two="" paths="" along="" the="" fence,="" going="" in="" the="" two="" directions.="" the="" problem="" is="" to="" find="" the="" shorter="" one.="" 2.1="" design="" a="" brute="" force="" algorithm="" to="" solve="" the="" shortest="" path="" around="" problem="" and="" analyze="" its="" efficiency.="" 2.2="" design="" a="" recursive="" divide-and-conquer="" algorithm="" of="" θ(n="" log="" n)="" to="" solve="" the="" shortest="" path="" around="" problem,="" set="" up="" a="" recurrence="" to="" analyze="" the="" number="" of="" repetitions="" of="" the="" basic="" operation="" to="" compute="" the="" hull="" (for="" the="" best="" case),="" and="" determine="" the="" efficiency="" class.="" use="" the="" master="" theorem="" to="" verify="" the="" efficiency="" class="" that="" you="" determine.="" 2.3="" implement="" the="" two="" algorithms="" and="" test="" them="" using="" data="" a2="" q2.txt.="" the="" file="" contains="" 30,000="" points="" (pairs="" of="" x-y="" coordinates).="" your="" programs="" will="" be="" graded="" by="" using="" this="" data="" file="" and="" two="" points="" s1="" and="" s2="" that="" are="" in="" the="" hull="" of="" the="" points="" in="" the="" file.="" your="" programs="" are="" required="" to="" display="" the="" number="" of="" points="" on="" the="" path,="" the="" length="" of="" the="" path,="" and="" x-y="" coordinates="" of="" the="" points="" (in="" the="" order="" from="" s1="" to="" s2="" inclusive).="" your="" programs="" are="" also="" required="" to="" display="" execution="" time="" for="" hull="" computing.="" compare="" the="" two="" algorithms="" in="" execution="" time="" and="" theoretical="" analysis.="" also,="" for="" grading="" your="" programs,="" we="" request="" that,="" when="" a="" program="" identify="" a="" hull="" point,="" it="" displays="" the="" x-y="" coordinates.="" you="" can="" hard-code="" the="" name="" of="" the="" data="" file="" in="" your="" programs.="" the="" file="" (data="" a2="" q2.txt)="" will="" be="" used="" to="" grade="" your="" programs.="" your="" program="" should="" prompt="" to="" enter="" s1="" and="" s2.="" note:="" write="" your="" own="" code="" for="" this="" assignment.="" no="" code="" from="" any="" source="" is="" allowed.="" due="" time:="" 08:00am,="" monday,="" february="" 13,="" 2023.="" submit="" your="" work="" as="" a="" tar="" file="" to="" moodle.="" 2="" a2_guide.dvi="" school="" of="" computer="" science="" university="" of="" guelph="" cis*3490="" the="" analysis="" and="" design="" of="" algorithms="" winter="" 2023="" instructor:="" fangju="" wang="" assignment="" 2="" guide="" 1.1="" develop="" a="" brute="" force="" algorithm="" based="" on="" the="" definition="" of="" inversion,="" which="" checks="" every="" pair="" of="" (a[i],="" a[j])="" for="" i="">< j. 1.2 modify the mergesort algorithm to count the number of inversions. 2.1 develop a brute force algorithm based on the definition of convex hull. the algorithm is to find the convex hull for a given set of points. please see figure 3.5 on page 111. develop your algorithm to find the nails holding the rubber-band, that is, to find the extreme points. a brute force algorithm checks every point in the given data set to see if it is an extreme point (nail) of the convex polygon. an extreme point is an ending point of a straight boundary line. two points define a boundary line if all the other points are on one side of the line. please read • “convex-hull problem” on page 109 for the definition and an example of convex hull; • the definition of extreme point (page 112); • the equation of a straight line through two points (page 112); • the method to check if all the points in a set are on one side of a line (page 112). then design an algorithm to find the shortest path. • the equation for calculating the distance between points s1 = (x1, y1) and s2 = (x2, y2) is √ (x1 − x2)2 + (y1 − y2)2 2.2 design a divide-and-conquer algorithm of θ(n log n) based on the idea of quicksort. please read • “convex-hull problem” on page 195 for the quick hull algorithm. then design an algorithm to find the shortest path. 1 • you can use the algorithm of 2.1 for finding the shortest path. 1.3, 2.3 make sure your programs can be correctly compiled and executed on the linux system in socs. your work should be submitted as a tar file containing files like readme, design, p11.c, p12.c, p21.c, p22.c, makefile. please do not submit the data files. any compilation error or warning will result in a mark deduction. there will be some marks allocated for documentation. each file should have a comment at the beginning containing your name, id, date, and the assignment name. the readme file should contain the following: • name, id, and assignment number • a brief description of how to compile and run your programs. the design file should include the algorithms you design for 1.1, 1.2, 2.1, and 2.2, efficiency analysis, and comparisons. this can be a text, pdf or scanned file. in your c files, each function should have a brief comment describing its purpose. also, any section of code where it is not easily apparent what the code does should have a short comment. you can use timespec get() to get program running time. 2 1804289383 846930886 1681692777 1714636915 1957747793 424238335 719885386 1649760492 596516649 1189641421 1025202362 1350490027 783368690 1102520059 2044897763 1967513926 1365180540 1540383426 304089172 1303455736 35005211 521595368 294702567 1726956429 336465782 861021530 278722862 233665123 2145174067 468703135 1101513929 1801979802 1315634022 635723058 1369133069 1125898167 1059961393 2089018456 628175011 1656478042 1131176229 1653377373 859484421 1914544919 608413784 756898537 1734575198 1973594324 149798315 2038664370 1129566413 184803526 412776091 1424268980 1911759956 749241873 137806862 42999170 982906996 135497281 511702305 2084420925 1937477084 1827336327 572660336 1159126505 805750846 1632621729 1100661313 1433925857 1141616124 84353895 939819582 2001100545 1998898814 1548233367 610515434 1585990364 1374344043 760313750 1477171087 356426808 945117276 1889947178 1780695788 709393584 491705403 1918502651 752392754 1474612399 2053999932 1264095060 1411549676 1843993368 943947739 1984210012 855636226 1749698586 1469348094 1956297539 1036140795 463480570 2040651434 1975960378 317097467 1892066601 1376710097 927612902 1330573317 603570492 1687926652 660260756 959997301 485560280 402724286 593209441 1194953865 894429689 364228444 1947346619 221558440 270744729 1063958031 1633108117 2114738097 2007905771 1469834481 822890675 1610120709 791698927 631704567 498777856 1255179497 524872353 327254586 1572276965 269455306 1703964683 352406219 1600028624 160051528 2040332871 112805732 1120048829 378409503 515530019 1713258270 1573363368 1409959708 2077486715 1373226340 1631518149 200747796 289700723 1117142618 168002245 150122846 439493451 990892921 1760243555 1231192379 1622597488 111537764 338888228 2147469841 438792350 1911165193 269441500 2142757034 116087764 1869470124 155324914 8936987 1982275856 1275373743 387346491 350322227 841148365 1960709859 1760281936 771151432 1186452551 1244316437 971899228 1476153275 213975407 1139901474 1626276121 653468858 2130794395 1239036029 1884661237 1605908235 1350573793 76065818 1605894428 1789366143 1987231011 1875335928 1784639529 2103318776 1597322404 1939964443 2112255763 1432114613 1067854538 352118606 1782436840 1909002904 165344818 1395235128 532670688 1351797369 492067917 1504569917 680466996 706043324 496987743 159259470 1359512183 480298490 1398295499 1096689772 2086206725 601385644 1172755590 1544617505 243268139 1012502954 1272469786 2027907669 968338082 722308542 1820388464 933110197 6939507 740759355 1285228804 1789376348 502278611 1450573622 1037127828 1034949299 654887343 1529195746 392035568 1335354340 87755422 889023311 1494613810 1447267605 1369321801 745425661 396473730 1308044878 1346811305 1569229320 705178736 1590079444 434248626 1977648522 1470503465 1402586708 552473416 1143408282 188213258 559412924 1884167637 1473442062 201305624 238962600 776532036 1238433452 1273911899 1431419379 620145550 1665947468 619290071 707900973 407487131 2113903881 7684930 1776808933 711845894 404158660 937370163 2058657199 1973387981 1642548899 1501252996 260152959 1472713773 824272813 1662739668 2025187190 1967681095 1850952926 437116466 1704365084 1176911340 638422090 1943327684 1953443376 1876855542 1069755936 1237379107 349517445 588219756 1856669179 1057418418 995706887 1823089412 1065103348 625032172 387451659 1469262009 1562402336 298625210 1295166342 1057467587 1799878206 1555319301 382697713 476667372 1070575321 260401255 296864819 774044599 697517721 2001229904 1950955939 1335939811 1797073940 1756915667 1065311705 719346228 846811127 1414829150 1307565984 555996658 324763920 155789224 231602422 1389867269 780821396 619054081 711645630 195740084 917679292 2006811972 1253207672 570073850 1414647625 1635905385 1046741222 337739299 1896306640 1343606042 1111783898 446340713 1197352298 915256190 1782280524 846942590 524688209 700108581 1566288819 1371499336 2114937732 726371155 1927495994 292218004 882160379 11614769 1682085273 1662981776 630668850 246247255 1858721860 1548348142 105575579 964445884 2118421993 1520223205 452867621 1017679567 1857962504 201690613 213801961 822262754 648031326 1411154259 1737518944 282828202 110613202 114723506 982936784 1676902021 1486222842 950390868 255789528 1266235189 1242608872 1137949908 1277849958 777210498 653448036 1908518808 1023457753 364686248 1309383303 1129033333 1329132133 1280321648 501772890 1781999754 150517567 212251746 1983690368 364319529 1034514500 484238046 1775473788 624549797 767066249 1886086990 739273303 1750003033 1415505363 78012497 552910253 1671294892 1344247686 1795519125 661761152 474613996 425245975 1315209188 235649157 1448703729 1679895436 1545032460 430253414 861543921 677870460 932026304 496060028 828388027 1144278050 332266748 1192707556 31308902 816504794 820697697 655858699 1583571043 559301039 1395132002 1186090428 1974806403 1473144500 1739000681 1498617647 669908538 1387036159 12895151 1144522535 1812282134 1328104339 1380171692 1113502215 860516127 777720504 1543755629 1722060049 1455590964 328298285 70636429 136495343 1472576335 402903177 1329202900 1503885238 1219407971 2416949 12260289 655495367 561717988 1407392292 1841585795 389040743 733053144 1433102829 1887658390 1402961682 672655340 1900553541 400000569 337453826 1081174232 1780172261 1450956042 1941690360 410409117 847228023 1516266761 1866000081 1175526309 1586903190 2002495425 500618996 1989806367 1184214677 2004504234 1061730690 1186631626 2016764524 1717226057 1748349614 1276673168 1411328205 2137390358 2009726312 696947386 1877565100 1265204346 1369602726 1630634994 1665204916 1707056552 564325578 1297893529 1010528946 358532290 1708302647 1857756970 1874799051 1426819080 885799631 1314218593 1281830857 1386418627 1156541312 318561886 1243439214 70788355 1505193512 1112720090 1788014412 1106059479 241909610 1051858969 1095966189 104152274 1748806355 826047641 1369356620 970925433 309198987 887077888 530498338 873524566 37487770 1541027284 1232056856 1745790417 1251300606 959372260 1025125849 2137100237 126107205 159473059 1376035217 1282648518 478034945 471990783 1353436873 1983228458 1584710873 993967637 941804289 1826620483 2045826607 2037770478 1930772757 1647149314 716334471 1152645729 470591100 1025533459 2039723618 1001089438 1899058025 2077211388 394633074 983631233 1675518157 1645933681 1943003493 553160358 1635550270 2069110699 712633417 864101839 1204275569 1190668363 1336092622 410228794 1026413173 773319847 1404196431 1968217462 452456682 1302539390 1858504292 235745791 802205057 427355115 1388391521 1272796157 1452888574 1280631491 126401947 1204462951 1210359231 521035021 40610537 738393740 19485054 1983614030 1291554098 1655035325 1905241081 2004187516 371653516 962033002 1047372231 1707746139 1372261796 2073785404 333582338 628974580 1894519218 786039021 1931513970 1605539862 1021784812 586235379 2032894977 262692685 1859031536 1338299904 1543324176 1985433483 395279207 606199759 358984857 435889744 1344593499 378469911 272020127 488663950 2033505236 29777560 345367818 257675105 991810563 1392740049 1965421244 216588711 1319041805 151519934 845563291 1066077375 937558955 629593614 524133589 1959343768 1215828993 409544918 74552805 927376882 1747844822 1617876982 765326717 2143124030 76593093 1124311574 431530126 1421186593 1502781486 703550253 1909850543 1388803074 733327814 107734713 1646478179 1725138377 1500474762 1464415775 1941727088 672032919 1615935710 639806732 1738110294 406011017 1269400346 114760235 217871137 337745691 524305153 292423943 1265122573 124666328 1910300925 2030449291 120306710 1986894018 1007277217 551836836 1260596963 362575055 1255387090 1022963858 1751378130 1988714904 1130698571 1250372661 1566369633 483689685 567304789 1360613073 1155722604 35756851 2000419805 746349250 441767868 1122336503 861109485 659639006 1460082195 1385414639 952062949 577721120 1510080967 714880226 460686763 1630387677 554290596 1467963981 34740865 1814887560 1830539036 1290127955 690367770 1434433518 1131359211 1821066342 537322532 550245196 157272379 1104627321 1910858270 1312994984 1140384172 1763794427 2059344234 1582152040 738647283 772970072 94307398 51245830 10901063 1046370347 628966950 1520982030 1761250573 1089653714 1003886059 168057522 410134047 1038626924 1982945082 93189435 181271232 525829204 1527622954 1312630443 199411898 2064945486 1862875640 356684278 1022089159 1626250262 1669679262 14989683 1242561041 1581539848 1597141723 1981208324 207026272 1691449122 2032454154 217927335 590335821 513937457 1738909365 204102747 1603591171 595311776 372160269 2013725218 1633938701 207621703 2106914653 1815209933 733450907 1487053959 980356728 932862806 1404515797 695748720 1289547084 279121308 174515334 811742698 294110991 1417076376 245798898 1891252715 1250801052 452825171 1435218189 1135771559 670752506 2025554010 1649709016 262178224 82173109 1105816539 857490000 454333378 972058109 343945053 661955081 931489114 11671338 1395405989 271059426 992028067 180785147 1675575223 1687776787 1470332231 1954696532 1862292122 134591281 101323875 1131884850 380390179 1992576590 235202254 833215350 1280311131 1370973813 1503967857 1158381494 873199181 1766146081 1240554603 1979015720 476152433 1694887982 803590181 820097487 209359415 1735079296 831768825 1604765404 2006138722 1823796892 1785550551 1534230297 1364090032 1108399134 1341443181 1078898506 1242990415 1442767057 63299708 1623380595 1287859999 298501962 309112297 420687483 1669475776 1813080154 1579068977 395191309 1431742587 672139932 226723382 1907895021 219544266 1030313563 580508860 428903682 617909211 1412277685 2033669086 476564285 1088590930 1671735990 2010794583 305197314 632651476 1204754116 1384095820 1875641892 500037525 1447395528 1351538839 1787897525 1745897490 1660651136 61101360 1267889618 1326247643 1640170337 j.="" 1.2="" modify="" the="" mergesort="" algorithm="" to="" count="" the="" number="" of="" inversions.="" 2.1="" develop="" a="" brute="" force="" algorithm="" based="" on="" the="" definition="" of="" convex="" hull.="" the="" algorithm="" is="" to="" find="" the="" convex="" hull="" for="" a="" given="" set="" of="" points.="" please="" see="" figure="" 3.5="" on="" page="" 111.="" develop="" your="" algorithm="" to="" find="" the="" nails="" holding="" the="" rubber-band,="" that="" is,="" to="" find="" the="" extreme="" points.="" a="" brute="" force="" algorithm="" checks="" every="" point="" in="" the="" given="" data="" set="" to="" see="" if="" it="" is="" an="" extreme="" point="" (nail)="" of="" the="" convex="" polygon.="" an="" extreme="" point="" is="" an="" ending="" point="" of="" a="" straight="" boundary="" line.="" two="" points="" define="" a="" boundary="" line="" if="" all="" the="" other="" points="" are="" on="" one="" side="" of="" the="" line.="" please="" read="" •="" “convex-hull="" problem”="" on="" page="" 109="" for="" the="" definition="" and="" an="" example="" of="" convex="" hull;="" •="" the="" definition="" of="" extreme="" point="" (page="" 112);="" •="" the="" equation="" of="" a="" straight="" line="" through="" two="" points="" (page="" 112);="" •="" the="" method="" to="" check="" if="" all="" the="" points="" in="" a="" set="" are="" on="" one="" side="" of="" a="" line="" (page="" 112).="" then="" design="" an="" algorithm="" to="" find="" the="" shortest="" path.="" •="" the="" equation="" for="" calculating="" the="" distance="" between="" points="" s1="(x1," y1)="" and="" s2="(x2," y2)="" is="" √="" (x1="" −="" x2)2="" +="" (y1="" −="" y2)2="" 2.2="" design="" a="" divide-and-conquer="" algorithm="" of="" θ(n="" log="" n)="" based="" on="" the="" idea="" of="" quicksort.="" please="" read="" •="" “convex-hull="" problem”="" on="" page="" 195="" for="" the="" quick="" hull="" algorithm.="" then="" design="" an="" algorithm="" to="" find="" the="" shortest="" path.="" 1="" •="" you="" can="" use="" the="" algorithm="" of="" 2.1="" for="" finding="" the="" shortest="" path.="" 1.3,="" 2.3="" make="" sure="" your="" programs="" can="" be="" correctly="" compiled="" and="" executed="" on="" the="" linux="" system="" in="" socs.="" your="" work="" should="" be="" submitted="" as="" a="" tar="" file="" containing="" files="" like="" readme,="" design,="" p11.c,="" p12.c,="" p21.c,="" p22.c,="" makefile.="" please="" do="" not="" submit="" the="" data="" files.="" any="" compilation="" error="" or="" warning="" will="" result="" in="" a="" mark="" deduction.="" there="" will="" be="" some="" marks="" allocated="" for="" documentation.="" each="" file="" should="" have="" a="" comment="" at="" the="" beginning="" containing="" your="" name,="" id,="" date,="" and="" the="" assignment="" name.="" the="" readme="" file="" should="" contain="" the="" following:="" •="" name,="" id,="" and="" assignment="" number="" •="" a="" brief="" description="" of="" how="" to="" compile="" and="" run="" your="" programs.="" the="" design="" file="" should="" include="" the="" algorithms="" you="" design="" for="" 1.1,="" 1.2,="" 2.1,="" and="" 2.2,="" efficiency="" analysis,="" and="" comparisons.="" this="" can="" be="" a="" text,="" pdf="" or="" scanned="" file.="" in="" your="" c="" files,="" each="" function="" should="" have="" a="" brief="" comment="" describing="" its="" purpose.="" also,="" any="" section="" of="" code="" where="" it="" is="" not="" easily="" apparent="" what="" the="" code="" does="" should="" have="" a="" short="" comment.="" you="" can="" use="" timespec="" get()="" to="" get="" program="" running="" time.="" 2="" 1804289383="" 846930886="" 1681692777="" 1714636915="" 1957747793="" 424238335="" 719885386="" 1649760492="" 596516649="" 1189641421="" 1025202362="" 1350490027="" 783368690="" 1102520059="" 2044897763="" 1967513926="" 1365180540="" 1540383426="" 304089172="" 1303455736="" 35005211="" 521595368="" 294702567="" 1726956429="" 336465782="" 861021530="" 278722862="" 233665123="" 2145174067="" 468703135="" 1101513929="" 1801979802="" 1315634022="" 635723058="" 1369133069="" 1125898167="" 1059961393="" 2089018456="" 628175011="" 1656478042="" 1131176229="" 1653377373="" 859484421="" 1914544919="" 608413784="" 756898537="" 1734575198="" 1973594324="" 149798315="" 2038664370="" 1129566413="" 184803526="" 412776091="" 1424268980="" 1911759956="" 749241873="" 137806862="" 42999170="" 982906996="" 135497281="" 511702305="" 2084420925="" 1937477084="" 1827336327="" 572660336="" 1159126505="" 805750846="" 1632621729="" 1100661313="" 1433925857="" 1141616124="" 84353895="" 939819582="" 2001100545="" 1998898814="" 1548233367="" 610515434="" 1585990364="" 1374344043="" 760313750="" 1477171087="" 356426808="" 945117276="" 1889947178="" 1780695788="" 709393584="" 491705403="" 1918502651="" 752392754="" 1474612399="" 2053999932="" 1264095060="" 1411549676="" 1843993368="" 943947739="" 1984210012="" 855636226="" 1749698586="" 1469348094="" 1956297539="" 1036140795="" 463480570="" 2040651434="" 1975960378="" 317097467="" 1892066601="" 1376710097="" 927612902="" 1330573317="" 603570492="" 1687926652="" 660260756="" 959997301="" 485560280="" 402724286="" 593209441="" 1194953865="" 894429689="" 364228444="" 1947346619="" 221558440="" 270744729="" 1063958031="" 1633108117="" 2114738097="" 2007905771="" 1469834481="" 822890675="" 1610120709="" 791698927="" 631704567="" 498777856="" 1255179497="" 524872353="" 327254586="" 1572276965="" 269455306="" 1703964683="" 352406219="" 1600028624="" 160051528="" 2040332871="" 112805732="" 1120048829="" 378409503="" 515530019="" 1713258270="" 1573363368="" 1409959708="" 2077486715="" 1373226340="" 1631518149="" 200747796="" 289700723="" 1117142618="" 168002245="" 150122846="" 439493451="" 990892921="" 1760243555="" 1231192379="" 1622597488="" 111537764="" 338888228="" 2147469841="" 438792350="" 1911165193="" 269441500="" 2142757034="" 116087764="" 1869470124="" 155324914="" 8936987="" 1982275856="" 1275373743="" 387346491="" 350322227="" 841148365="" 1960709859="" 1760281936="" 771151432="" 1186452551="" 1244316437="" 971899228="" 1476153275="" 213975407="" 1139901474="" 1626276121="" 653468858="" 2130794395="" 1239036029="" 1884661237="" 1605908235="" 1350573793="" 76065818="" 1605894428="" 1789366143="" 1987231011="" 1875335928="" 1784639529="" 2103318776="" 1597322404="" 1939964443="" 2112255763="" 1432114613="" 1067854538="" 352118606="" 1782436840="" 1909002904="" 165344818="" 1395235128="" 532670688="" 1351797369="" 492067917="" 1504569917="" 680466996="" 706043324="" 496987743="" 159259470="" 1359512183="" 480298490="" 1398295499="" 1096689772="" 2086206725="" 601385644="" 1172755590="" 1544617505="" 243268139="" 1012502954="" 1272469786="" 2027907669="" 968338082="" 722308542="" 1820388464="" 933110197="" 6939507="" 740759355="" 1285228804="" 1789376348="" 502278611="" 1450573622="" 1037127828="" 1034949299="" 654887343="" 1529195746="" 392035568="" 1335354340="" 87755422="" 889023311="" 1494613810="" 1447267605="" 1369321801="" 745425661="" 396473730="" 1308044878="" 1346811305="" 1569229320="" 705178736="" 1590079444="" 434248626="" 1977648522="" 1470503465="" 1402586708="" 552473416="" 1143408282="" 188213258="" 559412924="" 1884167637="" 1473442062="" 201305624="" 238962600="" 776532036="" 1238433452="" 1273911899="" 1431419379="" 620145550="" 1665947468="" 619290071="" 707900973="" 407487131="" 2113903881="" 7684930="" 1776808933="" 711845894="" 404158660="" 937370163="" 2058657199="" 1973387981="" 1642548899="" 1501252996="" 260152959="" 1472713773="" 824272813="" 1662739668="" 2025187190="" 1967681095="" 1850952926="" 437116466="" 1704365084="" 1176911340="" 638422090="" 1943327684="" 1953443376="" 1876855542="" 1069755936="" 1237379107="" 349517445="" 588219756="" 1856669179="" 1057418418="" 995706887="" 1823089412="" 1065103348="" 625032172="" 387451659="" 1469262009="" 1562402336="" 298625210="" 1295166342="" 1057467587="" 1799878206="" 1555319301="" 382697713="" 476667372="" 1070575321="" 260401255="" 296864819="" 774044599="" 697517721="" 2001229904="" 1950955939="" 1335939811="" 1797073940="" 1756915667="" 1065311705="" 719346228="" 846811127="" 1414829150="" 1307565984="" 555996658="" 324763920="" 155789224="" 231602422="" 1389867269="" 780821396="" 619054081="" 711645630="" 195740084="" 917679292="" 2006811972="" 1253207672="" 570073850="" 1414647625="" 1635905385="" 1046741222="" 337739299="" 1896306640="" 1343606042="" 1111783898="" 446340713="" 1197352298="" 915256190="" 1782280524="" 846942590="" 524688209="" 700108581="" 1566288819="" 1371499336="" 2114937732="" 726371155="" 1927495994="" 292218004="" 882160379="" 11614769="" 1682085273="" 1662981776="" 630668850="" 246247255="" 1858721860="" 1548348142="" 105575579="" 964445884="" 2118421993="" 1520223205="" 452867621="" 1017679567="" 1857962504="" 201690613="" 213801961="" 822262754="" 648031326="" 1411154259="" 1737518944="" 282828202="" 110613202="" 114723506="" 982936784="" 1676902021="" 1486222842="" 950390868="" 255789528="" 1266235189="" 1242608872="" 1137949908="" 1277849958="" 777210498="" 653448036="" 1908518808="" 1023457753="" 364686248="" 1309383303="" 1129033333="" 1329132133="" 1280321648="" 501772890="" 1781999754="" 150517567="" 212251746="" 1983690368="" 364319529="" 1034514500="" 484238046="" 1775473788="" 624549797="" 767066249="" 1886086990="" 739273303="" 1750003033="" 1415505363="" 78012497="" 552910253="" 1671294892="" 1344247686="" 1795519125="" 661761152="" 474613996="" 425245975="" 1315209188="" 235649157="" 1448703729="" 1679895436="" 1545032460="" 430253414="" 861543921="" 677870460="" 932026304="" 496060028="" 828388027="" 1144278050="" 332266748="" 1192707556="" 31308902="" 816504794="" 820697697="" 655858699="" 1583571043="" 559301039="" 1395132002="" 1186090428="" 1974806403="" 1473144500="" 1739000681="" 1498617647="" 669908538="" 1387036159="" 12895151="" 1144522535="" 1812282134="" 1328104339="" 1380171692="" 1113502215="" 860516127="" 777720504="" 1543755629="" 1722060049="" 1455590964="" 328298285="" 70636429="" 136495343="" 1472576335="" 402903177="" 1329202900="" 1503885238="" 1219407971="" 2416949="" 12260289="" 655495367="" 561717988="" 1407392292="" 1841585795="" 389040743="" 733053144="" 1433102829="" 1887658390="" 1402961682="" 672655340="" 1900553541="" 400000569="" 337453826="" 1081174232="" 1780172261="" 1450956042="" 1941690360="" 410409117="" 847228023="" 1516266761="" 1866000081="" 1175526309="" 1586903190="" 2002495425="" 500618996="" 1989806367="" 1184214677="" 2004504234="" 1061730690="" 1186631626="" 2016764524="" 1717226057="" 1748349614="" 1276673168="" 1411328205="" 2137390358="" 2009726312="" 696947386="" 1877565100="" 1265204346="" 1369602726="" 1630634994="" 1665204916="" 1707056552="" 564325578="" 1297893529="" 1010528946="" 358532290="" 1708302647="" 1857756970="" 1874799051="" 1426819080="" 885799631="" 1314218593="" 1281830857="" 1386418627="" 1156541312="" 318561886="" 1243439214="" 70788355="" 1505193512="" 1112720090="" 1788014412="" 1106059479="" 241909610="" 1051858969="" 1095966189="" 104152274="" 1748806355="" 826047641="" 1369356620="" 970925433="" 309198987="" 887077888="" 530498338="" 873524566="" 37487770="" 1541027284="" 1232056856="" 1745790417="" 1251300606="" 959372260="" 1025125849="" 2137100237="" 126107205="" 159473059="" 1376035217="" 1282648518="" 478034945="" 471990783="" 1353436873="" 1983228458="" 1584710873="" 993967637="" 941804289="" 1826620483="" 2045826607="" 2037770478="" 1930772757="" 1647149314="" 716334471="" 1152645729="" 470591100="" 1025533459="" 2039723618="" 1001089438="" 1899058025="" 2077211388="" 394633074="" 983631233="" 1675518157="" 1645933681="" 1943003493="" 553160358="" 1635550270="" 2069110699="" 712633417="" 864101839="" 1204275569="" 1190668363="" 1336092622="" 410228794="" 1026413173="" 773319847="" 1404196431="" 1968217462="" 452456682="" 1302539390="" 1858504292="" 235745791="" 802205057="" 427355115="" 1388391521="" 1272796157="" 1452888574="" 1280631491="" 126401947="" 1204462951="" 1210359231="" 521035021="" 40610537="" 738393740="" 19485054="" 1983614030="" 1291554098="" 1655035325="" 1905241081="" 2004187516="" 371653516="" 962033002="" 1047372231="" 1707746139="" 1372261796="" 2073785404="" 333582338="" 628974580="" 1894519218="" 786039021="" 1931513970="" 1605539862="" 1021784812="" 586235379="" 2032894977="" 262692685="" 1859031536="" 1338299904="" 1543324176="" 1985433483="" 395279207="" 606199759="" 358984857="" 435889744="" 1344593499="" 378469911="" 272020127="" 488663950="" 2033505236="" 29777560="" 345367818="" 257675105="" 991810563="" 1392740049="" 1965421244="" 216588711="" 1319041805="" 151519934="" 845563291="" 1066077375="" 937558955="" 629593614="" 524133589="" 1959343768="" 1215828993="" 409544918="" 74552805="" 927376882="" 1747844822="" 1617876982="" 765326717="" 2143124030="" 76593093="" 1124311574="" 431530126="" 1421186593="" 1502781486="" 703550253="" 1909850543="" 1388803074="" 733327814="" 107734713="" 1646478179="" 1725138377="" 1500474762="" 1464415775="" 1941727088="" 672032919="" 1615935710="" 639806732="" 1738110294="" 406011017="" 1269400346="" 114760235="" 217871137="" 337745691="" 524305153="" 292423943="" 1265122573="" 124666328="" 1910300925="" 2030449291="" 120306710="" 1986894018="" 1007277217="" 551836836="" 1260596963="" 362575055="" 1255387090="" 1022963858="" 1751378130="" 1988714904="" 1130698571="" 1250372661="" 1566369633="" 483689685="" 567304789="" 1360613073="" 1155722604="" 35756851="" 2000419805="" 746349250="" 441767868="" 1122336503="" 861109485="" 659639006="" 1460082195="" 1385414639="" 952062949="" 577721120="" 1510080967="" 714880226="" 460686763="" 1630387677="" 554290596="" 1467963981="" 34740865="" 1814887560="" 1830539036="" 1290127955="" 690367770="" 1434433518="" 1131359211="" 1821066342="" 537322532="" 550245196="" 157272379="" 1104627321="" 1910858270="" 1312994984="" 1140384172="" 1763794427="" 2059344234="" 1582152040="" 738647283="" 772970072="" 94307398="" 51245830="" 10901063="" 1046370347="" 628966950="" 1520982030="" 1761250573="" 1089653714="" 1003886059="" 168057522="" 410134047="" 1038626924="" 1982945082="" 93189435="" 181271232="" 525829204="" 1527622954="" 1312630443="" 199411898="" 2064945486="" 1862875640="" 356684278="" 1022089159="" 1626250262="" 1669679262="" 14989683="" 1242561041="" 1581539848="" 1597141723="" 1981208324="" 207026272="" 1691449122="" 2032454154="" 217927335="" 590335821="" 513937457="" 1738909365="" 204102747="" 1603591171="" 595311776="" 372160269="" 2013725218="" 1633938701="" 207621703="" 2106914653="" 1815209933="" 733450907="" 1487053959="" 980356728="" 932862806="" 1404515797="" 695748720="" 1289547084="" 279121308="" 174515334="" 811742698="" 294110991="" 1417076376="" 245798898="" 1891252715="" 1250801052="" 452825171="" 1435218189="" 1135771559="" 670752506="" 2025554010="" 1649709016="" 262178224="" 82173109="" 1105816539="" 857490000="" 454333378="" 972058109="" 343945053="" 661955081="" 931489114="" 11671338="" 1395405989="" 271059426="" 992028067="" 180785147="" 1675575223="" 1687776787="" 1470332231="" 1954696532="" 1862292122="" 134591281="" 101323875="" 1131884850="" 380390179="" 1992576590="" 235202254="" 833215350="" 1280311131="" 1370973813="" 1503967857="" 1158381494="" 873199181="" 1766146081="" 1240554603="" 1979015720="" 476152433="" 1694887982="" 803590181="" 820097487="" 209359415="" 1735079296="" 831768825="" 1604765404="" 2006138722="" 1823796892="" 1785550551="" 1534230297="" 1364090032="" 1108399134="" 1341443181="" 1078898506="" 1242990415="" 1442767057="" 63299708="" 1623380595="" 1287859999="" 298501962="" 309112297="" 420687483="" 1669475776="" 1813080154="" 1579068977="" 395191309="" 1431742587="" 672139932="" 226723382="" 1907895021="" 219544266="" 1030313563="" 580508860="" 428903682="" 617909211="" 1412277685="" 2033669086="" 476564285="" 1088590930="" 1671735990="" 2010794583="" 305197314="" 632651476="" 1204754116="" 1384095820="" 1875641892="" 500037525="" 1447395528="" 1351538839="" 1787897525="" 1745897490="" 1660651136="" 61101360="" 1267889618="" 1326247643="">