Алгоритм муравья (работа 1)

Министерство образования Российской Федерации

Кафедра алгебры и математической логики

РЕФЕРАТ

на тему «Алгоритм муравья»

2009 г.

Содержание

Введение.

1 Идея алгоритма.

2 Пошаговое описание общей схемы

3 Муравей

4 Начальная популяция

5 Движение муравья

6 Путешествие муравья

7 Испарение фермента

8 Повторный запуск

9 Блок-схема алгоритма

10 Демонстрационный пример

11 Характерные особенности

12 Области применения

Заключение

Список литературы

Введение

Каждый, кто хоть раз в жизни наблюдал за муравьями, обязательно должен был заметить: вся деятельность этих насекомых имеет ярко выраженную групповую окраску. Работая вместе, группа муравьев способна затащить в муравейник кусок пищи или строительного материала, в 10 раз больше них самих. Организацию муравьев можно применять и людям в решении некоторых задач. Сам по себе муравей - достаточно примитивное существо. Все его действия, по сути, сводятся к элементарным инстинктивным реакциям на окружающую обстановку и своих собратьев. Однако несколько муравьев вместе образуют сложную систему. Например, группа муравьев прекрасно умеет находить кратчайшую дорогу к пище. Если какое-нибудь препятствие - палка, камень, нога человека - встает на пути, они быстро находят новый оптимальный маршрут. Муравьи решают проблемы поиска путей с помощью химической регуляции. Каждый муравей выделяет феромоны, и их след образует, таким образом, путь муравья. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев - тем явнее след, а чем явнее след - тем большее «желание» пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к цели, тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, и круг замыкается. Остальные пути - менее используемые - потихоньку пропадают. Алгоритмы муравья (Ant algorithms), или оптимизация по принципу муравьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго (Marco Dorigo)), основаны на применении нескольких агентов и обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, в изменяющихся сетях.

Мы рассмотрим общий случай алгоритма муравьиной колонии.

1. Идея алгоритма

Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного феромона, используя его в качестве маркера.

0100090000034adc000000009f68000000001610000026060f002220574d464301000000000001009c440000000008000000002000008cc500008ce50000010000006c000000000000000000000045010000450100000000000000000000d51f0000d81d000020454d46000001008ce500000c00000001000000000000000000000000000000000500000004000040010000f000000000000000000000000000000000e2040080a90300460000002c00000020000000454d462b014001001c000000100000000210c0db01000000600000006000000046000000b4120000a8120000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c000000000000000840000500120000f41100000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d4948445200000146000001460403000000e4f92bc300000018504c5445f7f6f6828282bdbcbd4d4d4debebeb9d9d9dd6d6d6ffffffb6da617800000001624b47440088051d480000000c636d50504a436d7030373132000000074f6db7a5000011554944415478daed9ddb7ba23cb7c0333e8cb91d6871df0aafe0b5d33ddfb5fa21dc166a9cdbc22b709b7153f8f77712f00082588c50e761b5b58826fc585939ad1c004953c14d0281d6025142609a5bd3300df2b2ddb223931cd11ffa86c9761b908fcd40f7bc4025a239ba6ab5c8384008d908c9e44546ecd8a6ff64f68e1dee453e3976509b8c910e8439980301002010d9ff13c07c3e6787ec684ecfd31f7a0005a8b4c9186f120c3ff17d88313560fbbd4d3d8e3ec79849ab7a8c368d822961cfc885d16a9371f4008c7f715ab7c9183f823d3e02a3031b31866d323e803d461bd888d1ea19f38cbd3d7262848d18ad9e3127d86914acb7c782e086f9da6a91f111eaebde1ebb65b45a65845f9ff111eaebbf98d1ea19b930863d231746ab67cc334a7f2da3f6008cbd3d16191f418fbd3df2617c047bfc8bebc24760b47a462e8c61cfc885d17a00c6b067e4c1a87d7946f8007a7c04c624711f80f1ebeb11b6aec7cf43b66f8f4d82b6ab47049b046b5b8f9f876cdb1e5183b4eeedf19cb1b7473e8cbd3df2616ca2c7f6edf1f34141afc733c6de1ef9303e863d3609d6ae1e1b325a0fc018b6c9f808fe9e46ab4c7a9fd41963433db6caf817db63d82a236c12acaf677830f6f5352fc65e8f3c187b7be4c5d8eb9107636f8fbc187b3df260eced911763af471e8cbd3df262ecf5c883b1757bb49a04fbfa7aecfd3d258cf00118ad0760840fc0683d00237c0046eb01186193607d3d73c6089b5cacd7e319236c12acd7e319236c72b15e8f7c18fbfe0c0fc6de1e793172d26334bf8e113661e4a447c163f1d46c37daa93d62a08d3098c3a88ed16a70354e7ac42092ada076bbcbeeec117b5b9c08fe64551b5567f608868a3c99c358de8dee628f3c1885b9e08b688e355db66ac275668f90686f694b70e7b8d3fb30de6e8f905ddd1e439ad8758cb00923af7a66111a28b26b22eb24ad61f6066037fc784e9457cc4e9af00b315220408108e3b7e940b6526014964376c198153582b14dbeeb5ae8bea69f0a8ec597b149a803234189020f89f2c4156752369b4cd0f48a70ddcc2385d8175f88cc9ec8cbb31fd26ad177de9372966eec112f295c26bf9efe3337020d85c917622469adbc9ccacc5155759af0666c12eac888df728c2f4807f4e38a69e0ddd823fe27cf28e9c13b00156aecc61e41e2e7d35a573544375aabd263078ce4b22706f9cb7e26273c55b512a3821176c0089258b349d696489acf26438849ad13a17152de05eb8691d6349187a47061cf549a9202c070a957a074541742905688ab77df7247940dc3480bbf8e3d625aadd003babeeee335b6a7e979afb2be86b571f3664c523e4aeb4e3f4649c658f97c8253469c4420fd2a296513f62f01594b2f8df6f05d3e7d05d29e9f46f250ae51d331adb1e0a91ac95820bd4301ec196984ec9f002180bc18992c452311973f6a3c2a4746608ac8666f20bd436ad4701f33d120552f3c5c868b9f42f0ed0dd86daab2ca09e35ed1a4ab6bf95b55b606e8dd479b9dac6a72e03b9eacfa68ee41136887b281c73a4d88971a7260a46ce5ba7039c6e49b272a1b4d5b3f21d947b2360b44d1791b29c8514c7129a3bdd783c77a5752d438db04eea455ed8ea827691dcff0ca736247f4253972146f144bbb1fc37777ea6ae4ddccfd5fe5f7c1a3c0c11e71f04e6c479992166ead9fe2c828e355b0893451dd90bce6ca52441831584d5d67634baa22a170be2f1f78d823c9d9702703330457fb52402c26df02693512cd8d389417d2cf58de3dfb1377aaa8f2db48557e787be3e6b66e5850a638cda2d7e9318955b8349136f6b5b563a87ea00f7501d9e3c5bb4fd27aec790eda8371638cf46b567f9f30626c59838d8e05d5c2807a8189b9983a14801018434b80de499dcf89111bd7843badaf4162c55b50e9fa8d4e6e9913e3756be8f36d0a48d487f3903833977c6c9c18af1b6928b429f0c9ebfecc81111c6f9b575a5fc9685dfcfcf40e405a237264a427eb7559c6786a2520c58485c4e6c768cc615db832468c8b89409aa4023cbdc8ad7d85b4a5b3d46c5146b62cd31203e32a8d96b671cbcce4d08ae4c1c85a55430dc948d53d4dd36c794218e117f2a5303560cf96f56d0a853d4d74280757c6dbea6b8282357943135c48533d22c495513662bcb12ea48583266fd3ce5776796c2a9563205d8c1712341fbd0b698f06a7151be94b6955908df4086eedbbaee4f7645fe6c0ec2318f9159daf868cb7d9e3522cba9599e362a8958fd4b4ad476a8bb1bd2e6b4c6078f006141961d2401a33d23f9fe4e8d2abe265294ddbe523f91bcad63e37e709c99fbbe6c7788b3dbaeb4a8f6db22bcbdbede7eba1139262a7c23501fcd1397efbf3f6fc3569e1e12af749d90067dbf68823dbc2171ee10917cf67e770dbf6b81a55f410d8590063e58cbf657b04891d5eba20a91f953169b9e538ef618f425a8ea49eb61c239ec75285b3f6209e53740adcc31e0f10180aa74000626bb54eea661c1183cddfc61dec91453854b749b14345df5cb169ad3b2e30de418fa46889902cdae81d17d3da8aa5ec1eca85c1ed36854c7587fa1a9292d8d91aa62659f99e11b9f4f767185d560ab941a7507836d4e3e5241ba0104220d8851618c933da140a9709c90fc9d9f99377c833d84f5db3b138cd33c21859979fc0cc3e5dbce633f63df2758ce6690671f36e6490eca42be28e769b7cd6bf47fb7141279a60ea7545997632465c3b258a7d5b70f299e61ef6b89f4006f0f17116e90c9ed538b942a096cf34f7b0c76394ee96b961b236c4d5dd20253f6df30ef5353c76ef1613e6a88dd2c4061085c935e2ff2e30c2ab8215e49242c03e63608b58a61004acc6a17fd8b9462138f9782d305e13ec4c2ee911ef07aeb0e5af23ed4914f5f41ae0da0711eef2e5c11deaeb48caec0fc3c5c676027329a659055cf9906818e7efe50ef618c9d63e8f2c34f59da02e650609066beadfc1740437a17539c0cca39764f52369361acc418b513e42bb911e8f8c381bf1a69ee86c985b99a6235718fe2b59ecdadf59b9083e3659a392bc1ad41630c9f2918531a5c438ed4c24e78c3ccaf0c3f0571a97360519fd3f59991db3d4021f6bf20dc18231533469ca46744c1c436090561cce46bce847bcf5080cd2e6a2d11f7cc503871192eaf965ff3536c79132e284b472576bea0410b22171c2b8d4f7960ad80de7157773befe40b6c3f4776c074422fb9424f5cfc3b72803f8bea61dbf9ff0dfd13c01ef011cea10043032608036000e87309ecf23da97b0f38cb7eaf18f6cffa2f64fdb5cd8a095184cfc74dae5d23e54cfb46d9b803f34eb2c7e596f8e1339229ab8e25a119f57e2d8379de574e58ddd89ce6ad9fc23a16eb6c73feba13c809e39f5f076a9a6854cac4de6091edaeab1af4c931f7ca31fbba2893668f8eba73752fd675b756c4f5a99b2bb567cfd4d1711f557e515d7508f476fc29fdf11723dd17fd576926fa74f1005038454cdd657bfb32fe1443d30ae5455d55d6db389a5953d7ab347b6f853d32477f6a4a96fc1cb847e3f6f8037dbe3ff11c685f7e4fe8fb293963e7b9216c9afff88f2d36c3a38d4695885073d06a2b7f93e0b46431969cfae23db81ae3cfbdab3ad89eeda9668e6e66d8f3f62a4c8aef2db37241f8dd2ece34a1360facee0c7e1324c8fc41e31f4b772b0897f09b2e6d8ca48d1641b39eec8d77efbaaf44797b53165cc41e13c7203c675841469e18f8859910bb21a6620d379404041d49bc8ce588cf16342caede55c35f5a114cf9cb14b30d17a674fbdc9d20b97e664a74f96531a3d0f3d1eebebdd64a8fae3a53b13c517a21148a2c30a33aa24b64734725282c221cb33bb35eb5491dfd53a760c36a5893958309b5d480a596cd16e4254ac671a309ed6d7a4123386168e80b9f5b7c696a6f54ecae25cfdca8637e0c73363dcec9d18cba9c0eee358a81e3487e9ac893ce3ad7a3cc69c0cb2a8be65fd3a10ed3b8698751f58bb87b1404c6bc388b52cb28e224cab7de6e22db48f6eb6c7ec5621c8ea429c0131f9f73f9051a52e64106dd830dcfed2240895fdd03d48678c9177bbbc57fc763d526b828491aa01d0990d181dba4cff152794314e5df1e0f8d072909262da34a3064ab31639b20cd6aed8716887e7da8f209b44479a09309da324315c7af115425bd2d2f1c4301d53b8aa3f13c1c56f1e7abcd857c85a121880e5da1737c19b3c39bfb54be24f0b7a84bc19a3a33362f58a7dd22e0a60c6b89826f5021394ef5fdf418f9194352441b2fa919f71fdb14eea05447cfc1417d37a1f25e9f38fe1c9180280d1351d433828785ceea0c7c38718a647a4fac89893ab2cabe871b98f4f2aebbba6911f06074194d4ae25649117be7473fbb1440652564c5337596e320afcfe9ad44b11e91e7a8ce4345f0acc6f73628f74b0f0e2042e0c48177658f414dcc36f96ac52bf8e2785457f38a87b782da0ae41581c43ba0363ac6ce650f0d0a4707d78e6123b678458b40a73d0aed3e3d998f8c57548102fdf64cd16f5f9d9b8c215dee6c1d9937bafb3c7b3f18a4b8c3442ba787033cf4debccfc7b4a78d11e2176c7c531cf2bf408ca18c39a10aca186f376c566ecaf7ec08b2187e74abbd21e8be12ed633745c901d18e7695d734190f8b4fb9b5775d37c7d211410b27b320a5f4ad3703181a5c152ae1885a418cd8f33dd711e00283b81e190b6c94b86d9d9428ec42fc953f7a8af2f43636f93944ea7106062c5652abbcb78e10546f217cb212e9b856b90e6bcc26d7ecf2d730b497622d9a264d490f52cc5b292296ad22fbc8591a4686497698bbac9ed7559e1d9c93cd29d5d3a261729e573561ae9f1e6f9b8dfcb26b6629f186a194d437bbc4d8f18fa92714a438f2382583e0fad8bf9b8743e8282b6273c90fa7e51d5a02ce6e4eff91463c226873b6c243ef3c07848ae5c33d57e19be578e8a90be4d2f8e4d4574b6b06a415227f6c8966710558ab2a30781ae91861c6db9c38a708dda1437af954a7d65a4a58e902dda36a284d5eb3f78f91f3fc798dd29112108b21c8e2b67ac34cc3337ea11662f87e13b882fae1b6ec078b33dee69b235b597009b3372da972b23ab5932d54d5a9f9cc0a0365c67e523130cae62ecf4997658ad9b55cabed52d237550d64a87692d902eee4082422d407779069b56028036f6de2b2bc14cbab3c7c847610206d27253fef95760c44bba622fd28efb01543176583e62a0384ef87da34d6bc2755a3e62537c15d07124be8ab1bbb2878ed6b96380843a840ecb47eaab5884b103ff99967e7e906eebc26431fdd844d94ab328a840e9b44d41fdf31fd3d5284588aa667076628fac49667aaa6ab8c8a6db3558749ae152ad582fde0923e9cc98487c7999c936ddcb2eb22cda0553c755eb863b486ba2c6a19d6e1ac6363753684de3397ad51aaf2eec9134bbddfcfe669ee6687a254847e5639ef1457654c3aaec3274638fc9e95e7624c1e5ca74668cdd943d053d3a9aac56c7d84df908866fa77afc390f54ad7ace4a57f5f5d0a61b69ce28ea0f932e4fc0de619ba5a274565f0b9ef2345bbbb317271b91c17ed58490a6f6783323a1148c64b555a6d92c3f1ca9159136b5470e8c5456e1ea7597ad31c374efd432e9acfd4807dc71b298ec249c8d32e06caad2d76184ecc4628c659c4d20a9f69b759ad6913bb6d0403a5097b77b3ab5c7c846e1505a65b3c82b376eead2df433aaf5bb8186bdb9a70ddd923f66cd2f0165020d5ed7cd59d3d6293b6c6569b7411c825e9d01e212dc6edd0b43eb14f5ccb8c904e40f34717f658e89c11d213906dcb0deb183b4aeb74173bc16073386b203bb3474877e76233c46bc375ea0fbf6e9bb8c7788e4fb7be94aba4e3f6e355d2edf8cc75c269ddc75d191fc31e6123c62677f677dbe3e7ae06ba606c74b596191f21ad1f418f0f50cf247d5af3617c80b4eee6d92e9f9347287b1ea12eecd39a0fe323a475af476e8c9f0f3a4f8a5bb9dd97b1f66996a5d2ae3daa569d4be8209008c06c2fa0ba473772658cb477b8df6be013c1ea965b72658c6da41ec5231214c5344c831d1844b6e4879c68558f099d474ec5b6455b3c932726b3d9ec497ca26fc4d98cbd6964c58d19e9ee48548c3930d20393a82a551991f9dc4885282f308360bb25bf66306976a566f219233c84c1b051b8cf30e25a0ff47de4738c9d20de608fedc9ff03d73b3a2cb3b0fd670000000049454e44ae426082000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf0000a3430000a34303000000000000b3000000b3ffffa243000000b3000000b3ffffa2432100000008000000620000000c00000001000000150000000c00000004000000150000000c000000040000005100000074d1000000000000000000004501000045010000000000000000000000000000000000004601000046010000500000004c0000009c000000d8d00000000000002000cc0046010000460100002800000046010000460100000100040000000000000000000000000000000000090000000000000000000000ffffff00f6f6f700ebebeb00d6d6d600bdbcbd009d9d9d00828282004d4d4d00111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111112122111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112122111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122112222222222333222332222222222333433433333333333433333333332323333333333333334333444344444434344434334445311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111456666666666666667677767777777777777777777777777777777777777787878787878878787787778777878787787878787877877763111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111467665555555555555555555555454545454444444444444444444444444444444444343334334444444444333333334333433334333467411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111135642212211111111121112111111111111111111111111111111111111111111111111111111111111111111111111111111111111115631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112553111211111111111111111111111111111111111111111111111111111111111111111111111111111112121212122121212112211674111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111103111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111376311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111136631221111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111132115752111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111071111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111266311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111610000026060f002220574d4643010000000000010000000000000008000000002000008ca500008ce5000011111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111267311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111267311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111257311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111221111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111267211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112672111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111211111111111111111111111111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111121111112322211121212111111111111111111111111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111123311111111233321111221112111111111111111111111111111111111111111111111111111111111111112673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111211111112221464111111221111111111111111111111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111211111221246741221123211111111111111111111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111211111232367413431121111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111234543111113664366312311111111111111111111111111111111111111111111111111111111111111267311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111121124567653111236644752121111111111111111111111111111111111111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111113567764321375256431111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111367664124753673111111111111212111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111347523166257511111111111121111122111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111112111111122113752127612674111111111111221111111111111111111111111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111222111111211375315751267521111111111124421111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111136413662156532111111111112464111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111232333113643575157531111111111121355311111111111111111111111111111111111111111111112673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111234557788763478788657511111111111112466311111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111112467778888888768888888723442111111124566421111111111111111111111111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111112224688888888888888888888887888532445556664111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111114788888888888888888888888888886556765541111111111111111111111111111111111111111111111111111267311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111112111588888888888888888888888878888765432111111111111111111111111111111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111147888888888888888888888888888876655533311112111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111211114788888888888888888888888888874556655654311111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111122111246788888888888788888888755764111111456554321111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111212111346677888887766788888873133131112111245552112111111111111111111111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111112211111113445555533476667656641113111221211355522221111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111147511651367431111111111113653111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111113751166413675111111111111344311111111111111111111111111111111111111111111112673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111122221111374114652158511111111111112211111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111112221111247522266236631111111111111111111111111111111111111111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111112347762236625721111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111112225765654126645651111111111111111111111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111123567765311135643761111111111111111221111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111113466641112225753564111111111111111122111111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111234311122225652454211211111111111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111112321123125752123311111111111111111111111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111610000026060f002220574d4643010000000000010000000000000008000000002000008c8500008ce5000011111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111247522111111111111111111111111111111111111111111111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111125531211111111111111111111111111111111111111111111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111112221112221111111111111111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111221111111222111111111111111111111111111111111111111111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111112122111111111111211111111111111111111111111111111111111111111111111111111111112673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111211111111111111112111121111111121111122111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111121111111112111111222111111111111112112111112211111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121114741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111211111111123444433211111111111121221111111111111111111111111111111111111111111111112673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111122221211111234566666667776767666531111122111111111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111221121112456777665544444545666777665311111211111111111111111111111111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111255666654433111111111111234577765432121121111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112111474111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111124566665321111221112221111111112456676411112111111111111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111221135766432111111111111111111111211111145666521111111111111111111111111111111111111111111111126731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111122146753321111111111111111111111121111111134676411121111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111267641111111111111111111111111111111111111124676411221111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211147411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111567521111111111111111111111111111111111111111135774112211111111111111111111111111111111111111136721111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111123211113676311111111111111111111111111111111111111121111236763121111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111474111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111231114664211221111111111111111111111111111111111112111111257741121111111111111111111111111111111111111367211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111122111114764112222211111111111111111111111111111111111133211211576311111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111124564111232111111111111111111111111111111111111112321113114663111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111564111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111122124763111112211111111111111111111111111111111111112111111221146751111111111111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111113753211111111111111111111111111111111111111111111211111111111466412212212311111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111112211111111111111111111111111111111011111111113663111111111111111111111111111111111111111111111111111111122114664211111121111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111573111111111111111111111111111111111111111111111111111112223111121111111113331111111111111111111111111111100111111213672211111111111111111111111111111111111111111111111111111112211246621111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111157411111111111111111111111111111111111111111111111111111122221123111111111123311121111111111111111111111110111111122574112111111111111111111111111111111111111111111111111111112222112475222111111111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111122111113311111111111111111111111111111115741111111111111111111111111111111111111111111111111111111112211111222111111121221111111111111111111111111001111111575111111111111111111111111111111111111111111111111111111111111111125752111111111111111111111111111111113662111111111111111111111111111111111111111111111111111111111111111111111111331111111111111111111111111111111573111111111111111111111111111111111111111111111111111112111111145667776643211132111111111111111111111111101211111466111111111111111111111111111111111111111111111111111111111111122211277312222111111111111111111111111111266311111111111111111111111111111111111111111111111111111111111111111111111123111111111111111111111111111111157311111111111111111111111111111111111111111111111111111112112356876566777543211121111111111111111111111110011112256311111111111111111111111111111111111111111111111111111111111112211114751211221111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111457643221234566531111111111111111111111111111011111246511111211111111111111111111111111111111111111111111111111111222311212246411111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111366531111111114575411211111111111111111111111100122126621111111111111111111111111111111111111111111111111111111111111111111111673111111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111376321111111111234661111111122111111111111111110113114751111111111111111111111111111111111111111111111111111111111111111111111157511111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111116741111111111111111111111111111111111111111111111111111111257512111111111111157411112211111111111111111111001111662111111111111111111111111111111111111111111111111111111111111111111111113652111111111111111111111111111113662111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111137621221111111111213662111111112311111111111111101211365111111111111111111111111111111111111111111111111111111111111111111111121257411111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111115741111111111111122157411111111121121211111111110011166311111111111111111111111111111111111111111111111111111111111111111111112213652211111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111112663111111111111122114752211112211111111111111111011137511111111111111111111111111111111111111111111111111111111111111111111111211166321111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111375221111111111112211367211112211111111111111111100115741111111111111111111111111111111111111111111111111111111111111111111111111114651111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111137511111111111111111136621246666765442111111111110111664111111111111111111111111111111111111111111111111111111111111111111111111321376111111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111112851111111111111222223563467764446876531111111111001265211111111111111122111211111111121212211112212112111112212111123133112112111115621111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112211574111111111111111111122111121121111111231112132122111111175122111112221111221366666432111234577412211111101136411211111121111111111111112221112121212122221211111111111222111211221112121111563111111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147411111111111111111112211122121132122122111112212211211126632111111111111111138775311112111144763111111110014641111211111111121123112211113211112112112211111111111211112211111122211211111146411111111111111111111111111126721111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111113212211122211111111121112475111111111111111114884211111211111157631111111011564111121111111111135512353111111111211111111111111111121111111111111111112111114551111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111474111111111111111111111111111111112111111253111111111111127621211111111112213775111111111111112475111111100156311122112212112213663146533212122211122111122111221122221111121121231131111111366111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111221157411111111111111111133112332431121322344346433343112111111575311111111111113686111211111112222116731111110116531112313532553454247514876552475665676663156751455335454135345315545335511111115721111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114741111111111111111115532455465235478777778867666521311111125753111111111114677431111111122233212465111111001752111221464376446414862376566567577457567667666547744656614655751754765652121111673111111111111111111111111112672111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111763136657753746746745755756761221111111257622211111225766631111111221111111315511111101275211111147447745642687447424766656734765766744545773465673675677476367752112111167211111111111111111111111111367311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111177214665776475761463375466674112111111112477553223446652572111111111111111113551111110027521111113655555554475664641475366774686774677785565675478778565568448853111111116631111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111118611366374578477157157535467521111111121113587776788751256211111111111111111255211111012752111111477734666466248685457455467367556567457536347647635746546854776632112111673111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111674111111111111111111761136647457746625615754667642111111111222566665556675436611111111111111112115511111100175211111137863168656513657766534777635777733677524634653551364552475354564111111156311111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111176324762521453451451243355552111111111114565332111224675573111111111111111111651111110126631111213785214874321122424421245421224421133321446664222124242114323213312111116721111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111117766786121121112123111112333211111121114665211111111135677411111111111111111475111111001663111211366311366312311111231221111121112212212235546411111111111111221122111111662111111111111111111111111113663111111111111111111111111111111111111111111111111111111610000026060f002220574d4643010000000000010000000000000008000000002000008c6500008ce5000011111111111111111111111111111111111111111111111111115741111111111111111116666765112111111112111111111111111111137741111111111221488511111111111111111664111111011663112111233121143112211111211211131123212112212233112222121211211211111112211111661111111111111111111111111113673111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111222332211311121121112221111111111111125651111111211222114884111111111111111476211111100166411122111112111122111331111123112231112133112121121133112121122111111121111111266111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111112211111111111121112111111111115651221111111112111158741111111111111466311111110125631112311112111123211112112111221211121221111121133111111111221221331121211111126611111111111111111111111111136731111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111112111112211111121122112111221111111121575122121111111112214875311111112212267411111111001464111111111111111111111111111111111111111111111111111111111111111111111111112114651111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112211574111111111111111111111111111111111111111111111111111111376311221111111112211375655421112213576521111111101126511111111111111111111111111111111111111111111111111111111111111111111111111111564111111111111111111111111111266311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147411111111111111111111111111111111111111111111111111111137511122111111111122137646765443435775211111111110012653111111111111111111111111111111111111111111111111111111111111111111111111211166211111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111112761111111111111112314663135678777754311111111111012166411111111111111111111111111111111111111111111111111111111111111111111111111146611111111111111111111111111113662111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111474111111111111111111111111111111111111111111111111111112275111111111111111231376211234444431111112211111100114741111111111111111111111111111111111111111111111111111111111111111111111111115742111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111221157411111111111111111111111111111111111111111111111111111217621111111111111111137533311111111131211111111110112365211111111111111111111111111111111111111111111111111111111111111111111111121563211111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111663111111111111111114743111222112311122111111111001215741111111111111111111111111111111111111111111111111111111111111111111111122365221111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111564111111111111111111111111111111111111111111111111111111147511111111111112212563111111111111111112211111101111575111111111111111111111111111111111111111111111111111111111111111111111113156413111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111113762111111121111221466111111111111121111111111110021146631122111111111111111111111111111111111111111111111111111111111122111111137621211111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111146632111122111111476411111111111111111111111111011112565121231111111111111111111111111111111111111111111111111111111112211221125752111111111111111111111111111112663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111112466411111111111477511111111111111111111111111100111126732113311111111111111111111111111111111111111111111111111111111111122113653211111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111156411111111111111111111111111111111111111111111111111111111125664121212223675411111111111111111111111111110111311475111131111111111111111111111111111111111111111111111111111112211111111564221111111111111111111111111111136621111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111121112246654333345675311112111111111111111111111111001111115641111111111111111111111111111111111111111111111111111111111111111111475212211111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111112112211366767767664212112111111111111111111111111101211231366311131111111111111111111111111111111111111111111111111111111111111367311221111111111111111111111111111266311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147411111111111111111111111111111111111111111111111111111311111111124554311111122221111111111111111111111110011123214753121111111111111111111111111111111111111111111111111111111111111456521121111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111211111111111111111122123211111111111111111111111011111221167413111111111111111111111111111111111111111111111111111111121111257521122122111111111111111111111111113662111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111474111111111111111111111111111111111111111111111111111111123111112111111122111112111111111111111111111111100111111113674112211111111111111111111111111111111111111111122111111112221145721111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111221157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111112136731121112211111111111111111111111111111111111111111111111112137731111111111111111111111111111111111126631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111466321122112321111111111111111111111111111111111111111111111136741111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111124654123211132111111111111111111111111111111111111111111112246742111111111111111111111111111111111111366211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111147632211211111111111111111111111111111111111111111111111157631111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111112211112476311231111111111111111111111111111111111111111211111147631111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111474111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111221111114664321121111111111111111111111111111111111111111112356621111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111112211111146763212111111111111111111111111111111111111112211467511111111111111111111111111111111111111111136621111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111357754111111111111111111111111111111121111111324567411111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112211574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111211367642113221111111111111211111111122111121134676211111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111221147411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111121111466642232111121111111222111112111112111356763111111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111112211111567643111112111112311111111111111234577631111111111111111111111111111111111111111111111113662111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112211474111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111121111112567664321111112332111111111113456776411111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111212456776544321111111111112455677653111111121111111111111111111111111111111111111111111136631111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111122121111245666766655544556565667765311121221112111111111111111111111111111111111111111111113663111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111123211111111113556677776666776765421111112122211111111111111111111111111111111111111111111111366211111111111111111111111111111111111111211111111111111111111111111111111111111221111112211111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111113332211111111111111111111111111111111111111111111111111111111111111111136631111111111111111111111111111111111112121112111111111111111111111111111112221123211111221111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111222211111111111111111111111111111111111111111111111111111111111111111113663111111111111111111111111111111111112121111111111111111111112211112111111121111121111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111112111111111111111111111111111111111111111111111111111111111111111111111111111366311111111111111111111111111111111111111111111111111111111111211111111111111111111111221121122111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111112211111111111111111111111111111111111111111111111111111111111111111111111111136621111111111111111111111111121111111111121111111111111111111111121112111111111121111122212111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111212111111111111111111111111111111111111111111111111111111111111111111111111113663111111111111111111111112113321112111112111111111111111111111112211211111111112111111111111111111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111112331111111111111111111111111111111111111111111111111111111111111111111111111366311111111111111111112211311443221111121111111111111111111111111111111111111111111113211111111111111111111157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111354212111111111111111111111111111111111111111111111111111111111111111111111136631111111111111111112123131256454122355311222133211112111223454212322234433243123214554211111111111111111115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111235751121121121111111111111111111111111111111111111111111111111111111111111113663111111111111111111455213534665652465663653355464454245423666752374246566557524545656641111111111111112111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111121111221157622344122121111111111111111111111111111111111111111111111111111111111111366211111111111111122147711274475367477346477247637758514761573465347515755766874555772454122111111111111211157411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111124442211122575146411112111111111111111111111111111111111111111111111111111111111111136631111111111111112214761236446413567755647624764776751375157212223651476564677555577566413212211111111111114741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111112113566543112115753664111111111111111111111111111111111111111111111111111111111111111113663111111111111111221487123645651465774675761365574574147515722442475147566557458747835761111211111111111111574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111211235566665211357437611111111111111111111111111111111111111111111111111111111111111111366211111111111111121147611274577576456566378667646667656874477776568745766655734773576664211111111111111211147411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111123466764221564564122111111111111111111111111111111111111111111111111111111111111136621111111111111112114763146435576312566424666641576555676444665457655466632452134225654211111111111111121115741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111357733117735723211111111111111111111111111111111111111111

Рис. 1.

При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время t_>1>. Первый муравей в этот момент пройдет только половину пути (рис. 2).

Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время t_>2> второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рис. 3).

При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время t_>0>t_>2> путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время t_>4> первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.

010009000003e4d300000000c562000000001610000026060f002220574d4643010000000000010079cc00000000080000000020000074c0000074e00000010000006c0000000000000000000000f4000000960100000000000000000000ec1700004225000020454d460000010074e000000c00000001000000000000000000000000000000000500000004000040010000f000000000000000000000000000000000e2040080a90300460000002c00000020000000454d462b014001001c000000100000000210c0db010000006000000060000000460000005019000044190000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c00000000000000084000059c180000901800000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000f500000197040300000099d40bb300000018504c5445eaeae99b9b9b231f1f5d5c5cb6b5b57f7e7ed0d0d0ffffff9fca762000000001624b47440088051d480000000c636d50504a436d7030373132000000074f6db7a5000017ef4944415478daed9dcb7fda3a16c7cd14f0b6c438ac03ed5d171c67b6a1bcb621c6c91606305bf1b9c4faf7477e812c1dc9c75672bb98717b6f1a90fdf5efe8fd3ab268b3cba6b4bdedda0def4e2f6235bb2f0e56743f9eadfe0c7bbcbd78c7ef7f824d760ceeb8f77f824d692bd8ecfd8dfd47d864e71fc6e1e94fb00925e1e165f692fcbba1f8e6ba29e9cd5e7e276cb26c063760c7bde03e48127abcfe87d9ddc85e788b4df2cff3a6d9231ab2a3a5e3dddf8d5edf98e2ee228d745afb490dd80c174f86d9e5bdd168e19ffe49ddfb61713d1067bccc9ef40fb009d37d77650f7bee73fa71b7bef8da6c6bf15c62fb7d9bbd0ea1c7fa455c4d3639b8de8a678fd66b0667e96ce7d5ae57eab1ad9d377c60a8ff5cd94fd63cbc4fe29a380fdbaf64c72e4bdf49866a15e93cfccede273c25e9ac1d8c575fc966c89f767297e3059eef8dbcef76f24b5693b25ad5ae55b4d7621316cf4fd95b4451b73bed2dd2df5a493263e9ed3079fb3add5d6738ba0923f34594243c8b14e5f9deafd596a8c3b61c2f979db248cf7971b27a2cfbda2633ff190daec76e8da6a3d3edded8ddbd2d562501d6ece16b74b79da7f85680d8f4e077c7bd5339ccc5430bafc38e037f4bb82c7cf0c68be05108c4a265f5e96c9bb6bd7bbe75d4f6c64bc7791283c5c113ee8178366b9d39a50c44eefc6d1c1c5fa470ed009fdcb0363f26b534b956943143b41ea57e094beb7b745ac7b2535b72c5166b1f92d9cbce16c359b4fb8ab53ad6e6fb718ae159b17f026fde79a7cf63334bb742b9866c8d55267ab429e642b129098096415b5580eebcc127b25b5073507debec91622e547c93d913b111e18a2b0e51cd08149bc906d9caf759bc615aad289bbf7e871afeca3b59352396f30dd936edfcb4854f7284fa6a63ca17049bdc3dd56ef7c77dbb3a10827df14e8807098fdd3d5737dd10f13dfbab41e7beddff0cdd17efbb6072428875bb6c8ba47f8b5fb330f1a23ac6abd9b3bc5c2151378aa2e561ceaedef5eaf7e7e935cd3f73ef73f8aebad958c98ef3be0e69b96e2fcc2e3ff0922bf082305ce72fb1669f078117160dd9b8671bb25971fa903d83ccd6a1cb74b961f2639ecb9d47d1214afe5bb2bfc9ef87c929bf75b734d51d0779738538cf5177cbae2e8b54925fb4f8cf26d99b5272ad402f95a33055ec4bd1f623a8a28ad578abe25f6ed50d55ecce639ec1aa1f9505bb351c8e5529bd8aedbc90ab0c1bc52e74b36e9a19fb72adb849882bdd6eba2b2d55c1fef68e7e521eec1adf4c78c548849e4dee064599563fbee9a5a24bac67b77cbbae6e8e1d87b63eac96bdbfb53fb0798c6f2067bdd4666ce2dc1e84d6cdf15a7aa36bd9979bc99bd83ce93d346413fa8d6beba26dcee9a6b34143b6451cae9bd94437edbce99a756a36b15bfc731ae46f4acfbe6e4243a3dbde3f723736d21d07ba9b74f1ed0cf8df9ae8a6d2e000927df16cce5e4df237a51fba9e99867d2e8d5735d37de672691df6ec8d4f278de25b1fe11ab6535280d65d0ee6688a36259b08354133ddb433d68455ea6e9593494376ecd567133afb552a911ab28966e047a93b7e1d34620bf14deed4395cc9167347b3fc4d4bf51196fded971010c78e4576ecd767ffeb5d7886b66856eba68172124599d6824185209c6e9666577575c763e1659bc6b7a63a51b13be2806c8c4be7b127bc33fdf8ab2e7b2fb171369774db9791ea46255bec5320f3b7942459cb4bd52754b06595689b8bba65197ab67d1686f3f0e93c106f641d8c7a6c29ba937e28860d94df9d7a6ce20ee48f70bae5eec059ccae156cd972314e3750fc11d59499822dd7bae83c268b54556530fbb2960322eb1259b7fdb762e2086603491331569799470a66b714110eb39d77f9a16b94ee0bc0be8c6db05306b2a1711de236d5ad1c7f00d9d0c22ca46e208f11eac0b782eccb23df1bca1f8ad40db2e15215666f643641ea066c9e255d39ca417607982069ae9b956c702603d9bf5f00364e3754b6a88694213681a6cf4d742b123ac4be401d5793f856d40510fb038a1e13dd42a75ccb86ca7e93f82677ef68f62f20a0896eba076b32880d86ac1a98cd2f30ad24b30f48b6d825c9d8c8ba04645fc04e19c4065b09c8c5b7309b60d9177098026973389d9370856377c0129098c4b7bd7fc7b1e14489b639a49b76906cb8d36a14dfb435003ae112db22f0a0778c5b75acd68d6027637ad0aba3d9a06e568b22d83671c04938a4cd15af7879045a8b229bb0bb4148ac1b95add40de65059f7e501be1b37d673817513e86e39be5b7003c7a83c17078655ecd92ff066b3f8a633a0a92ab3ef146c33dd33a0c002d82bf06693728dc285a5c426339861a8bb85b2b9a20363528f256c8ceef8f54b74432d17897d5174960de3fb0c941a12bb052773c3724d1e9f85d81d05fb8263abe21b6a7a48ecd9d7e826401296ea92d22428cf568d92896c5837ddcbcf95d8aa2a036d734530605455642bb312dae68a77ff8660af15f3f4689b2b8201a3aa225bb5c05999efb1ec965cb888ecb38a8dd4ad1cb88de5c245642bd7579ada9cc8a224f69b617c2b07ace52fa4f856b19179cc44f751b559c034be49755a3baa26180ce3db22f238b4c8564eea18a73579bc47642b977d61f3b732983c6827b0d5b303a6e99cceaad8ea1919d3722d69a90a5f896ce58c8c697cd36f526b51642b5b65c6f12db79205f645b917c858b7bc8050609f95cb70d0f1adfae6fc5611df6763ddca6097cd1f648fc589907f8e2d37bad06c6c7c2b338adc72afc1c6a075baa5624b607f98b2956d2e60f25e601f35790ca95bcd162d22b0d5ab9791f1ad6c3b50b90217d8eac97d73dd556c79adc1e7b1abe2db98ad496b521529b24faa5bd505b5f08aaab7977b9965b66672005d872a7557b035832ac66c7900abccd6ec8c40c7b7ea1589bbd2b23f346c6c7c2bbf92a6dd04b67a41a771792eaf3c28b3fffea5baf113d8473d7b6fcc56e7ef2af6ef4fd0ad668b3b08cbec99717ceb744bce014a6cc79cadde772ed5cf653638fb5c8bad0926ad051474af8c75ab8349c3d882ee2f658bbe3eca6cf7a4dc8163cefef8a165cf4f5fa85bfaaacc8e6c63b67aa9fb596ff3a9b1ee4b63dd9a35a8e6baa59a10cd8e8d754bd54c99ad59077ac1f98bd0e88ebfdae63add6283acccd6acfb8d71cee574f1dd9c8db3b9467785cd35ec8bb96e2d9b68d61520d95f12dfc0f2e89abaa50e5999ad59c3824de71ab6d8402fdb5ca7dbb8dd22addcff6cb656b7966d6ef3f31f6437d7ad5957f0e5ba35eb0acee66cb125fa0fc63715a7d6d136ff6addbab51c5f1edf9a7d1ce6ba2b6cfeb5baf5694de30bf413e25b5b9ec79aba4a6a5d2b82a9ab5aa2b579fcb5baf5ec4f285b74ba575facfb4fb27579ec5dc3d696e79f90d6fe9c6e7d7bed33d29aa64fa46da77e6d1d2aed58f874b63abee3c6ed96af8e6f14bb6ba903e96d5ed156ac66c74e6f557e02e57db4344f6bbedaf75491bf3ba3e0ed706a3db7efbbf34364cd0ffdeed2dada852b6e4d7cebc71db4ec5cf7b71fc7b573bf7f9afd9c7a8137f79dd16edc9b2f8b4d0acdfbdf9ab662c1ee3c5dc270eca4aee782a1eb85a3993f72c685cf90e6631e9a3e51c16e31f6f3dda3b3597861cf5fcf0fe1221c053fdd3ca9686dae65eb7417f1fd573b3cdd3d048f0bcf7b1eaf4fedf5d11ffa9330dfd5df38ad69a6056f367fbc84fdc00f7bbdc05b86e166be9e79c371e015ba1b8f3b606c7e1f2f82b75d6f19f5a6cbded13bf4f6636fbd768bf86e6c73846e6b4b771bbbfd6c59dbee76db7ab4a2f6721e4545fda81b4f6d9ed66ef5777b9b3adc27ac48215b6ab13f841e4ea66ccdd81e772754a8160e433436ff14b6ee32d0bdfa4ab67efc7c61aebbb1cda776f621b061da5437a99827b20fd1328a2cd06f59cbd8e6472ddb72432f08d65b94c5eab375f382dd99e7f9e164b4894eb51e5a0aa68c6fb250ce03275ed3bd757f4be6d300f27e6dacbbe53d0a06bde926af7e3aec4048cb05cec53066efb3e32840f6d17fb6f35466cde4861b96ad5c08f66d387c87d8ac78de059cd6c485b990cd8cd339630f6036f14a03c01dc931b1b1cd3f94bacb1ece6de288cf6899ce515d14ba85130448b2385858ba6cac3b9e0c4fe54f72b6e0e19cfd732fb03aa66c3211fd0fe5369f495e9c63af3c176e5c9790095c8fb5c77219be782a7d621cdf74222e6049d816b871eb5236d127b00700db8ec1750ee5cd9a58b6dae6af2224b539ecc9b8ecb4c758b762cd20ec22ad9cbabe884de0652de505c4e66c708da86a5b5a69fcd338bee5330912b6aa9a282d023262dba437bd971a81091b5ebd45cae71a20d98a158f7bdff79ec5b32112b6726b24bf1506ab1b64b7bdcd7c265937612b5731f1cbf8b0ba419b3bac823e4beec8185bb9c4d0e6bd6b98e88e1996d03b600dd9c793caf123bfb7d144773649da01ea31b56f78fe410669cdce4ac8a41829bb26b5341d7ebe7469ce26c572c0d9a0bccb83581aefaa7c1d53e9bd3e6717e73af057fe98fdbbc4560f1ef3852db25f02d9bcd8e7bb179c99104b33604f38772a589b03fb4b8b327bff4ea7fc602cb1349b2f9bb021ddb9bae360e7f14d712d9bdf768165cbf14d72b6bd7b7edd1cb82e08b1ce9a45eddc12e20afff1926e2e37319ba703dd9dde78cbdabb579c5e37e78d029bce0b36f7d06b7c8f5e9219d9ab9e44b7fa495c83a6853b5deb5234b63976b14c2a3b4feb16798cbda1d6896e79235defe30ad59abac9966b2acc5ed2eaf3f77bc2b8798a26d6c75bb20139e9eddbe91f426fa7ca7162b1f19de7b14ec865b68f87440e9924f99bdcdaab4cf71bed3cc43f4fa4bb24ec8fdd3d75238bda1661c52d5791616d9ebfe26fef9a8c48be81f19857a2d7c5de8c7d4f3ba3cbc3fce0aedb7e373c2d96cbc57d77d95e1e963697b1d0656af6d359fbb6c5cc684509241810428a63c9be3df1ecd6e8f8b076fc703a998efa41e8bf8eddcdecded9f0436258dd99a949f0ec2ea7f7d1a197d6169d75bfe786f9c3ce3f7876c777367ef0b81b4fd69eeb079391e76d82b7d7ef7ce7b39ecd49b875c6139f094a3bfce46e3419cdf3e2adf5c0b3773ddf0dd7f7f1c37ebd719e0eaf6bafb70e5e58ce68a03b2bd788bb757d6f1df67a9394fdea05de739efaae993a4d6bfbf553e03c3aee90c552b0998e8e3fdbbe77fffa56ca63f5740791e307633f7283847d1c6fad63317276e6746f18fbade73cddfd74269be1fdcc7f383eb4c7ce72b6b17976ad7a8cb18307c7f39dd1eb7b22fb25714a937b59e8fc75657f6c68771bd9c173b86ccfad83d55e26873f6d23abbbe575776a95e7a4b79d2f23370c46fe8a7d98ce47b4f2a9a42397c792cc4368cfe24fb3ce0b25ae2ee9d48a6fda4dc6aebad66e932c69cf4652c9eb20fd71ed0e5ceb31cb023cef711e9d3a8deaef382d227367bdbf7f259a6e9e27aff518b8d18073c586d62d7f56b81960fd3bc20f1addea501bb8896b3bec9ab3afedb5f1b345c9ad5e66ed35c80ba5ccc6ead6b599dcf17d777a7339c8d8ea4950be9d8a8def92ee2c228bb6c3b11ffeec710396ac8dac63dfbeaa97c7cabaf366d2f1fb21f0fbb741f4a45fa2ec13f15b974ddaa9699596b6cf23fe4034c69e298f0f6c73cd2964997a86d21a63a7ba07e5cf19fb6fe5534b7d60833c96bb7a16dd2431b6bab7d3840d258b3cc98a8e1b193b0e542b2c66f5c71d209b2727c05060e37b36e601b34be36e06f14d3347e052ab2b1deb59d960917ae197f9ec70790c64a77d691b9c1f3b3ec1ecd224a2415a6346ef6fc9413a5a3361b7e1de7fe9382a6cfb1cd44ddbbd653495ce3a646ca2f03d56f6a7d2a9d74616aeeee110c9e2925c0f0f2c2615dc2d2a8c7427cd03f9b394ddf901c577e787dd40778d23df5376db831cd297f72d1bea56b2932e9204173cb12175b76ab3a15300846dcbc8764be73b2a18c796e751a4f583c8fabbbeeee4142171eef5adfc09b64cd5ea4e9f781d46cfd9f14498f78dc51df248dd1d58778e498ecebe1d1091db9c8823eb2d71f92032be5b605141e3ac504b4ae9d6e3a9fc42341eae4aefe98a2520328fc1f16d9fd35722c968d7e27b5937bb7e8f9f6f5339dda994f0b1690dd65d78cadcbf5cf8f1b5fc1f97607cba7e082cb6c0c637ccfefdefece7c723e75ceeb6d6e2108cf3e66bbcf0e59149239b93d79c1d6fb82ede956dd1cee83139ef77393f7a4f723167c48e27399bf6b9aece95cd9ad03b2f3dd9387c7d048a77a3f8ee5c9759acdd5b6f805b5b6393c374ea79fd39b8131ba91bcedfb361ae9b842e60f34c3c39b07c6d43b723db6ba06e7257e8266bf776949ce4c354b57ccec4e6e435d3cd4ad3108aefe277d571a38833b5d35784825d26c3ccf7ba457bf39352b7c2db3d3e9d43b79f87457cd31dd70c90d8e2197757dd06698de92ed8bfb9c941d94ff0bfc1679ac5f7dde83df9193fc793e1202e52baec1f59515f19e5b1fddb3689e5cecff670f8d2293ca9ca7ea115d3273b5c634891bf074922ef3ac3fe64f816f8f70ab6ca1f36960dda3c1de4228bf1e2c764e8fac764ac11621347c136c863d9ee8e96bf89fdc9d0fbde72b2e54a681fe446bad36ee0fed1ddde0d87a3ed6ceaabd80add06e93c4ed9879e17be0e8743d75b673b8b009ff366ba219b6767fcc4c1bcc7d0c3f1fd5df62c4037703012c5c737a83b6d9ab6d6b43b61ec173b3fd7133a6300661be88ed3017d7715c5097b70c87bd7325b3178b953bb30aa64a7ae342f1bfb354c6cee4f4eb30dccbec0de02b0baa160eda4e3d17ebe4c3c8fa5736ff2724ec75165b6c213b8497cef927652d7eedc47c7e1f0319a3e640c99ad706e81d40d464dba09c34ec615ff351cfea0c4dba60320d0f9252be8a1c80e2668f34366c9fd8035608623bb186784ceab01c7950dd239c95d10cdde4992ce57f4a8660f4cd880cd49d6b723af83943d280675a13382400a920d9e1d91e9be7827324c75cf94ec8e091bd49d0dad9dc734d13d5a91dc5d31c086c7b40d74c7590262adae44f7e854bc20c086974e1ae86e677dcc6e94e96645dc56c5a6a0374303dddd4c8bc50a3796c71eaefb9ec0f3c74ecdd947208f5d275a09fd4fc22e2e88fd0d2c1791bae560841b3ef9c6ca542d1bf4b2d89c1d73db4acefc460ff4397bcdd95d8e4d86dc9812c026a0b3e0e6ec36bf9de655cf86335973f68eaf1fa6dc0674f02c4b0770bb87654b1511e1873108bf2e1864ef5f9ab3a560ea35898af343e5cf76cf1473c9bad53309aa73539bb2db52b096d260f059b5c0503ed2e66d29d86e504f3790d01beb56efbd84cf07065685378eef85ad0a0b9f8b0c4c9835cd63a4af0c0bb3818d4b299bd0aa4b324f7ba90c0bb381920d5b87aec4fb4e35d9c0c9ab58b6a05be7764975eeb9f4b6d87e8910ac3e1b486cc8742eda3c562735155b5eddd030be5b9adb146c398737646b7694abd8f44e44616d3e28fd1aeb4e8957b18f0dd98b32fba2896e255b72668cb4b9c0d6ee5280d9366d89475735b3f951372aa7d22d1dd989640b1d688de304353be92397be6ac4be681c3e69d8df84237d90f15d66eb07fc956c319534d20d1cae87618b457a1336d146b7924de8ef97d2245d139b57f87b55eab63be5f1c526ba8ffaf755b2c5851e4dca35e7a4da1557c5764a34ac6e4e2a51afbaad60d37d29a523d9dcb4a27dae380243c32eb7d25bf5e35b35c58860973d07d54f6ba4ea24651d7bc1974af56d7eacdaa5af6197f709d74e6b65d70975d9a5d1ec435d9bb36657455742c72e1d7488d57d7ddd56e5412f5af6994be93836b76c40733e0586cdb756ebda3c9eacaac26ad9747fab0ceaeaee549f7da96773ab666bea26b3eaf9533d3bd94e5a8f5dd4256dc411ce15ecdb10637bd98da2a8cbfe97ecf8d95ad72bf9f87615fd900e625aa9821d5f7764b4dd30f4fd701d842efb11f6e6ec9af67abd3efb3cbd7c3ff93c2f8789e008b1099b5e176ec7f379429a277f13f092893cccfbf3e534f9749e7ddbefe763e5f1bcdae495ecf3b5954b721bdbd90f62db76fa837d4e6e3190872edcb119b149806ba795af585a6bde84cd6a23cc63840b591854b1635d0f5a750f26b6116cdad2f66bc00b591654b3e3b06e8cc707dcdb56b36b0b27854fd14f60cbcecbf45737420644b0e95174b2ab7f62840d8d61c78b1a8bca691b2b1bc5a66ddc39d4d98ba28a153c9b38b8cd06145ac06dc8a62d6cc94aa6fdd327b3ed4eb14ebae26a6bbcbf3664b37cb641250cb74eaa44b16dd6317411254cd7c52734bc6e5646bb958534996d703153974d776bcd295da9eac36dcbeb27b3c934bcaffade463eab2e9b76e7a90746d5835aebe5a916ba0e9b1067bc5505b7dae175efc617b0932ce46fe0ad855d37501fd0f3296cdaedc188d859f76a25f1066c4a76defa999495db64ead6aa651bb21357a47eafb7b96effb3a2696fead56fd23562b37a25f43cd607493b26d39eeb859822ef73d8c48aa25ee88d12ffe79ee7affbdb6ded673465a777455326def3c2f552eb79ff2bd82ca345acfb77880cc8cdd99f7135637fcef57ff6ffd9ff13ecff02909adf543190e73c0000000049454e44ae4260820000000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000075430080cb4303000000000080b3000080b3ffff7443000080b3000080b3ff7fcb432100000008000000620000000c00000001000000150000000c00000004000000150000000c0000000400000051000000c0c500000000000000000000f40000009601000000000000000000000000000000000000f500000097010000500000004c0000009c00000024c50000000000002000cc00f50000009701000028000000f5000000970100000100040000000000000000000000000000000000090000000000000000000000ffffff00e9eaea00b5b5b600d0d0d0007e7e7f005c5c5d009b9b9b001f1f2300111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111032111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211112443333334344222111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111244375566666666555734222111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222444477556686666666566666655773424222111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111610000026060f002220574d46430100000000000100000000000000080000000020000074a0000074e0000011111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111275655666677777334444444433777756655755321111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111276665777753222211111111111111224437773766532111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112476657321212111111111111111111111111112112377557411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111124775663211111111111111111111111111111111111111114765777421111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111123756553211112111111111111111111111111111111111111112475566321111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111212766742221111111111111111111111111111111111111111111111222355722111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111002111111111111111111111111111111111111111111111111111111111111111111111111111111111124336532211111111111111111111111111111111111111111111111111112275734411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111112375574111111111111111111111111111111111111111111111111111111111237557421111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100711111111111111111111111111111111111111111111111111111111111111111111111111111111475744211111111111111111111111111111111111111111111111111111111111244355311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111437532111111111111111111111111111111111111111111111111111111111111111112365342111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110061111111111111111111111111111111111111111111111111111111111111111111111211111137553211111111111111111111111111111111111111111111111111111111111111111112475732111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111123553221111111111111111111111111111111111111111111111111111111111111111111111237574111111111111111111111111111111111111111111111111111111111111111111111111111111111111111007111111111111111111111111111111111111111111111111111111111111111111111111212567421111111111111111111111111111111111111111111111111111111111111111111111111123654111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111112756721111111111111111111111111111111111111111111111111111111111111111111111111111123773411111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111276531111111111111111111111111111111111111111111111111111111111111111111111111111111112753411111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111123652111111111111111111111111111111111111111111111111111111111111111111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111114357411111111111111111111111111111111111111111111111111111111111111111111111111111111111111234411111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111455741111111111111111111111111111111111111111111111111111111111111111111111111111111111111111244411111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111123572111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111244411111111111111111111111111111111111111111111111111111111111111111111111111111110311111111111111111111111111111111111111111111111111111111111111111112753211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111224411111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111455721111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144321111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111127532111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111143321111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111114753111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111143321111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111456721111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111125672111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111753211111111111111112222222222222222122222222222212212121222222122112222212222222222222222222222111111111111143411111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111135721111111111111114333377777773337773337777333333344444444333733334377777733333333377777773737334211111111111143321111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111114553111111111111111237555556565555756557565655555773333333337777777737555555555555555656565655555554111111111111277311111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111111111156411111111111111112334244444442424444424444442422222222222222222222224444444444444444444444444447531111111111111257411111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111114651111111111111111143321111111111111111111111111111111111111111111111111111111111111111111111111135711111111111112357211111111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111112366411111111111111111433211111111111111111111111111111111111111111111111111111111111111111111111111367111111111111112365411111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111146531111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111123671111111111111112565211111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111112563111111111111111111143321111111111111111111111111111111111111111111111111111111111111111111111111136711111111111111114683111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111176521111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111112367111111111111111117652111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111111114564111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111113631111111111111111127672111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111276311111111111111111111143321111111111111111111111111111111111111111111111111111111111111111111111111136711111111111111111125631121111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111127671111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111367211111111111111111276541111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111112355411111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111114652111111111111111111456711111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111125541111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111136711111111111111111111256411111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111365211111111111111111111111273211111111111111111111111111111111111111111111111111111111111111111111111111367111111111111111111111266211111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111111146631111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111114652111111111111111111211767211111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111112763211111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111136721111111111111111111112662111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111125521111111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111357111111111111111111111117641112111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111212563211111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111113671111111111111111111111145721111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111121138522121111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111136711111111111111111111111135311111111111111111111111111111111111111111111111111111111111013111111111111111111111111111111111111111111111112564111111111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111367111111111111111111111111275411111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111176311111111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111113671111111111111111111111111467111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111112652112111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111136711111111111111111111111112554111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111146711122111111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111367111111111111111111111111113532111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111114564111111111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111113671111111111111111111111111117541111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111112111278721111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111145711111111111111111111111111145541111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111114664111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111357111111111111111111111111111176311111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111145721111111111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111113571111111111111111111111111111373111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111787211111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111145711111111111111111111111111114774111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111125631111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111453111111111111111111111111111117531111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111112763111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111114531111111111111111111111111111127721111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111136521111111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111145311111111111111111111111111111147311111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111112564111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111477211111111111111111111111111111277211111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111126621111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111114532111111111111111111111111111112772111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111465211111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111145311111111111111111111111111111114741111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111125671111111111111111111111111111111111477211111112111111111111111111111111111111111111111111111111111111111111111111473211111111111111111111111111111123341111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111365211111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112732111111111111111111111111111111127311111111111111111111111111111111111111111111111111100211111111111111111111111111111111111111125631111111111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111127321111111111111111111111111111111135211111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111365211111111111111111111111111111111111473211111111111111111111111111111111111111111111111111111111111111111111111111233211111111111111111111111111111111354111111111111111111111111111111111111111111111111110031111111111111111111111111111111111111114672111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112372111111111111111111111111111111114771111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111135321111111111111111111111111111111111147321111111111111111111111111111111111111111111111111111111111111111111111111123321111111111111111111111111111111127721111111111111111111111111111111111111111111111111007111111111610000026060f002220574d4643010000000000010000000000000008000000002000007480000074e0000011111111111111111111111111111125641111111111111111111111111111111111114732111111111111111111111111111111111111111111111111111111111111111111111111112732111111111111111111111111111111111354111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111465212111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111127721111111111111111111111111111111114572111111111111111111111111111111111111111111111111002111111111111111111111111111111111111117641121111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111273211111111111111111111111111111111123741111111111111111111111212211111111111111111111110111111111111111111111111111111111111111465211111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112772111111111111111111111111111111111147321111111111111111111111375741111111111111111111100111111111111111111111111111111111111215641111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111127721111111111111111111111111111111111234211111111111111111111115888311111111111111111111000111111111111111111111111111111111111155211111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111277211111111111111111111111111111111112442111111111111111111111288883111111111111111111110011111111111111111111111111111111111111662111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112772111111111111111111111111111111111114421111111111111111111117888852111111111111111111101111111111111111111111111111111111111126521111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111127721111111111111111111111111111111111123411111111111111111111268888631111111111111111111001111111111111111111111111111111111111564111111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111457411111111111111111111111111111111111134211111111111111112114888888711111111111111111110111111111111111111111111111111111111116511111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112752111111111111111111111111111111111111242111111111112212111158888887112111211111111111100111111111111111111111111111111111111465211111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111125521111111111111111111111111111111111112342111111111124441112688888862111134211111111111011111111111111111111111111111111111117631111111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111275211111111111111111111111111111111111114321111111111255411128888888641112552111111111110011111111111111111111111111111111111257211111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112552111111111111111111111111111111111111124411111111111767111268888886311226521111111111101111111111111111111111111111111111114672111111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111127521111111111111111111111111111111111111244211111111113664112888888883111367111111111111001111111111111111111111111111111111136711111111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111255211111111111111111111111111111111111112341111111111125871126888888871114671111111111110111111111111111111111111111111111111363211111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112574111111111111111111111111111111111111124421111111111136511268888888311145311111111111100111111111111111111111111111111121127631111111111111111111111111111111111111111127741111111111111111111111111111111111111111111111111111111111111111111111111125721111111111111111111111111111111111111143211111111111467112588888862111763111111111111011111111111111111111111111111111111256411111111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111475211111111111111111111111111111111111111434111111121114671112888888311126642441111111110011111111111111111111111111111111114552111111111111111111111111111111111111111114774111111111111111111111111111111111111111111111111111111111111111111111111112552111111111111111111111111111111111111114732111111242125744445888863443787145521111111101111111111111111111111111111111111136321111111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111125721111111111111111111111111111111111111123721211112332136866668888866668521765411111111001111111111111111111111111111111112563111111111111111111111111111111111111111111475211111111111111111111111111111111111111111111111111111111111111111111111111257411111111111111111111111111111111111111175411211113532158558888888865684136531111111110111111111111111111111111111111111136621211111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112574111111111111111111111111111111111111111473111111117531441468888888714314664111111111100111111111111111111111111111111111765212111111111111111111111111111111111111111147741111111111111111111111111111111111111111111111111111111111111111111111111125521111111111111111111111111111111111111114772111111127571124688888885221266311111111111011111111111111111111111111111111117841111111111111111111111111111111111111111111477211111111111111111111111111111111111111111111111111111111111111111111111111257411111111111111111111111111111111111111125741111111145633778888888867747872111111111110011111111111111111111111111111111176211111111111111111111111111111111111111111114754111111111111111111111111111111111111111111111111111111111111111111111111112752111111111111111111111111111111111111111473211111114377665558888888756657574111111111106611111111111111111111111111111111764111111111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111125521111111111111111111111111111111111111112732111111146637542788888864236376521111111111001111111111111111111111111111111127621111111111111111111111111111111111111111111477411111111111111111111111111111111111111111111111111111111111111111111111111257411111111111111111111111111111111111111147541111111276553146568886672277664211111111110111111111111111111111111111111111458211111111111111111111111111111111111111111114772111111111111111111111111111111111111111111111111111111111111111111111111112552111111111111111111111111111111111111111256311111111235673583688875654565311111111111100111111111111111111111111111111113652111111111111111111111111111111111111111111147721111111111111111111111111111111111111111111111111111111111111111111111111125741111111111111111111111111111111111111111367111111221247688736888545665741111111111111011111111111111111111111111111111276411111111111111111111111111111111111111111111275411111111111111111111111111111111111111111111111111111111111111111111111111257411111111111111111111111111111111111111114654421211111125852388885225872111111111111110011111111111111111111111111111112561111111111111111111111111111111111111111111112554111111111111111111111111111111111111111111111111111111111111111111111111112752111111111111111111111111111111111111111278865111111111143214688871147211111111111111101111111111111111111111111111111126621111111111111111111111111111111111111111111147541111111111111111111111111111111111111111111111111111111111111111111111111125741111111111111111111111111111111111111113688861111111111111113885211111111111111111111001111111111111111111111111111111465211111111111111111111111111111111111111111111275411111111111111111111111111111111111111111111111111111111111111111111111111275211111111111111111111111111111111111111178888611111111111111147531111111111111111111110111111111111111111111111111111123671111111111111111111111111111111111111111111114774111111111111111111111111111111111111111111111111111111111111111111111111112574111111111111111111111111111111111111111368885111211111112211773341121111111111111111100111111111111111111111111111111235411111111111111111111111111111111111111111111125541111111111111111111111111111111111111111111111111111111111111111111111111127521111111111111111111111111111111111111112588861111111111221115535311111111111111111111041111111111111111111111111211243654121211111111111111111111111111111111111111111475411111111111111111111111111111111111111111111111111111111111111111111111111275211111111111111111111111111111111111111127888511111111111111257757112111111111111111110011111111111111111122112433737666673333741111111111111111111111111111111111111112754111111111111111111111111111111111111111111111111111111111111111111111111112574111111111111111111111111111111111111111136886111111111111112557572111111111111111111101111111111111111212221476655565666555558632112111111111111111111111111111111111125541111111111111111111111111111111111111111111111111111111111111111111111111127521111111111111111111111111111111111111111258851111111111111115775321111111111111111111001111111111111112211258663333344443433456664111211111111111111111111111111111111275411111111111111111111111111111111111111111111111111111111111111111111111111277411111111111111111111111111111111111111111468611111111111111173353111111111111111111110111111111111111111435667421111111111111435657421111111111111111111111111111111112754111111111111111111111111111111111111111111111111111111111111111111111111112774111111111111111111111111111111111111111112586111111111111114533672111111111111111111100111111111111111135667411111111111111111127566721111111111111111111111111111111125541111111111111111111111111111111111111111111111111111111111111111111111111125521111111111111111111111111111111111111111113861111111111111156345641111111111111111111046111111111111113867321111221111111111111124376721111111111111111111111111111111255411111111111111111111111111111111111111111111111111111111111111111111111111275211111111111111111111111111111111111111111125621111111111114652136721111111111111111110011111111111111488311111111111111111111111111275341111111111111111111111111111112754111111111111111111111111111111111111111111111111111111111111111111111111112774111111111111111111111111111111111111111121175211111111121465211235722111111111111111101111111111121236671111111111111111111111111111276541211111111111111111111111111147641111111111111111111111111111111111111111111111111111111111111111111111111127521111111111111111111111111111111111111111111434111111111145631111276341111111111111111001111111111114687212111111111111111111111111111476721111111111111111111111111111255411111111111111111111111111111111111111111111111111111111111111111111111111257411111111111111111111111111111111111111111112221111111111237411111477211111111111111110111111111111266311121111111111111111111111111111175411121111111111111111111111112764111111111111111111111111111111111111111111111111111111111111111111111111111772111111111111111111111111111111111111111111111111111111111211111111122111111111111111100111111111125831111111111111111111111111111111111255211111111111111111111111111125541111111111111111111111111111111111111111111111111111111111111111111111111127741111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111112767211111111111111111111111111111111111457211111111111111111111111111476411111111111111111111111111111111111111111111111111111111111111111111111111257211111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111176521112111111111111111111111111111111111455211111111111111111111111112553111111111111111111111111111111111111111111111111111111111111111111111111112774111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111123662112111111111111111111111111111111111111767211111111111111111111111127541111111111111111111111111111111111111111111111111111111111111111111111111117741111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111258311121111111111111111111111111111111111112583211111111111111111111111255311111111111111111111111111111111111111111111111111111111111111111111111111135411111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111113652111111111111111111111111111111111111111113652111121111111111111111112754111111111111111111111111111111111111111111111111111111111111111111111111111774111111111111111111111111111111111111111111112222111111111111111111111111111111111111100111121276711111111111111111111111111111111111111111146641111111111111111111111125531111111111111111111111111111111111111111111111111111111111111111111111111113741111111111111111111111111111111111111111112443434411111111111111111111111111111111111011111123664111111111111111111111111111111111111111111276521111111111111111111111275411111111111111111111111111111111111111111111111111111111111111111111111111177411111111111111111111111111111111111111112377344437341111111111111111111111111111111110011111456421111211111111111111111111111111111111111111456311111111111111111111112764111111111111111111111111111111111111111111111111111111111111111111111111111374111111111111111111111111111111111111111136734212437321111111111111111111111111111111101111117631211112111111111111111111111111111111111111111355211111111111111111111147541111111111111111111111111111111111111111111111111111111111111111111111111117741111111111111111111111111111111111111114563111112135721111111111111111111111111111111001111156312111111111111111111111111111111111111111111112763111111111111111111111276411111111111111111111111111111111111111111111111111111111111111111111111111177411111111111111111111111111111111111111276721111111275311111111111111111111111111111110111114564121111111111111111111111111111111111111111111113662111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111774111111111111111111111111111111111111113654111111111455411111111111111111111111111111100111176311111111111111111111111111111111111111111111111125641111111111111111111127641111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111111111111111111111111111176311111111111367111111111111111111111111111111011111664111111111111111111111111111111111111111111111111256411111111111111111111276411111111111111111111111111111111111111111111111111111111111111111111111111137411111111111111111111111111111111111112554121111111114671111111111111111111111111111110011136641211111111111111111111111111111111111111111111112367111111111111111111112764111111111111111111111111111111111111111111111111111111111111111111111111111774111111111111111111111111111111111111146521221111111145711111111111111111111111111111101311563211111111111111111111111111111111111111111111111114554111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111111111111111111111111111465212221111111467111443411111111111111111111111001126541111111111111111111111111111111111111111111111111127641111111111111111111255411111111111111111111111111111111111111111111111111111111111111111111111111135411111111111111111111111111111111111114672111111111114572435665734211111111111111111110851465411111111111111111111111111111111111111111111111111276311111111111111111112563111111111111111111111111111111111111111111111111111111111111111111111111111374111111111111111111111111121111111111146521111111111145735585777663111111111111111111100114662111111111111111111111111111111111111111111111111112353111111111111111111125641111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111111111111111111111111111457211111111111457567742437553111111111111111111011136521111111111121111111111111111111111111111111111111123531111111111111111111476411111111111111111111111111111111111111111111111111111111111111111111111111137411111111111111111111111111111111111114552111111111114667322211124652111111111111111110011365211111111112111111111610000026060f002220574d4643010000000000010000000000000008000000002000007460000074e0000011111111111111111111111111111111367111111111111111111125641111111111111111111111111111111111111111111111111111111111111111111111111113741111111111111111111111111111111111111256311111111111466411121111256711111111111111111011176721111111112222221111111111111111111111111111111111113672111111111111111111256311111111111111111111111111111111111111111111111111111111111111111111111111135411111111111111111111111111144211111111785211111111113862112211111466211111111111111110011753111111121177223421111111111111111111112211111111111145721111111111111111112564111111111111111111111111111111111111111111111111111111111111111111111111111374211111111111241112211224224753442111114554111111111258711111111112767111111111111111101115531124424421563255342333224322233444244444424422244211255411111111111111111125541111111111111111111111111111111111111111111111111111111111111111111111111113541111111111127742333444755556866531111113554111111127864111111111114552111111111111111001175311465754777664788576685388743665874587236776343653212554111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111137311111111111256445687766665768658511111125852111114588721111111111125841111111111111110141754114657645676637675887657655653378645852365667458541125541111111111111111112764111111111111111111111111111111111111111111111111111111111111111111111111111354111111111112564476655667654475565111111145674222455653211111111111178711111111111111100117741147776575555774148746575376644358576677575652564111256311111111111111111127641111111111111111111111111111111111111111111111111111111111111111111111111113742111111111127542756566575577776851111111125866566632731111111111111767111111111111111011177411256576536556634767685766756556688666665356545872112567111111111111111111276411111111111111111111111111111111111111111111111111111111111111111111111111135411111111111255427667686557766588511111111278866886335721111111111127871111111111111110011774112786458757766555376837867356556558677553367476531125631111111111111111112764111111111111111111111111111111111111111111111111111111111111111111111111111373111111111112563275343774444377664111111125577377755563111111111111178311111111111111101117741125861387334375572365245541353434357424342334433421276311111111111111111127531111111111111111111111111111111111111111111111111111111111111111111111111113741111111111117657652122211121224411111112567112121256632111111111112664111111111111111001175411258714854112243412341234212441244422112122121222112564111111111111111111276411111111111111111111111111111111111111111111111111111111111111111111111111135411111111111138666521111111111111111211136521111111456631111111111176521111111111111110111554112754125321111121112111211112111242111111111111111127641111111111111111112754111111111111111111111111111111111111111111111111111111111111111111111111111373111111111111255573111111111111111111111587112111111268711121111212583111111111111111100117531122411142111211111111111111111111211111111111111111255411111111111111111127531111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111242221111111111111111111136521221111111385112111111146611111111111111111011176711111111111111111111111111111111111111111111111111114552111111111111111111276411111111111111111111111111111111111111111111111111111111111111111111111111137411111111111111211111111111111111111112564111111111114667211111112763111111111111111110011365211111111111111111111111111111111111111111111111111146521111111111111111112753111111111111111111111111111111111111111111111111111111111111111111111111111354111111111111112111111111111111111111146521111111111146865211111275721111111111111111101117672111111111111111111111111111111111111111111111111111457211111111111111111127541111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111112111111111111111111111465211211111121257767421125672111111111111111111001136521111111111111111111111111111111111111111111111111113531111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111137421111111111111111111111111111111111214572111111111214732585343567211111111111111111110311365211111111111111111111111111111111111111111111111111236311111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111354111111111111111111111111111111111111145721111111111145714766666321111111111111111111100114572111111111111111111111111111111111111111111111111112363111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111113731111111111111111111111111111111111111465211111111111465111377731111111111111111111111011125721111111111111111111111111111111111111111111111111127631111111111111111111176311111111111111111111111111111111111111111111111111111111111111111111111111135411111111111111111111111111111111111114552111111111114671112111111111111111111111111110011266411111111111111111111111111111111111111111111111111456311111111111111111112753111111111111111111111111111111111111111111111111111111111111111111111111111374211111111111111111111111111111111111115631111111111146512121111111111111111111111111100011564111111111111111111111111111111111111111111111111114654111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111111111111111111111111121156711111111111367121211111111111111111111111111001114532111111111111111111111111111111111111111111111111135311111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111135411111111111111111111111111111111111121465411111111127631111211111111111111111111111110111115641121111111111111111111111111111111111111111111112554111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111353111111111111111111111111111111111111111363111111112585211111111111111111111111111111100111136721111111111111111111111111111111111111111111112125641111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111117541111111111111111111111111111111111111114663111121178641111111111111111111111111111111011111156311111111111111111111111111111111111111111111111466211111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111135311111111111111111111111111111111111111117663211117663111111111111111111111111111111110011111767111111111111111111111111111111111111111111111145632111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111754111111111111111111111111111111111111111123665333366711111111111111111111111111111111101111113652111111111111111111111111111111111111111112112585211111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111113541111111111111111111111111111111111111111114665656632122111111111111111111111111111111001111127671111111111111111111111111111111111111111111146641111111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111175311111111111111111111111111111111111111112112773774111211111111111111111111111111111110111111146521111111111111111111111111111111111111111111767111111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111753111111111111111111111111111111111111111111111111112211111111111111111111111111111111100111111276311111111111111111111111111111111111111111146541111111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111117631111111111111111111111111111111111111111111111111277211111111111111111111111111111111011111111455211111111111111111111111111111111111111111767111111111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111112664111111111111111111111111111111110011111112753111111111111111111111111111111111111111146541111111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111126641111111111111111111111111111111101111112114563111111111111111111111111111111111111111783111111111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111117531111111111111111111111111111111111111111111111111258311111111111111111111111111111111001111122113662111111111111111111111111111111111111138521111111111111111111111111276311111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111111687111111111111111111111111111111110111111111123671111211111111111111111111111111111113564211111111111111111111111112763111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111116862111111111111111111111111111111100111111111123674111111111111111111111111111111111466411211111111111111111111111117671111111111111111111111111111111111111111111111111111111111111111111111111117531111111111111111111111111111111111111111111111111268871111111111111111111111111111111011111111111127654112211111111111111111111121111146671111111111111111111111111111256711111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111112688521111111111111111111111111111110011111111111127654111111111111111111111112111114663211111111111111111111111111111767111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111146888411111111111111111111111111111101111111111122127654111111111111111111111112112766311111111111111111111111111111127631111111111111111111111111111111111111111111111111111111111111111111111111117631111111111111111111111111111111111111111111111111388887111111111111111111111111111111001111111111221126663211111111111111111111111256672121111111111111111111111111111176711111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111115888851111111111111111111111111111110111111111112211147567211111111111111111111145663211211111111111111111111111111112767111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111268888711111111111111111111111111111100111111111111111114565322111112111111111223665211111111111111111111111111111111117671111111111111111111111111111111111111111111111111111111111111111111111111117641111111111111111111111111111111111111111111111112688885111111111111111111111111111111011111111111111111112586577211111111212277566721111111111111111111111111111111111176711111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111146888852111111111111111111111111111110011111111111111112112356665773421233375656532111111111111111111111111111111111111767111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111276663421111111111111111111111111111101111111111111111111111243666666555688653444111111111111111111111111111111111111117631111111111111111111111111111111111111111111111111111111111111111111111111117531111111111111111111111111111111111111111111111111235721111111111111111111111111111111001111111111111111111111122755566565657421111111111111111111111111111111111111111176711111111111111111111111111111111111111111111111111111111111111111111111111176311111111111111111111111111111111111111111111111111455411111111111111111111111111111110111111111111111111111111214344344444221111211111111111111111111111111111111111112767111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111114563111111111111111111111111111111100111111111111111111111111137211111111111121112111111111111111111111111111111111117671111111111111111111111111111111111111111111111111111111111111111111111111117631111111111111111111111111111111111111111111111121125631111111111111111111111111111111011111111111111111111111111354111111111111111111111111111111111111111111111111111176711111111111111111111111111111111111111111111111111111111111111111111111111175311111111111111111111111111111111111111111111111111176711111111111111111111111111111110011111111111111111111111117531111111111111111111111111111111111111111111111111111767111111111111111111111111111111111111111111111111111111111111111111111111111763111111111111111111111111111111111111111111111111111787111111111111111111111111111111104111111111111111111111111175411111111111111111111111111111111111111111111111111117671111111111111111111111111111111111111111111111111111111111111111111111111117631111111111111111111111111111111111111111111111111117671111111111111111111111111111111001111111111111111111111111754111111111111111111111111111111111111111111111111111176711111111111111111122211111111111111111111111111111111111112111211111111111175311111111111111111111111111111111111111111111111111176711111111111111111111111111111110761111111111111111111111115541111111111111111111111111111111111111111111111111111787111111111111111111234211122111111211211112421122112211121143411111111111111763111111111111111111111111111111111111111111111111111767111111111111111111111111111111100111111111111111111111111156411111111111111111111111111111111111111111111111111117671111111111112242114753212332222242244242276322442334334444763111111111111117631111111111111111111111111111111111111111111111111117671111111111111111111111111111111011111111111111111111111112554111111111111111111111111111111111111111111111111111176711111111111127741435565447773444773734774566437746676657577554111111111111175311111111111111111111111111111111111111111111111111136711111111111111111111111111111110011111111111111111111111115641111111111111111111111111111111111111111111111111111767111111111111256313557356655577775666345555533357366688675666652111111111111763111111111111111111111111111111111111111111111111111367111111111111111111111111111111101111111111111111111111111165411111111111111111111111111111111111111111111111111117871111111111112584235541788756633566663267574123574565886568558641111111111117631111111111111111111111111111111111111111111111111114572111111111111111111111111111111001111111111111111111111111554111111111111111111111111111111111111111111111111111176711111111111127641355327863765335665577655733435535558656857565211111111111175311111111111111111111111111111111111111111111111111136711111111111111111111111111111110111111111111111111111111116541111111111111111111111111111111111111111111111111111767111111111111256413555567766556666666568875665586366586766776541111111111111763111111111111111111111111111111111111111111111111111467111111111111111111111111111111100111111111111111111111111265412111111111111111111111111111111111111111111111111117671111111111112683455776744664368537665666336576864767773334367111111111111117631111111111111111111111111111111111111111111111111113572111111111111111111111111111111011111111111111111111111112654121111111111111111111111111111111111111111111111111178711111111111125865654434127322374243343442233437324342242212441111111111111175311111111111111111111111111111111111111111111111111136721111111111111111111111111111110011111111111111111111111126521111111111111111111111111111111111111111111111111111767111111111111147677311111111111111111111111111112111111211111111111111111111763111111111111111111111111111111111111111111111111111457211111111111111111111111111111101111111111111111111111111255211111111111111111111111111111111111111111111111111117671111111111111124222111111111111111111111111111111111111111111111111111111117631111111111111111111111111111111111111111111111111114754111111111111111111111111111111001111111111111111111111112552111111111111111111111111111111111111111111111111111176711111111111111111111111111111111111111111111111111111111111111111

В этом и состоит базовая идея алгоритма муравья - оптимизация путем непрямой связи между автономными агентами.

2. Пошаговое описание общей схемы

Предположим, что окружающая среда для муравьев представляет собой полный неориентированный граф. Каждое ребро имеет вес, который обозначается как расстояние между двумя вершинами, соединенными им. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении (рис. 4).

010009000003ee3c000000001b1b000000001610000026060f002220574d464301000000000001001e7e000000000300000000200000b8220000b8420000010000006c0000000000000000000000a3000000a3000000000000000000000003100000030f000020454d4600000100b84200000c00000001000000000000000000000000000000000500000004000040010000f000000000000000000000000000000000e2040080a90300460000002c00000020000000454d462b014001001c000000100000000210c0db01000000600000006000000046000000e80a0000dc0a0000454d462b224004000c000000000000001e4009000c00000000000000244001000c000000000000003040020010000000040000000000803f214007000c0000000000000008400005340a0000280a00000210c0db01000000000000000000000000000000000000000100000089504e470d0a1a0a0000000d49484452000000a4000000a40403000000eb9b987200000018504c54450a0a0af6f6f6a2a2a2c5c5c5e2e2e2484848777777ffffffb40a88c400000001624b47440088051d480000000c636d50504a436d7030373132000000074f6db7a5000009894944415468deed9acb73aacc12c0ad9ccfec5b8dbd4d4ea26ef352d79828db130d641b3d82eb96f99c7fff760f28a0bc342ceeadba54aae2037ef674f7f40b1afa8243bd5805df362e414e7db76e64efb537ae19f9acbdba91389bd7bdf0c0bbc39a91d305d48dbc5dfdae194943dfb76b96b2f3fe5ef0ed45c8e2e3222440cde62126529d5292eea00676779d873d1f89d0f9bd7ad202ad6fe1c346e30aeb44c2f64fa3d158b2b8f521a74c6c5cd52825c1a3209b88f521f5b741da75202124ea5b41366a41a25936bc4552e69e7726927dd2118337ae31f7bcf3744913df5d8d04f90f400d484b77facefc412b5e79f38eac1a909d37dff96d13e1ec4fe3978eccf523e43b8bf8a449f18afdfea25ad8c01cfd8934a85e3ce7de36ef117d5da9da008df2b3c75a8710d9ee3babd7705b93a695ee61052469842ca4bc57cf9ebbe6950a927f81e67a38ae827cb1f054e724ea6011fda7fd778c0c16fa665301d972add3c510e71835f2dc7b4ce89ab60bbdfba8809c5c9f9a503e78f3dc9525af709fc268fba9d5a2cac2fd2cafe8f43dffdea4443ae804761b8dae86bc181c3b918f073d6204a7097b8e65b4185f0e381b107a3695ba3ab9f61ec42281c590f6c8715f32ae993272f8509e2894136b908845e84c8c739f6803d98350df7c9623c98d9525c437f69c57cc485aa07b4fa8d944e5e679de23a59a10e7fecb8ba7539331d266d79a972335e2e1729af0fe7b8a2a8b132479f2cfaf902868bf17a9c3cefd80e1fe3eb98e40b9f2616f5c8edc2f8b5abee3cbe939fa8770cdd34d3192b0f3fe1a5e007dde7fbae08070e7743f8afd12f4d071ef582ce2c8fd373fba9a2330c820d73e1152ea9c6b5bbf0fddb9485b84c4d07f945bb27b7a92f5d613479c1b0b9184dda579e1d98548657273d3995b25220af2df8179311c14228310f9606a27566951298e53c3c29b0d61a65344c846584170896b5243a1a05192d8c92e2f40864589492c4512867a0f91b9264f2f9c811d2821626817ca4dbc91ab9b6acce148015886243f42f6ec22a41e0af269e2b9af59912275a8483a0acd9487c436afbc39a676cf5997a99275684e81ee120b90802ddf9ff146531cd5ac32a4a91034b472b264b470f61d549ecd7a7c91c587e569b610c1df504a540b2a429a73864b6e37a12d298740c267a6a5b6e17ee4d8e26129327025ca218dfeac2ce3c599c8ee528493c5f7c6548ce4ede58d45039c271cffc1ce0bc1b34d84c4e1a6584a0174ff91cd03b66e73d4b4720acee961fac2510e0a91fcc706e26dce5a447a76dca7ecad3e1ceced162c0ac2c65e9bd3a5c40d73e2244c69a287d405c81a8c402a7b4ba6915b970e76ee18173d8e22c8a1f7f049f6964c21096fb9dcd95f01bf1dc91a6975b10d0f0d29666fc9141260b788eb0b2e623ce7e1a8e0409a1f04c7d9a61c49e4c44507868b4f2f0ed53cb6c976518a645f9b6ef6be63d2809a88e5139ac17602a3aea29f2ed02567df58083267b74c3311233958c467f47909a6144d762247e601ed0de21f0845e93b0ba9e1d0a411dd5a1f2a6a4231b9f965d439485167f7483f8c79966654b6bfc5cad82de3020f0f8937e9bdc748524eba7e91ce8723f3bde9d200b1bb4920671f07a4ce456a982ed39152a21c8d4c64e605b22fc65e261d90b1622a0e9e20692be563cc24512369def3afeca288892283a3b66bbea4772c40f245bdbb645c639321b718f8c68bb740a7ba47c0305b7656c9659d4a89dda304c0ae255b88a6d2ec4a8f4b3aeaab90a663f9c9d1356181792412dbd9b97ce6cd5fa1af4d640991fa86154fe0b9c928973535986e723299e2c5fb62f6e82751da538460be4aae2b0bd99ee7750bead9b9b662e3a10e3eb9479a2e5dbbc02f8d36bff3ba05a0b7265b5ec78e3807b26fddc613411192ebbc5f9940cec49d60ee4b8f7540f62cb027fd663257662149676768f1eadd970adbac5052781cd8fcf1ea6070ca41e26c99bd700299404c7c4e4b52de72e6bbf9929947ec22943727e222213be572a18e66cf7327635c69fb29f68f7d885f6522917a83ecc200febd9335aa3e172492f2d5717b9a8704dd5d64fb116f1794dc43cf9c96d8c915faef56326628c844322c77078d6c6910787fca308a2da3be399324760659d97e29c135a785f7655c211589a699cce0765c3dcf1348b072a42408dc6cf3f81805117e2365a34c719b833dcf7c95331904ec6db28c0ef344534def7dc7344c7b97035340e7216137d7a783544a1b18b599b137f64a0afd3d6f7ec955dc38c340c7fdd3d620d319300f897af895315c4ad71740bbea48855c24647cbe4b3902c036b5f042a43469dfe3d3cfbba9cd4f14768a9b2a482921ba1945d47473f48171a27115a48c5c9563ebe38e7b3a48e857a6a32e8bb94e7b5bc1c49acb6cc2a32c344a0904fa71cd7b287d4a21722b7dd011d24ea6781d5cdb206d6c4529f95a6f707c77d04b21f1f1c3bc4d37dc055202577194d625b99074d6e05a160147f7160a90325db38f3e4ad500bab7e660661aa5aaba046e54d36a52a91a990b320c67ba957549b8bd52c9c422fd58fc35b290850d5ff621d39684aa9248d83a881720794f270dd25a2716d1fb509909aa18c965762a077537b1a6b7ae9d18cc564682e69e3b71d96c108b35fca4ec9b5d25521287b884b74f0707bdb6640e7f0192d3ab97aca086fba861696f997251a88ce4b5ae13c8dbf1fe0bd6641243af5811a9a58f4f143cfb069c4350ba103b0ba96f0f83070d3eee85bc3e6ab8ac7390dbabc3cbce61f2c04296df49c93b287e2a27cee21c82ec7428ad6c1e6dead77d0284609f8d7a4bb9a9742952873710e47232ed3dc9d8cb86bcdb9655905cc52da37146ebcbbc9798573038ad7003568a8450a4688b074df8199255f66d87529abb8ff9b56755a4785ff733f4c1702e1434edc2a976058b4b880b5f3d8ee53f0bf933a4398677fa301d390aa11722697b453232f044bad167c9d9d5901c2fa49673499f26e20b9172db911d692e85529990d59052a171afd3594843342ebb895111a91f07285b9ca60b5d0b921d69fb8bec2dd72b65e6ae2c254988c3dd87de2d242de2cf91d273dd7ca8e9a62363f2779b7e8ee4430573af71355c98aeae0657374758e8cb3c52d783249276a4a955eedde1f3912dd3340da8e49ee2390b0f1bd04d3423ae11f9411d9d9f6ecf44de18e45785332b23bb8dd36ef167483237548fbac59f2195b9557955e5d4ca52ea963c9155275246fdcedf9280712e521ee324d0e5d4339f1984a0e889e08b907a58aecf3391ca19fd2a3be74c64f0102ccace3977e1f43da81949eddebaec9c7317be56d923c31f20af26a59bf2dc857bceb2ec9c73cdd3beaf2f518447d96322972c1cb06ea43c975737b27cddff350feaff1ff93f8cfc0fa87a43cd55d2051b0000000049454e44ae426082000840010824000000180000000210c0db01000000030000000000000000000000000000001b40000040000000340000000100000002000000000000bf000000bf000024430000244303000000000000b3000000b3ffff2343000000b3000000b3ffff23432100000008000000620000000c00000001000000150000000c00000004000000150000000c00000004000000510000006c3600000000000000000000a3000000a300000000000000000000000000000000000000a4000000a4000000500000004c0000009c000000d0350000000000002000cc00a4000000a400000028000000a4000000a40000000100040000000000000000000000000000000000090000000000000000000000ffffff00e2e2e200c5c5c500f6f6f6004848480077777700a2a2a2000a0a0a0011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114444441111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144441141111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111441111141111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114373141111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111146555641111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111138727871111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111136212564111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144375621111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111468711111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111137213531111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125536831111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113585741111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111441377411111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111114411114114441111411111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111111476556311411111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111114114788888574111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111112146888888887111111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111114138888888885311111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111468888888888611111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111458888888888511111111111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111258888888888541442111114441111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111258888888888611111144114411111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111114478888888888711411141111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111114145888888885111241411111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111111117888888885311441441111441111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111111111112135765888735531111444441441111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111141141411455412256142653111442221141111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111144141411653141165411165314444411411111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111114411117831421176211145521441111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111144111138714144135311142553114441111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111144111356441414425311111465314441111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111114114552141141115711114125521111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111114147521444144115614114412562111111111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111111111114178714411414416544411111365211111111111111111111111111111111111111111111111111111111111111040411111111111111111111111111111111111111111111111111111111111111111111111111357411111114417521111114125521441111111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111441111412551111111114413831111111113552114441111111111111111111111111111111111111111111111111111111050511111111111111111111111111111111111111111111111111111111111111111411111146521411111111112571111111111385214441111111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111114411168214441111111114561111111144135521111111111111111111111111111111111111111111111111111111111070411111111111111111111111111111111111111111111111111111111111111111111441757114111111111114661111111111113854411441111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111114413564144441111111114751111111144141356411441111111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111144125641111141111111144353111111141141135621441141111111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111441265211111111111111441353111111111111117564444444144111111111111111111111114411111111111111111111010111111111111111111111111111111111111111111111111111111111111111111411653111111111111111141257111111111111111386412114414111111111111111111111114411111111111111111111010111111111111111111111111111111111111111111111111111111111111111111117871111111111111111114256111111111111111138641114441111111111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111111111178714441111111111111114466411111111111114417864111141111111111111111111111142441111111111111111111010111111111111111111111111111111111111111111111111111111111111111111256144111111111111111111475211111111111114411386411111111111111111111111111143241111111111111111111010111111111111111111111111111111111111111111111111111111111114411112662141111111111111111111178311111111111111144175621114411111111111111111111143241111111111111111111010111111111111111111111111111111111111111111111111111111111114444146531141111111111111111111135714411111111111124116564144111111111111111111111114411111111111111111111010111111111111111111111111111111111111111111111111111111111111414175711444111111111111111111125712411111111111111114756211411441111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111114411356111141111111111111111111126714111111111111111111135521444441111111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111412552144111111111111111111111146611111111111111111114117562141411411111111111111111111111111111111111111010111111111111111111111111111111111111111111111111111111111111116521144144411111111111111111147621111111111111111111441755412414111111111111111111111111111111111111111010111111111111111111610000026060f002220574d464301000000000001000000000000000300000000200000b8020000b842000011111111111111111111111111111111111111111111753111111424111111111111111111135314111111111111111114441755414144111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111441144117871244111441111111111111111111135314111111111111111114414175621144111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111141444135641141111111111111111111111111125714411111111111111114111117564141114411411111411111111111111111111111110101111111111111111111111111111111111111111111111111111114441256211111111111111111111111111111145614411111111111111111111111756211142414411444441111111111111111111111110101111111111111111111111111111111111111111111111111111144444653141441111111111111111111111111145644144411111111111111111111138641411111441424111111111111111111111111110101111111111111111111111111111111111111111111111111111441116571444441111111111111111111111111116521144111111111111111111114413854144111111141441111111111111111111111110101111111111111111111111111111111111111111111111111111141175611144141111111111111111111111111113621144111111111111111111114111386214442411111411111111111111111111111110101111111111111111111111111111111111111111111111111111141256414414441111111111111111111111111113631111111111111111111111111441138622655574111111111111111111111111111110101111111111111111111111111111111111111111111111141441112552111411441111111111111111111111111112571441111111111111111111114441113565888886211411111111111111111111111110101111111111111111111111111111111111111111111111411114146531111111111111111111111111111111111112561111111111111111111111111111111788888888531111111111111111111111111110101111111111111111111111111111111111111111111114441441168311111111111111111111111111111111111114664111111111111111111111111141413588888888861111111111111111111111111110101111111111111111111111111111111111111111111111241441757111111111111111111111111111111111111111652111111111111111111111111444417888888888852111111111111111111111111110101111111111111111111111111111111111111111111111141113551144411111111111111111111111111111111111753111111111111111111111111441416888888888853111111111111111111111111110101111111111111111111111111111111111111111111111114126531441111111111111111111111111111111111111357111111111111111111111111111117888888888853111111111111111111111111110101111111111111111111111111111111111111111111114444165711444411111111111111111111111111111111141257111111111111111111111111411125888888888852111111111111111411111111110101111111111111111111111111111111111111111111114441756111114111111111111111111111111111111111114457111114411111111111111114227655888888888864111111111111114424111111110101111111111111111111111111111111111111114111144413564111111111111111111111111111111111111111114166411144411414111411111143655573788888888571111111111111114444411414110101111111111111111111111111111111111111144111144135521111111111111111111111111111111111111111111166211411111441144411142655573411168888885744411111111111111111114424110101111111111111111111111111111111111111114111111465214411111111111111111111111111111111111111111136214411444414141143765567211441126855563444411111111111111111111424110104111111111111111111111111111111111111111144114653414111111111111111111111111111111111111111111425314114444111143765557244144412416622241144111111111111111111111244110101111111111111111111111111111111111111111141147571144111111111111111111111111111111111111111114415744114111112765867241444414412125711111111111111111111111111111441110104111111111111111111111111111111111111111111135611114111111111111111111111111111111111111111114115714141114375556341111144114411175241414411144111111111111111111441110101111111111111111111111111111111111111111441266411111111111111111111111111111111111111111111144445611111276656724141144144411444455141111414214411111111111111111411110101111111111111111111111111111111111111111411654111111111111111111111111111111111111111111441144116511276556734111111111144111144387121144114674114111111111111111411110101111111111111111111111111111111111111111116831111111111111111111111111111111111111111111444144213576656632411114411111111111111752444212776853114111111111111111111110401111111111111111111111111111111111111144168314111111111111111111111111111111111111111111111441423855632411111114411111111111111574414217856883414441111111111111111110101111111111111111111111111111111111111114357414111111111111111111111111111111111111111111111123755862411114111111111111111411113521414442564562111141111111111111111110701111111111111111111111111111111111111112561444111111111111111111111111111111111111111111112755573661144414144111111111111411116541141441357671411111111111111111111110101111111111111111111111111111111141441146521441111111111111111111111111111111111111111112665573244761114441144114411111111411145641144144465561441111111111111111111110101111111111111111111111111111111111441465314111111111111111111111111111411444114141114255567321111754111141114114411111111411425311441444136861441141111111111111111110101111111111111111111111111111111144141757411144111111111111111111114414441444414412375557324441111353111111111111111111111444166211111111142674111111111111111111111110101111111111111111111111111111111111417564111114111111111111111111114114114411411375556324114144141357111111111111111111144411256411441141114224144111111111111111111110101111111111111111111111111111111114425641144411111111111111111111111144444111436556724111141114141257114111111111111111144141753111441144111441144111111111111111111110401111111111111111111111111111111141255411114111111111111111111111114114111437555731114441111444141466114111111111111111114412654111111111111114411111111111111111111110101111111111111111111111111111111444653111111111111111111111111111144111437555772111114414224144114166414111111111111111114413571111111111111114411141111111111111111110506111111111111111111111111144144116571111111111111111114111111111111127655532411411441111444111411476244144111111111111114417521111114111141114111441111111111111111110101111111111111111111111111141144175714411111111111111114111141111147655662411111111111111111144141475311144111111111111111147621111144241141111144441111111111111111110404111111111111111111111111411141256111411111111111111441144111122755563411111111111111111111144141435311111111111111111111128711111111411111111111111111111111111111110101111111111111111111111111441414554141141111111111111141111142765567211111111111111111111111111141125714411111111111111111175311111111111111111111111111111111111111110104111111111111111111111111444416531414111111111111111144112365557241141411111111111111111111111141145714444111111111111141266111111111111111111111111111111111111111110101111111111111111111111111144178711441411111111111111144775557321111441111111111111111111111111141146541414111111111111141257111111111111111111111111111111111111111110101111111111111111111111111411756144411441111111111114276556724111444411111111111111111111111111141116521411111111111111111752111111111111111111111111111111111111111110101111111111111111111111111412564414411441441111111276556724111111144111411111111111111111111111111417531144111111111111112561111111111111111111111111111111111111111110101111111111111111114111114126521411441144444411437555634111411111111111111111111111111111111111111113571444111111111111113531441111111111111111111111111111111111111110101111111111111111114411111468211144441442111436655632411411111111111111111111111111111111111111111112574411111111111111117521144111111111111111111111111111111111111110101111111111111111111144114653111441144111427556672211114411111111111111111111111111111111111111111112661141111111441114135611111111111111111111111111111111111111111110101111111111111111111114113561114414241143658672441114111114411111111111111111111111111111111111111114664141111111441111175311411111111111111111111111111111111111111110101111111111111111111114135644444414443655573211444144444114411111111111111111111111111111111111111111764111111111141111465411111111111111111111111111111111111111111110101111111111111441144411265214411113365563211114111111144411111111111111111111111111111111111111111111363114111111111411253141111111111111111111111111111111111111111110101111111111144414766662653111112765567241111111111111111111111111111111111111111111111111111111111111357144111111411444753111111111111111111111111111111111111111111110101111111111141435888888531144375556241111111111111111111111111111111111111111111111111111111111111111357114111111111444664411111111111111111111111111111111111111111110101111111111111358888888834276556321142411111111111111111111111111111111111111111111111111111111111111256111111111111142571111111111111111111111111111111111111111111110404111111111114688888888855566324444144111111111111111111111111111111111111111111111111111111111111111466211111111114117521111111111111111111111111111111111111111111110101111111111113588888888885721114444244111111111111111111111111111111111111111111111111111111111111114165211111111114115611111111111111111111111111111111111111111111110505111111111113588888888886111444111444411111111111111111111111111111111111111111111111111111111111111175311111111111135711111111111111111111111111111111111111111111110101111111111113888888888886411441441144441111141111111111111111111111111111111111111111111111111111111135311111111111165214411141111111111111111111111111111111111111110404111111111113588888888885724141411111144111444111111111111111111111111111111111111111111111111111114125711111111141456114411441111111111111111111111111111111111111110101111111111112588888888885555724111111141111111111111111111111111111111111111111111111111111111111144115711111111111357111111111111111111111111111111111111111111111110204111111111111758888888862275555732111411111141111111111111111111111111111111111111111111111111111144146641111111111652111111111111111111111111111111111111111111111110101111111111144175888888621112235565732111111141111111111111111111111111111111111111111111111111111114117521111111112564411111111111111111111111111111111111111111111110101111111111144113555567414411114236655634111141111111111111111111111111111111111111111111111111111111113531111111113571111111111111111111111111111111111111111111111110101111111111114414222321111111111444476655673111111111111111111111111111111111111111111111111111111114412531111111146544411111111111111111111111111111111111111111111110101111111111111111111111111111111441114476655664111111114411111111111111111111111111111111111111111114412571111111125614111111111111111111111111111111111111111111111110101111111111111111111144444111111111111144236655672411111441114444111111111111111111111111111111111144412564111111175314111111111111111111111111111111111111111111111110101111111111111111111414114111111111111111114277655673411111411424111111111111111111111111111111111114414651111111166414111111111111111111111111111111111111111111111110101111111111111111114371144111111111111144444441237655663241141141411111111111111111111111111111111114411752141111257111111111111111111111111111111111111111111111111110101111111111111111114561144111111111111114414144411237655663241111441111111111111111111111111111111114411753441111752111111111111111111111111111111111111111111111111110101111111111111111112551111111111111111141114141444114227655573211114111111111111111111111111111111114111353141114552144111111111111111111111111111111111111111111111110101111111111111111114562114111111111111144444144424114111433655563311111111111111111111111111111111111111257114413572144111111111111111111111111111111111111111111111110101111111111111111111664144111111111111111141141111111111111427655573241111114411411111111111111111114441267114416521144411111111111111111111111111111111111111111111110201111111111111111114661114111111111111111111111111111111111111427665667311114444441411441111111111111144166111415611441441111111111111111111111111111111111111111111110101111111111111111127861114111111111111111111111111111111111411111123655667241114111141444111111111111114175211125311111111111111111111111111111111111111111111111111110101111111111111111147562441111111111111111111111111111111111114444111123665567341111111411111111111111114175311165411111111111111111111111111111111111111111111111111110101111111111111111114332441111111441111111111111111111111111111141141111143765566341111114411111111144411135311456111111111111111111111111111111111111111111111111111110101111111111111111114114144111111444411111111111111111111111111114444111111123765566241111414411111144411145711353111111111111111111111111111111111111111111111111111110101111111111111111144114114111111444411111111111111111111111111114411144411111143765567321114411111111411146711754111111111111111111111111111111111111111111111111111110101111111111111111111114111111111111111111111111111111111111111111111144411111141123365557321111111111441416611561111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111122765557341114124444116676531141111411111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111422366557721141441265888831111114411111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111241142765557721112688888857414241111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111142766566736888888888244441111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111411111114442775558888888888641111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111411111111444442368888888888521111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111441111111114111178888888888821414111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111141168888888888521414111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144438888888888541414111111111111111111111111111111111111111111111110808111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114425888888888711114111111111111111111111111111111111111111111111110401111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114417588888886411144111111111111111111111111111111111111111111111110808111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114358888874111114111111111111111111111111111111111111111111111110401111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144144427767341111114111111111111111111111111111111111111111111111110805111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111141142411144111141111411111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114444444141111111111111111111111111111111111111111111111111111110401111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114444444111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114222221111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111143566662111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111117867774111111111111111111111111111111111111111111111111111110101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111117201000026060f00da02574d4643010000000000010000000000000003000000b802000000000000b842000025534441111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113657441111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111141265711111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111137116531111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111175327531111111111111111111111111111111111111111111111111111101041111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125665611111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112332411111111111111111111111111111111111111111111111111111101014c000000640000000000000000000000a3000000a30000000000000000000000a4000000a40000002900aa0000000000000000000000803f00000000000000000000803f0000000000000000000000000000000000000000000000000000000000000000220000000c000000ffffffff460000001c00000010000000454d462b024000000c000000000000000e000000140000000000000010000000140000000400000003010800050000000b0200000000050000000c02a400a400030000001e00040000000701040004000000070104001b1b0000410b2000cc00a400a40000000000a400a4000000000028000000a4000000a40000000100040000000000000000000000000000000000090000000000000000000000ffffff00e2e2e200c5c5c500f6f6f6004848480077777700a2a2a2000a0a0a001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111411111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111444444111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114444114111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144111114111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111437314111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114655564111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113872787111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113621256411111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114437562111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111146871111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113721353111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112553683111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111358574111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144137741111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111441111411444111141111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111147655631141111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111411478888857411111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111214688888888711111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111413888888888531111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111146888888888861111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111145888888888851111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111125888888888854144211111444111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111125888888888861111114411441111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111447888888888871141114111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111414588888888511124141111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111788888888531144144111144111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111213576588873553111144444144111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111114114141145541225614265311144222114111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111114414141165314116541116531444441141111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111441111783142117621114552144111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111114411113871414413531114255311444111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111114411135644141442531111146531444111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111411455214114111571111412552111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111414752144414411561411441256211111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111417871441141441654441111136521111111111111111111111111111111111111111111111111111111111111104041111111111111111111111111111111111111111111111111111111111111111111111111135741111111441752111111412552144111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111144111141255111111111441383111111111355211444111111111111111111111111111111111111111111111111111111105051111111111111111111111111111111111111111111111111111111111111111141111114652141111111111257111111111138521444111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111441116821444111111111456111111114413552111111111111111111111111111111111111111111111111111111111107041111111111111111111111111111111111111111111111111111111111111111111144175711411111111111466111111111111385441144111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111441356414444111111111475111111114414135641144111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111114412564111114111111114435311111114114113562144114111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111144126521111111111111144135311111111111111756444444414411111111111111111111111441111111111111111111101011111111111111111111111111111111111111111111111111111111111111111141165311111111111111114125711111111111111138641211441411111111111111111111111441111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111787111111111111111111425611111111111111113864111444111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111117871444111111111111111446641111111111111441786411114111111111111111111111114244111111111111111111101011111111111111111111111111111111111111111111111111111111111111111125614411111111111111111147521111111111111441138641111111111111111111111111114324111111111111111111101011111111111111111111111111111111111111111111111111111111111441111266214111111111111111111117831111111111111114417562111441111111111111111111114324111111111111111111101011111111111111111111111111111111111111111111111111111111111444414653114111111111111111111113571441111111111112411656414411111111111111111111111441111111111111111111101011111111111111111111111111111111111111111111111111111111111141417571144411111111111111111112571241111111111111111475621141144111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111441135611114111111111111111111112671411111111111111111113552144444111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111141255214411111111111111111111114661111111111111111111411756214141141111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111652114414441111111111111111114762111111111111111111144175541241411111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111117531111114241111111111111111111353141111111111111111144417554141441111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111114411441178712441114411111111111111111111353141111111111111111144141756211441111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111414441356411411111111111111111111111111257144111111111111111141111175641411144114111114111111111111111111111111101011111111111111111111111111111111111111111111111111111144412562111111111111111111111111111111456144111111111111111111111117562111424144114444411111111111111111111111101011111111111111111111111111111111111111111111111111111444446531414411111111111111111111111111456441444111111111111111111111386414111114414241111111111111111111111111101011111111111111111111111111111111111111111111111111114411165714444411111111111111111111111111165211441111111111111111111144138541441111111414411111111111111111111111101011111111111111111111111111111111111111111111111111111411756111441411111111111111111111111111136211441111111111111111111141113862144424111114111111111111111111111111101011111111111111111111111111111111111111111111111111111412564144144411111111111111111111111111136311111111111111111111111114411386226555741111111111111111111111111111101011111111111111111111111111111111111111111111111414411125521114114411111111111111111111111111125714411111111111111111111144411135658888862114111111111111111111111111101011111111111111111111111111111111111111111111114111141465311111111111111111111111111111111111125611111111111111111111111111111117888888885311111111111111111111111111101011111111111111111111111111111111111111111111144414411683111111111111111111111111111111111111146641111111111111111111111111414135888888888611111111111111111111111111101011111111111111111111111111111111111111111111112414417571111111111111111111111111111111111111116521111111111111111111111114444178888888888521111111111111111111111111101011111111111111111111111111111111111111111111111411135511444111111111111111111111111111111111117531111111111111111111111114414168888888888531111111111111111111111111101011111111111111111111111111111111111111111111111141265314411111111111111111111111111111111111113571111111111111111111111111111178888888888531111111111111111111111111101011111111111111111111111111111111111111111111144441657114444111111111111111111111111111111111412571111111111111111111111114111258888888888521111111111111114111111111101011111111111111111111111111111111111111111111144417561111141111111111111111111111111111111111144571111144111111111111111142276558888888888641111111111111144241111111101011111111111111111111111111111111111111141111444135641111111111111111111111111111111111111111141664111444114141114111111436555737888888885711111111111111144444114141101011111111111111111111111111111111111111441111441355211111111111111111111111111111111111111111111662114111114411444111426555734111688888857444111111111111111111144241101011111111111111111111111111111111111111141111114652144111111111111111111111111111111111111111111362144114444141411437655672114411268555634444111111111111111111114241101041111111111111111111111111111111111111111441146534141111111111111111111111111111111111111111114253141144441111437655572441444124166222411441111111111111111111112441101011111111111111111111111111111111111111111411475711441111111111111111111111111111111111111111144157441141111127658672414444144121257111111111111111111111111111114411101041111111111111111111111111111111111111111111356111141111111111111111111111111111111111111111141157141411143755563411111441144111752414144111441111111111111111114411101011111111111111111111111111111111111111114412664111111111111111111111111111111111111111111111444456111112766567241411441444114444551411114142144111111111111111114111101011111111111111111111111111111111111111114116541111111111111111111111111111111111111111114411441165112765567341111111111441111443871211441146741141111111111111114111101011111111111111111111111111111111111111111168311111111111111111111111111111111111111111114441442135766566324111144111111111111117524442127768531141111111111111111111104011111111111111111111111111111111111111441683141111111111111111111111111111111111111111111114414238556324111111144111111111111115744142178568834144411111111111111111101011111111111111111111111111111111111111143574141111111111111111111111111111111111111111111111237558624111141111111111111114111135214144425645621111411111111111111111107011111111111111111111111111111111111111125614441111111111111111111111111111111111111111111127555736611444141441111111111114111165411414413576714111111111111111111111101011111111111111111111111111111111414411465214411111111111111111111111111111111111111111126655732447611144411441144111111114111456411441444655614411111111111111111111101011111111111111111111111111111111114414653141111111111111111111111111114114441141411142555673211117541111411141144111111114114253114414441368614411411111111111111111101011111111111111111111111111111111441417574111441111111111111111111144144414444144123755573244411113531111111111111111111114441662111111111426741111111111111111111111101011111111111111111111111111111111114175641111141111111111111111111141141144114113755563241141441413571111111111111111111444112564114411411142241441111111111111111111101011111111111111111111111111111111144256411444111111111111111111111111444441114365567241111411141412571141111111111111111441417531114411441114411441111111111111111111104011111111111111111111111111111111412554111141111111111111111111111141141114375557311144411114441414661141111111111111111144126541111111111111144111111111111111111111101011111111111111111111111111111114446531111111111111111111111111111441114375557721111144142241441141664141111111111111111144135711111111111111144111411111111111111111105061111111111111111111111111441441165711111111111111111141111111111111276555324114114411114441114114762441441111111111111144175211111141111411141114411111111111111111101011111111111111111111111111411441757144111111111111111141111411111476556624111111111111111111441414753111441111111111111111476211111442411411111444411111111111111111104041111111111111111111111114111412561114111111111111114411441111227555634111111111111111111111441414353111111111111111111111287111111114111111111111111111111111111111101011111111111111111111111114414145541411411111111111111411111427655672111111111111111111111111111411257144111111111111111111753111111111111111111111111111111111111111101041111111111111111111111114444165314141111111111111111441123655572411414111111111111111111111111411457144441111111111111412661111111111111111111111111111111111111111101011111111111111111111111111441787114414111111111111111447755573211114411111111111111111111111111411465414141111111111111412571111111111111111111111111111111111111111101011111111111111111111111114117561444114411111111111142765567241114444111111111111111111111111111411165214111111111111111117521111111111111111111111111111111111111111101011111111111111111111111114125644144114414411111112765567241111111441114111111111111111111111111114175311441111111111111125611111111111111111111111111111111111111111101011111111111111111141111141265214114411444444114375556341114111111111111111111111111111111111111111135714441111111111111135314411111111111111111111111111111111111111101011111111111111111144111114682111444414421114366556324114111111111111111111111111111111111111111111125744111111111111111175211441111111111111111111111111111111111111101011111111111111111111441146531114411441114275566722111144111111111111111111111111111111111111111111126611411111114411141356111111111111111111111111111111111111111111101011111111111111111111141135611144142411436586724411141111144111111111111111111111111111111111111111146641411111114411111753114111111111111111111111111111111111111111101011111111111111111111141356444444144436555732114441444441144111111111111111111111111111111111111111117641111111111411114654111111111111111111111111111111111111111111101011111111111114411444112652144111133655632111141111111444111111111111111111111111111111111111111111113631141111111114112531411111111111111111111111111111111111111111101011111111111444147666626531111127655672411111111111111111111111111111111111111111111111111111111111113571441111114114447531111111111111111111111111111111111111111111101011111111111414358888885311443755562411111111111111111111111111111111111111111111111111111111111111113571141111111114446644111111111111111111111111111111111111111111101011111111111113588888888342765563211424111111111111111111111111111111111111111111111111111111111111112561111111111111425711111111111111111111111111111111111111111111104041111111111146888888888555663244441441111111111111111111111111111111111111111111111111111111111111114662111111111141175211111111111111111111111111111111111111111111101011111111111135888888888857211144442441111111111111111111111111111111111111111111111111111111111111141652111111111141156111111111111111111111111111111111111111111111105051111111111135888888888861114441114444111111111111111111111111111111111111111111111111111111111111111753111111111111357111111111111111111111111111111111111111111111101011111111111138888888888864114414411444411111411111111111111111111111111111111111111111111111111111111353111111111111652144111411111111111111111111111111111111111111104041111111111135888888888857241414111111441114441111111111111111111111111111111111111111111111111111141257111111111414561144114411111111111111111111111111111111111111101011111111111125888888888855557241111111411111111111111111111111111111111111111111111111111111111111441157111111111113571111111111111111111111111111111111111111111111102041111111111117588888888622755557321114111111411111111111111111111111111111111111111111111111111111441466411111111116521111111111111111111111111111111111111111111111101011111111111441758888886211122355657321111111411111111111111111111111111111111111111111111111111111141175211111111125644111111111111111111111111111111111111111111111101011111111111441135555674144111142366556341111411111111111111111111111111111111111111111111111111111111135311111111135711111111111111111111111111111111111111111111111101011111111111144142223211111111114444766556731111111111111111111111111111111111111111111111111111111144125311111111465444111111111111111111111111111111111111111111111101011111111111111111111111111111114411144766556641111111144111111111111111111111111111111111111111111144125711111111256141111111111111111111111111111111111111111111111101011111111111111111111444441111111111111442366556724111114411144441111111111111111111111111111111111444125641111111753141111111111111111111111111111111111111111111111101011111111111111111114141141111111111111111142776556734111114114241111111111111111111111111111111111144146511111111664141111111111111111111111111111111111111111111111101011111111111111111143711441111111111111444444412376556632411411414111111111111111111111111111111111144117521411112571111111111111111111111111111111111111111111111111101011111111111111111145611441111111111111144141444112376556632411114411111111111111111111111111111111144117534411117521111111111111111111111111111111111111111111111111101011111111111111111125511111111111111111411141414441142276555732111141111111111111111111111111111111141113531411145521441111111111111111111111111111111111111111111111101011111111111111111145621141111111111111444441444241141114336555633111111111111111111111111111111111111112571144135721441111111111111111111111111111111111111111111111101011111111111111111116641441111111111111111411411111111111114276555732411111144114111111111111111111144412671144165211444111111111111111111111111111111111111111111111102011111111111111111146611141111111111111111111111111111111111114276656673111144444414114411111111111111441661114156114414411111111111111111111111111111111111111111111101011111111111111111278611141111111111111111111111111111111114111111236556672411141111414441111111111111141752111253111111111111111111111111111111111111111111111111111101011111111111111111475624411111111111111111111111111111111111144441111236655673411111114111111111111111141753111654111111111111111111111111111111111111111111111111111101011111111111111111143324411111114411111111111111111111111111111411411111437655663411111144111111111444111353114561111111111111111111111111111111111111111111111111111101011111111111111111141141441111114444111111111111111111111111111144441111111237655662411114144111111444111457113531111111111111111111111111111111111111111111111111111101011111111111111111441141141111114444111111111111111111111111111144111444111111437655673211144111111114111467117541111111111111111111111111111111111111111111111111111101011111111111111111111141111111111111111111111111111111111111111111111444111111411233655573211111111114414166115611111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111227655573411141244441166765311411114111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111114223665577211414412658888311111144111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111112411427655577211126888888574142411111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111427665667368888888882444411111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111114111111144427755588888888886411111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111114111111114444423688888888885211111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111114411111111141111788888888888214141111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111411688888888885214141111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111444388888888885414141111111111111111111111111111111111111111111111108081111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144258888888887111141111111111111111111111111111111111111111111111104011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144175888888864111441111111111111111111111111111111111111111111111108081111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111143588888741111141111111111111111111111111111111111111111111111104011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111441444277673411111141111111111111111111111111111111111111111111111108051111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111411424111441111411114111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144444441411111111111111111111111111111111111111111111111111111104011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111144444441111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111142222211111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111435666621111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111178677741111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125534441111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111113657441111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111141265711111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111137116531111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111175327531111111111111111111111111111111111111111111111111111101041111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111125665611111111111111111111111111111111111111111111111111111101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112332411111111111111111111111111111111111111111111111111111101010c00000040092900aa00000000000000a400a40000000000040000002701ffff030000000000

Рис. 4.

Вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромонов на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьев двигается по локально-оптимальному маршруту. Избежать этого можно моделируя отрицательно обратную связь в виде испарения феромона. Причем, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарений может привести к получению устойчивого локального оптимального решения.

3. Муравей

Муравей - это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона, по имени математика сэра Уильяма Гамильтона.

Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.

Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи, так как для каждой задачи способ размещения муравьев является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.

На этом же этапе задается начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.

4. Начальная популяция

После создания популяция муравьев поровну распределяется по узлам сети. Необходимо равное разделение муравьев между узлами, чтобы все узлы имели одинаковые шансы стать отправной точкой. Если все муравьи начнут движение из одной точки, это будет означать, что данная точка является оптимальной для старта, а на самом деле мы этого не знаем.

5. Движение муравья

Движение муравья основывается на одном и очень простом вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующей грани пути используется уравнение :

(2.1)

Здесь _> > - интенсивность фермента на грани между узлами r и u, _> >-Функция, которая представляет измерение обратного расстояния для грани, a -вес фермента, а b- коэффициент эвристики. Параметры a и b определяют относительную значимость двух параметров, а также их влияние на уравнение. Вспомните, что муравей путешествует только по узлам, которые еще не были посещены (как указано списком табу). Поэтому вероятность рассчитывается только для граней, которые ведут к еще не посещенным узлам. Переменная k представляет грани, которые еще не были посещены.

6. Путешествие муравья

Пройденный муравьем путь отображается, когда муравей посетит все узлы диаграммы. Обратите внимание, что циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана - она равна сумме всех граней, по которым путешествовал муравей. Уравнение показывает количество фермента, который был оставлен на каждой грани пути для муравья k. Переменная Q, является константой.

_>> (2.2)

Результат уравнения является средством измерения пути, - короткий путь характеризуется высокой концентрацией фермента, а более длинный путь - более низкой. Затем полученный результат используется в уравнении 2.3, чтобы увеличить количество фермента вдоль каждой грани пройденного муравьем пути.

_>> (2.3)

Обратите внимание, что данное уравнение применяется ко всему пути, при этом каждая грань помечается ферментом пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни фермента, в противном случае истинная длина пути останется неизвестной. Константа р - значение между 0 и 1.

7. Испарение фермента

В начале пути у каждой грани есть шанс быть выбранной. Чтобы постепенно удалить грани, которые входят в худшие пути в сети, ко всем граням применяется процедура испарения фермента. Используя константу р из уравнения 2.3, мы получаем уравнение 2.4.

(2.4)

Поэтому для испарения фермента используется обратный коэффициент обновления пути.

8. Повторный запуск

После того как путь муравья завершен, грани обновлены в соответствии с длиной пути и произошло испарение фермента на всех гранях, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по сети, основывая выбор грани на уравнении 2.1. Этот процесс может выполняться для постоянного количества путей или до момента, когда на протяжении нескольких запусков не было отмечено повторных изменений. Затем определяется лучший путь, который и является решением.

9 Блок-схема алгоритма

10. Демонстрационный пример

Разберем функционирование рассмотренного выше алгоритма на простом примере, чтобы увидеть, как работают уравнения. Возьмем простой сценарий с двумя муравьями из примера который рассмотрели в п. 1. На рис. 5 показан этот пример с двумя ребрами между двумя узлами (V0 и V1). Каждое ребро инициализируется и имеет одинаковые шансы на то, чтобы быть выбранным.

Рис. 5. Рис. 6.

Два муравья находятся в узле V0 помечаются как A0 и A1. Так как вероятность выбора любого пути одинакова, в этом цикле мы проигнорируем уравнение выбора пути. Данные для задачи:

число пройденных шагов: для A0 − 20, для A1 − 10

уровень феромона (Q/пройденное расстояние): для A0 − 0.5, A1 − 1.0

ρ = 0.5

α = 0.3

β = 1.0

На рис. 6 каждый муравей выбирает свой путь (муравей A0 идет по верхнему пути, а муравей A1 - по нижнему). Муравей A0 сделал 20 шагов, а муравей A1, - только 10. По уравнению 2 мы рассчитываем количество феромонов, которое должно быть "нанесено".

Примечание: Работу алгоритма можно изменить, переопределив его параметры (например, α, β или p), например, придав больший вес феромонам или расстоянию между узлами.

Далее по уравнению 3 рассчитывается количество феромона, которое будет применено. Для муравья A0 результат составляет: 0,1 + (0,5 * 0,6) = 0,4. Для муравья A1 результат составляет: 0,1 + (1,0 * 0,6) = 0,7. Далее с помощью уравнения 4 определяется, какая часть феромонов испарится и, соответственно, сколько останется. Результаты (для каждого пути соответственно) составляют:

0,4 * (1,0 - 0,6) = 0,16

0,7 * (0,5 - 0,6) = 0,28

Эти значения представляют новое количество феромонов для каждого пути (верхнего и нижнего, соответственно). Теперь переместим муравьев обратно в узел V0 воспользуемся вероятностным уравнением выбора пути 1, чтобы определить, какой путь должны выбрать муравьи. Вероятность того, что муравей выберет верхний путь (представленный количеством феромона 0,16), составляет:

Вероятность того, что муравей выберет нижний путь (представленный количеством феромона 0,28) составляет:

При сопоставлении двух вероятностей оба муравья выберут нижний путь, который является наиболее оптимальным.

11. Характерные особенности

Для алгоритма муравьиной колонии необходимо указать:

закон выделения феромона,

закон испарения феромона,

количество агентов,

места размещения.

Все эти характеристики выбираются с учетом особенности задачи на основе экспериментальных исследований (эвристики).

Алгоритм:

реализует поиск приближенных решений,

имеет полиномиальную сложность,

является одним из видов вероятностных алгоритмов (законы выделения испарения – вероятностные законы).

12. Области применения

Алгоритм муравья может применяться для решения многих задач, таких как распределение ресурсов и работы.

При решении задачи распределения ресурсов необходимо задать группу ресурсов n для ряда адресатов m и при этом минимизировать расходы на перераспределение (то есть функция должна найти наилучший способ распределения ресурсов). Обнаружено, что алгоритм муравья дает решения такого же качества, как и другие, более стандартные способы.

Намного сложнее проблема распределения работы. В этой задаче группа машин М и заданий J (состоящих из последовательности действий, осуществляемых на машинах) должны быть распределены таким образом, чтобы все задания выполнялись за минимальное время. Хотя решения, найденные с помощью алгоритма муравья, не являются оптимальными, применение алгоритма для данной проблемы показывает, что с его помощью можно решать аналогичные задачи.

Алгоритм муравья применяется для решения других задач, например, прокладки маршрутов для автомобилей, расчета цветов для графиков и маршрутизации в сетях. Более подробно способы использования алгоритма муравья описываются в книге Марко Дориго «Алгоритмы муравья для абстрактной оптимизации»

Заключение

Рассмотрены механизмы реализации эвристических алгоритмов муравьиной колонии. Они могут быть успешно применены для решения сложных комбинаторных задач оптимизации. Основная идея, лежащая в основе алгоритмов муравьиной колонии, заключается в использовании механизма положительной обратной связи, который помогает найти наилучшее приближенное решение в сложных задачах оптимизации. То есть, если в данном узле муравей должен выбрать между различными вариантами и если фактически выбранные результаты будут хорошими, то в будущем такой выбор будет более желателен, чем предыдущий. Этот подход является многообещающим из-за его общности и эффективности в обнаружении очень хороших решений сложных проблем.

Список литературы

Джонс М.Т. Программирование искусственного интеллекта в приложениях / Пер. с англ. Осипов А.И. – Москва 2004

Журнал «Мир ПК». - №3. -2002

Сборник научных трудов СевКавГТУ. Серия «Естественнонаучная». 2006. №2

Штовба С.Д. Муравьиные алгоритмы. Exponenta Pro. Математика в приложениях, 2003, №4, стр. 70-75.

МакКоннелл Дж. Основы современных алгоритмов. – М.: Техносфера, 2004. – 368 с.