-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMain.java
More file actions
42 lines (18 loc) · 48.3 KB
/
Copy pathMain.java
File metadata and controls
42 lines (18 loc) · 48.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Main {
public static void main(String[] args) {
// Array de teste
int[] teste = {6638686, 5600129, 1866357, 1415128, 7328905, 5142723, 4961614, 5882627, 6396295, 9520711, 2904417, 3416396, 1429363, 2651966, 8173294, 5373960, 323721, 871335, 7125661, 770461, 6707939, 1948662, 9307880, 8611244, 9086896, 4241305, 9082942, 1033571, 3427740, 6834765, 1797013, 4882685, 5957632, 6359938, 7663212, 2221665, 2315509, 2013464, 6967380, 4567509, 5482982, 6394934, 283207, 1436459, 7939974, 4565986, 9083027, 80303, 8856390, 1462035, 4786150, 6661589, 8054116, 2600492, 1234106, 3808879, 3787851, 1920457, 2969479, 5323212, 5544723, 1742657, 2318554, 1112281, 6261842, 3743949, 7874638, 8278474, 1750374, 2302073, 4814761, 1405486, 7653843, 9348174, 8897885, 5889688, 5876167, 1753723, 3022906, 6030707, 8023097, 5165272, 42781, 3267341, 5614534, 8086142, 7491200, 849333, 5272148, 348490, 2503358, 1429863, 9772601, 8310469, 4446907, 9521523, 1157004, 2592159, 6013086, 7367903, 1923029, 9585092, 8357948, 6575398, 9814523, 6898462, 7670266, 7337872, 8896870, 6824963, 783556, 6836330, 9582354, 6399040, 2990487, 4356143, 1710022, 3640777, 8312317, 2567431, 7493046, 4377552, 1647054, 393831, 3159884, 5847994, 8058933, 5911852, 1453748, 2920891, 7015694, 8378017, 1334416, 2215584, 4819988, 5813962, 7319903, 2217764, 2899446, 6112001, 5787299, 9533892, 3468236, 7784269, 4584075, 3081829, 9596872, 8522429, 5523811, 114275, 8623269, 6338831, 4839595, 7415088, 3118772, 2819981, 2287607, 9095092, 6372756, 1104289, 5926390, 1627542, 9895858, 9224644, 5416110, 6084231, 9742336, 1495052, 2024298, 18398, 3786967, 1132207, 1674628, 1455861, 5744970, 3374468, 252522, 4913967, 3673264, 3851063, 5911832, 5689715, 3617620, 7478611, 4249065, 979895, 5393921, 8933873, 510623, 2416790, 7492445, 5396847, 2792486, 5873446, 3416839, 507813, 9744112, 5686872, 9310711, 6126745, 2034370, 5314035, 5070266, 7532192, 6591880, 4186892, 892652, 7213192, 2756130, 1482567, 3893067, 8693188, 1470636, 1694490, 1081909, 5616517, 3036549, 5896048, 1956176, 5738909, 6664358, 1762633, 8927743, 7932673, 9235567, 9707731, 599321, 9062277, 7173113, 6886815, 5361964, 5023800, 316102, 9020067, 1420212, 4637376, 7106571, 9822423, 3799777, 9171507, 1563967, 9366844, 1320838, 1259649, 6844643, 6585286, 4321684, 3015089, 5668421, 6768596, 3483083, 5431406, 7294987, 6667650, 1636, 9635180, 7086128, 1192175, 7859137, 3394736, 7346104, 5704427, 7756213, 9214141, 8176344, 902684, 5960655, 261615, 965709, 4859096, 5049403, 876687, 8863851, 3214092, 5253196, 3310770, 7955835, 3786524, 672677, 9077827, 3451371, 5792542, 8763036, 3577356, 8752598, 8242224, 8053420, 6084883, 6475314, 7293208, 3477695, 1650740, 2479109, 9464667, 9288350, 2060313, 1851930, 5958751, 9727865, 2234130, 6300331, 1057108, 2949192, 542845, 3749559, 8663826, 5593219, 8009957, 153484, 3671278, 2990634, 5252348, 5731042, 5698385, 7876415, 5994591, 8476832, 9919241, 951551, 3863498, 9625324, 691245, 5243770, 2084573, 3624497, 9736301, 7275291, 4057209, 2700250, 5366881, 1933890, 9935347, 2007334, 6658480, 4764677, 9565159, 6172464, 2389134, 8424682, 3390777, 2373147, 6797724, 6333499, 5469470, 5809022, 7522803, 7737996, 1462373, 2829974, 2573529, 2436104, 9682301, 2894930, 474331, 3708542, 5415454, 8860357, 9868807, 9635463, 862050, 8480392, 1871519, 2790488, 1703634, 8759853, 7333032, 5271284, 1797911, 9516545, 4897112, 5388899, 6110707, 2127512, 985618, 9112856, 7069218, 3693850, 6556308, 6956265, 4831230, 7356717, 1226156, 6123913, 4090758, 7044614, 9188918, 7858004, 2864849, 2357167, 6812661, 5512311, 2146380, 2689522, 3921005, 475873, 8304729, 1825821, 9096938, 855168, 6066114, 966632, 7236325, 255081, 5644088, 296770, 3675901, 6104024, 2901139, 9501620, 3278810, 5446103, 465778, 1080435, 5684920, 8378917, 8189211, 3362451, 5407532, 999463, 3063522, 8903377, 373815, 2185447, 8908175, 8057281, 5098293, 6370951, 5026211, 4179459, 3288456, 9417765, 3538003, 3282404, 4445757, 7119707, 9036413, 7711192, 3595037, 3316034, 1678376, 119421, 1942579, 6937576, 3703876, 5588956, 484794, 8481870, 9302680, 4008655, 6015776, 459772, 275913, 6465251, 154102, 5831462, 5339570, 4098605, 8976212, 7754884, 9893942, 1528200, 9952175, 7311752, 7114306, 1410108, 8140714, 11825, 1568921, 2219693, 4565264, 3694407, 8901123, 3758770, 3769317, 5465065, 4224059, 2533032, 2282466, 3012324, 7626981, 9458923, 7222734, 1339037, 3417703, 9295917, 2824544, 7067647, 8889720, 7149042, 2513204, 2500809, 5251215, 1725825, 998419, 9680038, 9956107, 2261718, 6701769, 5528931, 9424359, 7912190, 4827642, 819017, 2092088, 5460869, 3017016, 8528350, 7172604, 5414197, 164881, 2839018, 7024998, 134678, 2240858, 366739, 1997701, 410959, 1559957, 8786604, 784622, 2772111, 2928524, 1405986, 3775894, 4444240, 8046976, 3156275, 3532552, 6804254, 2748899, 6341918, 3459817, 3308244, 9101252, 7969198, 9494920, 7468377, 6613768, 4020013, 1642821, 8731090, 4399952, 5105977, 5843749, 1614122, 2571186, 1640215, 2783673, 3025664, 2683579, 3742575, 4576850, 5215563, 3643512, 4333576, 7446861, 3457503, 8602402, 5727118, 4293741, 1272659, 4805912, 4452366, 3697748, 7896907, 5000356, 3072954, 2821074, 7093610, 9051866, 7160829, 2953005, 9018997, 1114479, 1647325, 6240678, 667289, 4167675, 3117047, 9266210, 6200760, 1155426, 8540522, 3285512, 4591695, 2069772, 2605778, 9727432, 854257, 6376125, 5920343, 9237704, 8226007, 3897714, 245457, 7398877, 1216249, 3875683, 6289397, 3689630, 4003906, 3049435, 8482051, 8153793, 2152894, 3027951, 5665026, 2667034, 2331638, 1175127, 8582836, 510494, 2004363, 4304612, 4383, 6587599, 9213058, 5911364, 5543443, 9848746, 7617721, 6845949, 7473642, 2720482, 9934858, 240355, 5650692, 6119916, 3998660, 2729897, 6301379, 7128701, 3294657, 7797910, 3805772, 9187722, 8664690, 9472889, 9838850, 7808442, 1328530, 9634765, 173657, 5220459, 6132547, 9899940, 5357804, 4747264, 4878828, 8981496, 2994619, 220453, 6165176, 5269845, 6540617, 6210233, 3098383, 1591705, 2829462, 2269678, 7029894, 6536087, 7660493, 5108668, 9577520, 1160276, 5533785, 1200739, 9831338, 9246195, 3157542, 5821584, 602533, 5410622, 7373487, 2536529, 4912387, 1759664, 4654528, 5917537, 59873, 7221071, 5825409, 873266, 946458, 2681269, 5761882, 3664367, 2468242, 7348578, 6991796, 4333398, 6383524, 4339454, 6237414, 7508715, 2911896, 5538169, 1721051, 6865631, 4532769, 4395621, 3601422, 9577822, 9137146, 6798527, 803087, 4810515, 3742575, 4263930, 9888475, 6552955, 7776679, 9348617, 584918, 5424205, 7679384, 7167767, 4720180, 1996176, 861551, 6947502, 3832324, 7938362, 4595285, 2246210, 1626999, 7199347, 6667640, 1675720, 2417355, 3545084, 9105016, 4382508, 6739171, 5146979, 5084443, 2932635, 7283404, 9423072, 9768227, 1761825, 535521, 6184442, 5621587, 3722659, 1650506, 8258161, 1764257, 6854940, 5895314, 7173922, 6746645, 6438443, 6092785, 5279704, 9744815, 2160089, 11961, 5836656, 2313457, 9988541, 2481816, 8188165, 4050291, 5968801, 7277096, 5725752, 6850196, 9065809, 360258, 2473167, 5117470, 7740174, 2566201, 6770400, 3349672, 2538058, 6132188, 4977661, 5951104, 4484539, 2325250, 4627835, 2732873, 8453138, 7092507, 324429, 1950719, 4231185, 3880546, 9403750, 5420385, 8989082, 5107371, 3159065, 5428707, 4702726, 1231746, 8650476, 2574748, 7061816, 2430865, 330225, 4643226, 6562338, 2908455, 2804805, 5113668, 1804020, 801531, 854469, 120660, 8490981, 7115198, 326705, 8928650, 3049542, 2955306, 9740913, 6171166, 5236263, 3518377, 2394576, 4515032, 1194171, 168172, 3248558, 6494394, 4547306, 7421485, 7998287, 1109164, 5454352, 6201362, 5729528, 9547736, 1287745, 6773696, 611341, 9695173, 6947282, 5900788, 4462905, 6675367, 1656195, 6840621, 904143, 1555094, 3119674, 1041150, 1245061, 9110568, 5817818, 62764, 5255194, 9698171, 8757481, 1005859, 9234935, 8422028, 8661577, 5070850, 4595986, 4569440, 9847406, 5791016, 4613094, 5553984, 8212393, 5123946, 3066017, 9724531, 6766671, 2886610, 4755595, 8030562, 2543242, 137332, 7437181, 5805350, 8190754, 842485, 4757480, 4009634, 7811968, 7387725, 4921960, 1239818, 1348483, 4924713, 5963403, 8213985, 2788546, 6661554, 204043, 619550, 2881564, 5161104, 9871875, 9012984, 2647595, 8347979, 5117605, 1322208, 7418736, 3505257, 6762182, 6081311, 213714, 2796514, 7397673, 4387618, 3899573, 4941268, 9434631, 1460281, 2890902, 3098044, 3731720, 7389772, 8199212, 8189517, 5417037, 3305422, 1868036, 8573079, 4122713, 2801438, 5231462, 8053671, 1078279, 4620833, 4075707, 3195304, 312235, 5020385, 6154488, 6302785, 3737962, 8689155, 2433699, 9688342, 9493675, 5308354, 2795340, 136617, 2528261, 5669427, 4022391, 6374377, 5880838, 6492017, 9336664, 3581490, 5005399, 199637, 5680444, 5549246, 2930522, 6112917, 3347534, 9303372, 7069677, 3953694, 7693486, 2404814, 6830503, 7562719, 1819469, 6172260, 6111849, 1273736, 3705498, 8672144, 2341254, 5971186, 6250109, 5227360, 8220302, 3124939, 3118020, 3987445, 4949352, 4207158, 4044947, 9404359, 3154153, 3477571, 5341480, 1607703, 4897455, 2803535, 8070511, 4650902, 7015611, 1023380, 41467, 9488266, 6907523, 4266829, 2073811, 9579627, 26228, 8407687, 6042883, 6146604, 999432, 5435929, 2869706, 7633153, 8904561, 3127248, 4254801, 6588371, 3405821, 681009, 4396596, 9856678, 5927339, 9297924, 3305982, 2414828, 5384041, 1856698, 2424431, 2351652, 7954617, 3519114, 9647981, 2226877, 5342900, 9209245, 2729199, 1548860, 8885276, 9726292, 3744187, 3009551, 3025773, 9928343, 5294324, 2667384, 2622953, 9666129, 7718010, 9625475, 3743254, 4107483, 6085358, 4165650, 1072315, 3331536, 3975900, 8450132, 1416143, 7883316, 6613045, 8277302, 9700078, 8157477, 2480686, 3444844, 8221656, 2614288, 4862345, 4615363, 9403661, 9609687, 5137575, 578704, 2229016, 9346019, 7172769, 1136792, 3084828, 4008139, 9568998, 3811600, 2062574, 24958, 6878701, 4345967, 3947015, 3807356, 9444069, 1605904, 1142352, 1976446, 890111, 6120908, 4675724, 6208639, 9886660, 9798881, 4157101, 9035047, 6517129, 8568744, 7611666, 4444984, 3265875, 6484141, 9562250, 1865874, 9881031, 7844310, 7578089, 9405725, 7584551, 2686943, 4786083, 9569930, 162181, 6554636, 2291856, 4490650, 7303115, 7824507, 9709219, 6737726, 8858681, 6383066, 4322936, 1269394, 4270330, 2967641, 461900, 2662240, 7671350, 599494, 5345328, 579447, 4346156, 321950, 3851473, 6463839, 5221, 9771733, 2491995, 3892204, 8720004, 837492, 9385937, 9866031, 9210896, 3603363, 3505186, 9302493, 6497444, 3917266, 9628116, 2142359, 316710, 7058348, 4812743, 605781, 5192478, 6543482, 6320091, 6542860, 1589485, 6799492, 8175582, 9850848, 5848978, 8766751, 5323457, 263244, 7165757, 4859561, 667199, 4767095, 9137121, 8201714, 3201845, 9686051, 8082827, 1375300, 6849394, 4530597, 206373, 4868710, 7759000, 5033380, 3409613, 1438363, 4383807, 1080183, 9432998, 7345624, 7845968, 9664663, 5066830, 8625865, 6597006, 3864431, 8314217, 8272806, 6099381, 4289167, 8510541, 9547134, 9677808, 4257576, 4028020, 4192362, 8197253, 750753, 712160, 4292277, 8074186, 716688, 9965810, 3045998, 9229330, 4647251, 3200451, 4732752, 1826064, 2518580, 1014625, 2780694, 9802603, 2210424, 437607, 3502212, 7810515, 1480201, 6545380, 9525972, 4981365, 5724413, 2868026, 4356332, 5812570, 7657512, 7094088, 9397846, 4679022, 4289553, 7531753, 6659930, 4825451, 148175, 2228007, 6821357, 7107832, 4684196, 109266, 688756, 1575274, 7099170, 8657239, 3552164, 8476346, 9681760, 6425695, 5919908, 9761503, 5953267, 9974447, 2154477, 2120863, 7506708, 5167389, 711348, 7461863, 7782884, 6794828, 7973992, 1431770, 8545538, 4095192, 7113520, 6892713, 5609706, 1903695, 2331671, 4773543, 2659842, 7670312, 7757557, 787852, 9305126, 1295179, 8754394, 1635842, 6292186, 4022773, 6529109, 899511, 7434820, 416950, 3921766, 322082, 4109622, 3374319, 1335734, 9840338, 3724484, 8156710, 4310942, 9033063, 370681, 4099197, 5784112, 2161352, 6068666, 5261879, 6692505, 8811195, 9410690, 5231201, 3024753, 3848071, 1491964, 6494835, 6406871, 3497607, 6360647, 8739127, 6037692, 4199553, 6336273, 7930564, 9474945, 5358763, 3686619, 858243, 485506, 7917471, 9794435, 3157235, 3647097, 952545, 2364569, 4779391, 3129979, 2181102, 4954332, 3205297, 6280513, 6974269, 5667326, 6162092, 8999461, 2686939, 3484205, 4476296, 6647857, 6725447, 6132885, 6131356, 2680822, 9234433, 7694539, 1075632, 288546, 9050145, 2753275, 3654978, 8099312, 463403, 5299685, 4096553, 3021188, 1050263, 453186, 1533323, 9892860, 3219271, 1440426, 6222488, 7280075, 2975386, 4099735, 8189587, 9168344, 8605461, 1038536, 5867677, 5079362, 8309335, 9292322, 6619983, 5176218, 7456048, 9983957, 1302770, 2670265, 3960210, 4638310, 9017419, 4366785, 3183146, 237092, 3535700, 2710798, 592755, 1491008, 5118965, 9460845, 6751413, 5131260, 9059915, 2734350, 4810878, 7366598, 7430032, 8637790, 3170403, 1500134, 106389, 5921344, 3139907, 7479982, 3307065, 8904218, 6407947, 850502, 1305555, 1717745, 1053574, 1874972, 7598770, 5917165, 7285681, 14083, 6803671, 7465463, 3197940, 9672275, 2744658, 2945407, 5400748, 3294650, 1182088, 2783589, 9727610, 2238130, 3281331, 2923840, 6602952, 7156068, 6800011, 4864328, 7393137, 864091, 9046263, 5719964, 8432726, 6879703, 9153647, 4977120, 8425851, 6109084, 5735699, 3152580, 9752223, 6419448, 8787920, 6473937, 6281791, 9643570, 5230749, 1824348, 9087976, 8304217, 290399, 9825838, 323642, 1557720, 7351841, 1197512, 3552427, 4170190, 3261698, 4330013, 2208264, 6090406, 5434029, 6486608, 2949259, 5989382, 2585713, 8874034, 363922, 9911342, 9985381, 442336, 2567679, 9275038, 7727053, 3841002, 8462687, 638959, 6491776, 5412545, 7577253, 3403962, 9871763, 4381922, 3236862, 6932073, 4007264, 9302390, 3551659, 9420011, 3506880, 8585292, 8624913, 5180038, 9470944, 2151148, 4450017, 6422929, 2203536, 3539271, 2941452, 3524909, 7170311, 1942137, 6535258, 29756, 548807, 1089298, 7663939, 8000290, 4791697, 7613459, 9816305, 9815504, 7471004, 8522456, 9909314, 6334757, 9661729, 9943075, 1374951, 2801032, 1972241, 2000841, 9245432, 8961195, 4803107, 1577490, 3613569, 2900682, 3569186, 3783104, 6572100, 2722036, 5759156, 6457392, 4083414, 6758416, 8288841, 8269470, 9846509, 3177231, 1824664, 9981475, 8887663, 6293889, 5804662, 318944, 2127394, 1831598, 7513033, 931885, 3435949, 5558468, 181037, 2614271, 5513090, 2439613, 5763761, 2335304, 4273839, 796414, 4291645, 8357913, 8125532, 6370259, 5027095, 7860498, 34995, 7009170, 4243982, 1783856, 9160960, 5119125, 1650456, 4453542, 6644517, 3804099, 4540622, 6184627, 3221616, 7309181, 3928460, 3360358, 1136935, 7837927, 3631857, 2915683, 9140729, 6634525, 1885757, 5851538, 2722270, 6311930, 2136803, 28669, 1430740, 7254464, 1689693, 9210136, 6233052, 2097899, 7613273, 5961553, 5429340, 6762297, 5835984, 7076051, 4057869, 3234076, 7429423, 1626856, 1679362, 4808451, 5258909, 908076, 2192933, 2610434, 2226430, 1076240, 1073159, 305151, 8096732, 6927652, 3517011, 374748, 8467543, 492266, 5026543, 4382609, 6450441, 5489909, 6146515, 3612659, 4888860, 744377, 1687595, 2393246, 1459977, 1354700, 1760225, 6942955, 2409371, 9501850, 62835, 9284460, 1931826, 35809, 848501, 989368, 8259364, 6407422, 8559604, 9421318, 9745555, 6394124, 1793559, 3204973, 7032260, 5763619, 1635102, 4837194, 9973208, 7339029, 3284967, 5706174, 6564195, 6922493, 6695094, 5637268, 3840119, 4292818, 6259011, 8374870, 3927430, 1382342, 2473865, 5964138, 6178955, 5521953, 7299650, 6179167, 365962, 5895989, 8000758, 8395582, 2320579, 7478905, 2863978, 548763, 9352465, 6517387, 115971, 9576965, 6576089, 6747355, 9935824, 8558508, 9949249, 8652502, 5406013, 3553377, 577252, 2334405, 1403061, 9091360, 8582867, 1656517, 2288328, 5005121, 3015224, 6097785, 5114099, 781867, 9657255, 9794034, 753802, 3724514, 4604560, 3295174, 8517997, 4410390, 5533670, 7171023, 2677522, 1432226, 7276397, 6012579, 8572409, 9666528, 4444908, 9563324, 703680, 7782106, 7517984, 689241, 8298349, 3676751, 117572, 6712316, 4311213, 2272442, 7871459, 8661508, 6656058, 7134844, 2070404, 1495329, 246583, 6995822, 1365306, 4089937, 1099863, 8491776, 8253191, 5796818, 3602032, 4652719, 3836582, 807110, 9677760, 8771978, 8077711, 8404701, 9150386, 866168, 4359750, 5736680, 789307, 3689374, 6204899, 8493006, 5689693, 5055219, 4014568, 7514554, 4771698, 6334222, 8927033, 4753737, 7571997, 7460025, 3404287, 6742567, 7579706, 6898125, 6140454, 1245366, 1112045, 9443947, 9433029, 4680829, 4647902, 2207396, 6542493, 544204, 2341742, 8411273, 2169259, 6914995, 7464055, 9577836, 5289294, 3091699, 1964804, 9994407, 668091, 9097002, 8139394, 5707868, 1423565, 5337933, 888528, 2750638, 1556313, 2802244, 5075447, 7786743, 9467697, 1460804, 349998, 1145892, 2107225, 4993576, 8943821, 4069722, 1457414, 4611570, 2087598, 3002856, 760613, 6543957, 5391078, 9640413, 7137764, 7883877, 8035686, 6823140, 5177110, 2441206, 3564794, 6524573, 7551324, 4827199, 9648143, 2125242, 1677233, 7349264, 1186667, 9118788, 9648274, 8792990, 9592033, 4013224, 2940732, 5762729, 1727104, 4305045, 867, 6635090, 5152905, 5685584, 3378374, 5142027, 337140, 4207039, 3747251, 4607562, 9470905, 302494, 1887177, 6097781, 8005133, 2363205, 2134645, 5594525, 1893493, 7202241, 3193004, 428373, 1956570, 7345673, 7683593, 9884323, 1823829, 2479950, 6327273, 4664016, 9918308, 9729461, 8341872, 1972961, 8991297, 9184518, 4645875, 5938419, 4986040, 4899540, 6317997, 91364, 7872135, 6150514, 7377440, 8517384, 3941335, 168589, 2617262, 5050000, 5235157, 1258268, 6641375, 6912608, 5343360, 4065524, 7947090, 4564287, 8461831, 1953023, 4684989, 5240247, 2546075, 5420111, 9348164, 3951221, 2434060, 6684819, 6937906, 4622600, 2025606, 8961549, 6243050, 7154238, 5812422, 672134, 2955533, 2325134, 8511897, 6934229, 5086319, 3014027, 3147573, 1052053, 1213854, 5828908, 7441892, 926285, 888992, 2699019, 3553188, 510202, 465848, 4577858, 5239535, 4544256, 8062134, 5591977, 6221226, 9792894, 4825774, 4645065, 1880061, 9037009, 1490796, 4879060, 9615188, 5565055, 3925329, 6038443, 5965476, 8544956, 7759487, 9705783, 1616497, 3621398, 4124627, 6750220, 4253278, 6800812, 4538217, 9524973, 7242364, 1925561, 1679767, 8453648, 1116628, 4272175, 9631213, 7822379, 5781985, 6700654, 4585609, 548722, 3771915, 5009216, 1161602, 9607094, 3823132, 8956919, 3560100, 9728713, 1716767, 1355087, 2538197, 7123569, 558002, 4308318, 7669121, 1596382, 4006688, 5590422, 7218620, 8947405, 3418846, 1600005, 4909249, 7146173, 1912170, 8479888, 1292682, 4298047, 8166828, 7251088, 3133457, 4438630, 7820296, 2044017, 7530128, 8811531, 1958485, 8826755, 7978367, 3710364, 4604805, 9731051, 6860688, 6510300, 3969428, 3145352, 8320026, 6455426, 9493907, 9306756, 2918176, 4094001, 643437, 1016377, 5832383, 8389623, 3207977, 873790, 1616384, 801513, 9727752, 6716911, 6279242, 4688240, 5183077, 7144397, 8912530, 995567, 2308416, 2547984, 4845825, 9316723, 8346709, 1155413, 9510033, 9181682, 9189903, 9612316, 2908273, 2150962, 9277521, 9047012, 8247744, 2846663, 6346294, 9987595, 7939604, 3855163, 6571437, 2984734, 770668, 625213, 8364313, 6854722, 2179242, 3988355, 6573729, 9950750, 2963150, 9472288, 5737967, 7001451, 2328124, 979811, 1706026, 8364616, 7715698, 5363501, 6077959, 6102682, 7380829, 9592789, 2654299, 9098183, 992226, 3562244, 8631608, 6612184, 9345816, 6215396, 55961, 9317494, 3751220, 7950643, 7674038, 3981652, 5763939, 1147400, 166463, 7114142, 7916324, 6244778, 7232256, 3656486, 7559839, 1850870, 3964907, 5880761, 3184255, 100210, 9299394, 8002876, 3554432, 5175254, 2150424, 5006337, 3138585, 1358080, 5498814, 1676002, 4772591, 4877166, 3682769, 3403512, 4948591, 7633142, 7570580, 2736140, 8883703, 6084666, 9330106, 245025, 8011578, 5903156, 5185278, 9289833, 2337571, 5004717, 6581422, 7508130, 7748439, 870178, 3300194, 1977041, 3520561, 7957424, 1615039, 2004557, 4233321, 648355, 2298084, 1610370, 5689534, 7375213, 4949045, 6038482, 2691, 483278, 458477, 8192711, 8098901, 6864248, 7735569, 5582958, 7329559, 399182, 8976069, 3822995, 5156324, 3185472, 8853917, 523347, 5971106, 9017908, 3244628, 293824, 2411881, 5587363, 9145564, 5841599, 9960278, 8795594, 4431086, 4538350, 4168030, 5321882, 3338353, 8145746, 4376810, 9708559, 2867775, 6254891, 1476536, 8822538, 6573373, 5444142, 802591, 2588770, 5173538, 2957732, 3194307, 1685403, 6949481, 8024484, 9446878, 1305040, 8889943, 7132499, 4724273, 1474704, 8676934, 9676224, 8460807, 2660392, 6544410, 247589, 2488013, 4146288, 5495337, 5166945, 3080348, 966571, 6091199, 1175748, 6189952, 9968897, 29184, 5446715, 2816435, 549068, 4401548, 5956576, 1559664, 5089710, 7182455, 6361920, 6350630, 2478993, 9131657, 4186030, 5512745, 6537855, 6283506, 1769885, 1704518, 4642188, 9304412, 6721654, 483817, 2322288, 4102053, 5577443, 8640553, 9994192, 7342711, 8770439, 4460577, 5698920, 3329396, 5338904, 5252240, 4899355, 6505249, 9837029, 344030, 6014233, 7345045, 2345817, 5125505, 3331741, 4715358, 1312771, 6858427, 901371, 5869426, 2836267, 309945, 4223472, 8023543, 2655122, 6384799, 6794730, 6501341, 9879944, 8736571, 7817683, 4321537, 3271665, 5077206, 2249814, 4193587, 9085297, 2400237, 1821633, 591671, 3241705, 6751896, 3057951, 8697942, 1386394, 7343642, 4852690, 1738169, 2773303, 7238643, 8039831, 2419419, 1633605, 3389199, 8967996, 9809913, 3748548, 4734565, 8304184, 4431605, 4177045, 8484552, 932632, 6054004, 5110762, 1179938, 4702950, 485842, 2053370, 1541084, 213466, 485704, 1000115, 8863011, 6538777, 6528546, 1764733, 1037726, 8369891, 2443087, 9835222, 588855, 9782973, 6682027, 880510, 3938746, 2738361, 8755353, 2661495, 1059398, 9633759, 1017900, 773909, 9179625, 2088536, 6700735, 61939, 227728, 8994408, 1794993, 178934, 3024956, 5120519, 524221, 7966240, 1287106, 8882701, 4213208, 9349191, 8259710, 5335799, 420664, 9387226, 132632, 4325639, 564126, 342700, 9507743, 8895719, 9532387, 5220332, 6301022, 2443098, 1481674, 8506385, 1615457, 2821124, 8322953, 4576949, 3247523, 20044, 3036265, 8540339, 587388, 4340962, 9481632, 3884743, 6821238, 9864969, 8093825, 864846, 8881751, 3622610, 6405772, 9467852, 3230273, 586887, 910917, 5579107, 121971, 7449236, 8403827, 6438913, 740064, 3965535, 9572565, 520398, 2219353, 677460, 9999125, 1435475, 8384168, 742019, 4251427, 94868, 6726947, 7844466, 90288, 5085835, 6704365, 5357975, 3025066, 7529252, 6194918, 8706873, 4149096, 2216363, 7416627, 6104237, 7255017, 6298925, 2314510, 1863631, 7216687, 8637306, 4737247, 9112722, 4357217, 7455335, 3404766, 281485, 6717432, 9745241, 3298657, 7198205, 2067657, 6687420, 3862166, 309106, 8501964, 3495252, 6800028, 8245948, 7172150, 7786548, 1224527, 5453637, 3848403, 9718089, 998375, 1954350, 4617002, 4718568, 5298337, 8923741, 4445411, 8451152, 3699220, 6690528, 2726779, 9615229, 259425, 946320, 8240396, 25035, 3471225, 4496856, 2118713, 7102132, 7210672, 8159965, 53610, 47297, 4499256, 6695090, 5007348, 4582821, 4736088, 8781605, 7416031, 6050156, 6272879, 8812212, 5562519, 7544335, 7341262, 1466571, 5544321, 585402, 7529812, 4140372, 9000782, 6523887, 2858592, 4018574, 5848117, 973422, 4173843, 278530, 4916792, 3276188, 4548177, 9185020, 7787343, 7797114, 3449446, 2843622, 4114463, 8523339, 1650976, 9056189, 5944503, 4516741, 6220386, 3166749, 270243, 4964202, 7296710, 73800, 4165107, 7862055, 1749933, 7808817, 5735242, 5491071, 947991, 2736426, 3729282, 401092, 9544706, 7150782, 7721108, 1211036, 7021159, 9922176, 3507380, 9356167, 45331, 8861519, 8409553, 4220524, 6248903, 6915186, 3389103, 7796723, 1234865, 4502620, 596553, 3344343, 8039479, 4436688, 4173731, 1124671, 2659175, 937459, 2415789, 7725269, 9618544, 7077725, 7390141, 4201521, 8951140, 6020199, 6811583, 8152063, 2745878, 7304114, 7898809, 7999476, 1133601, 3405841, 5932319, 8808857, 6457582, 2432267, 6449269, 8904440, 632628, 5818387, 2419769, 9116120, 5901932, 6999942, 1423436, 2917592, 7909346, 4076444, 3918699, 1571274, 1628352, 502653, 6915818, 3544162, 6199246, 9650896, 3691677, 2013845, 5628189, 9396639, 7194840, 2223545, 6312200, 351531, 5929543, 9493461, 260241, 4440487, 9041617, 9777966, 6994898, 5157870, 7140999, 2444643, 3860370, 1022460, 3315829, 6845467, 110435, 2827404, 4947171, 3129851, 696426, 506369, 6382777, 305955, 9581684, 79096, 4342688, 3081853, 5492785, 7469226, 8809901, 7675104, 8175055, 9866100, 8037551, 1678299, 2386289, 8440031, 3811734, 8172449, 4342857, 1626502, 2287954, 4185781, 235229, 9141016, 8611316, 5022728, 9329376, 8200086, 4029389, 6849514, 254772, 2149919, 5145915, 5449492, 1804377, 3972535, 7578241, 6994495, 5484855, 7530562, 2529454, 9498748, 72752, 3688621, 4657630, 7738544, 5470614, 8263819, 6028554, 1567249, 1291496, 2571279, 7196083, 688538, 6485598, 9259056, 2094780, 9285816, 551778, 2836066, 5173545, 9513714, 962925, 8098067, 8175456, 3732651, 9956562, 7890030, 9574124, 5884102, 5149511, 4653407, 6166078, 4443328, 5275837, 6997280, 570106, 309661, 5903492, 4379932, 9367562, 7645743, 1970810, 151543, 4346764, 112755, 3187434, 2200825, 1500804, 4247818, 5311090, 4810300, 2877460, 3108893, 1129090, 1443201, 649232, 9363258, 5978715, 3793235, 9980077, 3763283, 2860771, 1185288, 4475979, 191930, 4776380, 8800599, 7628596, 720988, 3691615, 2711027, 5874451, 8857869, 2814468, 6138709, 95252, 963085, 821369, 2490713, 2362542, 915149, 949885, 8851615, 3123298, 5661714, 7830422, 8825628, 1229406, 7377243, 7980946, 2492087, 550829, 6902236, 6224925, 1879707, 1536550, 7064652, 1909368, 6750546, 5477010, 3567680, 862036, 5308553, 649521, 9608215, 4597672, 4072825, 1846493, 8298249, 5363922, 2352364, 6052003, 2213570, 518929, 7489256, 1211162, 4575663, 6712207, 9004671, 6784766, 1633385, 4107910, 3886106, 9350207, 3883512, 1751970, 1744130, 5120063, 1357748, 1089740, 3530571, 1156045, 6036972, 4727897, 1929298, 6884827, 1051869, 1089892, 9038435, 7994267, 4178215, 5089749, 1362434, 3080588, 8784824, 5950639, 3622223, 8793724, 4914651, 5660784, 7667879, 4010853, 6171214, 8110928, 1694724, 7390677, 9515801, 1061598, 9712951, 1923063, 259616, 7486984, 4578867, 7539986, 7548170, 3007229, 9633033, 8611039, 9513294, 7347240, 9458651, 2423129, 7201314, 4567918, 6843503, 2090147, 3399034, 3787816, 6844086, 6176318, 8277862, 6326962, 3146560, 1950491, 7499999, 5179808, 729798, 5819630, 5488595, 1426065, 3881285, 6333753, 1305538, 5190171, 4791992, 7913963, 170364, 3835211, 7901564, 2518483, 6146963, 6266771, 5659766, 2203416, 8753160, 308325, 9885711, 7464218, 4761878, 5222751, 329995, 3038137, 3987601, 5329104, 4218877, 1955542, 6852524, 6890760, 7371103, 8870173, 5816543, 27070, 994540, 7366711, 4121445, 3641253, 79172, 2811580, 5795699, 5947734, 4903161, 2525657, 6540843, 6501149, 9485965, 4933936, 7462760, 2588879, 6113402, 609273, 1869832, 29749, 7133721, 2090175, 915627, 1416827, 8485016, 8572824, 7474151, 3225423, 6204071, 5713364, 9544015, 8779760, 9484643, 5902114, 7080299, 6811893, 6693570, 7269834, 8703669, 8006070, 3719622, 7100931, 6217156, 3273322, 8572903, 8193900, 8160185, 3293042, 978330, 2015128, 2775838, 6674968, 8544615, 8053677, 9465942, 9069962, 4055695, 2285990, 4669018, 3274332, 7258209, 5640882, 727904, 7987827, 207252, 4453463, 8166150, 483922, 3018218, 1045516, 8937840, 7632380, 249637, 8174158, 5013710, 5674363, 3687313, 1734217, 1068063, 4735292, 2430140, 1676522, 5311638, 6337152, 9107608, 4279752, 3507226, 2717095, 2800829, 5036128, 7204916, 8302461, 9413674, 7599099, 900281, 4465375, 3974007, 3374828, 1531556, 2839672, 5545782, 8726610, 7415163, 460149, 2492732, 9595127, 8047871, 9166021, 3846766, 8537880, 4628822, 726145, 4849183, 7020799, 966437, 7220537, 7120250, 9416090, 2854701, 9462478, 4222968, 1170029, 4813047, 5921485, 1386628, 8567840, 578151, 5233707, 2488735, 6355925, 1507603, 3841874, 6328331, 279801, 4432532, 4947585, 6672507, 1510023, 7611975, 9651041, 8223628, 4588133, 5194811, 3548094, 7242219, 2960519, 3509832, 2112651, 9280313, 57650, 5484428, 4992337, 3386082, 5828709, 6399998, 1692952, 3810075, 828794, 6190322, 5556703, 3114303, 8604686, 4696784, 5468135, 8807912, 4874883, 1224225, 3835608, 4209101, 5520065, 3679613, 1873446, 5196199, 8189226, 9031854, 9536674, 2203694, 7162841, 6577963, 1220821, 1292701, 5148615, 911455, 9783580, 2957760, 7029339, 4649450, 3404533, 7637455, 371849, 6381100, 187963, 4809741, 7068867, 4262853, 4876607, 4990496, 3833605, 190103, 8301336, 6819430, 692519, 7373042, 5706792, 9023371, 9747644, 2809171, 9076573, 3564457, 7711541, 7768438, 8886221, 2051581, 2017648, 7891851, 1998707, 7570166, 4413940, 2920706, 2111699, 1095683, 8625959, 2132330, 8987854, 4147492, 3629343, 2871765, 7259444, 1121178, 527359, 5299059, 9303080, 6946094, 9082307, 1928595, 6339488, 2002426, 7868467, 8966683, 3680658, 2563939, 9735621, 6727589, 8009287, 2537805, 2152333, 9689045, 7523777, 4793184, 6732809, 8333275, 8831069, 8135615, 8520182, 6541851, 5567645, 7848845, 6650929, 1509786, 1393837, 7149335, 3500954, 889720, 4732190, 6906123, 6564737, 8323145, 6312540, 1661315, 9794358, 7412146, 1930003, 8743397, 3142926, 1011507, 5101659, 3342235, 2562265, 7790423, 7820542, 9646922, 586665, 8410444, 8979377, 3406697, 1623249, 7668513, 5472844, 8650907, 8190427, 5634851, 4992792, 5871835, 1331337, 223340, 1031275, 3112520, 2936628, 6022535, 7699544, 5487009, 1275836, 8571466, 2537550, 6301440, 6644627, 4411742, 2095155, 8520558, 3423726, 9842062, 9575756, 4082776, 3907943, 7635396, 1846109, 418509, 2878042, 4837234, 8718238, 4643166, 1627516, 2213996, 2354383, 2822445, 5901750, 2120408, 3829730, 2468921, 6102813, 6780184, 9279505, 1798714, 5556228, 348475, 1225295, 5738149, 2679860, 857498, 8042102, 8807604, 3413540, 8448664, 7115301, 6368428, 8624825, 2021773, 9025592, 2772828, 6762115, 4849897, 9996901, 3491010, 1996305, 8021337, 3143713, 8192197, 9419739, 8368136, 57488, 1042052, 1327771, 1221735, 2045817, 7228732, 3923042, 625820, 9140740, 9650715, 6071085, 6511743, 5437179, 2998644, 7085778, 154102, 8309593, 6637348, 1629610, 3066617, 6408710, 6725700, 1723301, 3650218, 3033381, 5422536, 9656662, 5802282, 1735103, 8352856, 2713627, 6438786, 8994733, 8424983, 7129139, 3393129, 2297283, 6181691, 2306541, 1835964, 8588070, 7179455, 6486134, 3571189, 511963, 8900526, 6429349, 4656623, 7096053, 2300619, 3872455, 2742719, 1756895, 5995138, 6796352, 8199927, 4839755, 9636922, 8404955, 4339117, 3878348, 8203565, 2724378, 8138888, 3347344, 5962611, 5000334, 1495386, 7938242, 624856, 1766849, 9128363, 8712375, 5372235, 1265629, 6803486, 1058947, 7858722, 9797396, 1915959, 4890808, 6358133, 4028120, 7425612, 5837335, 5890478, 3778312, 8212984, 80574, 2843834, 6972579, 7263110, 6433471, 8568993, 5515840, 3704684, 3292533, 6545776, 2946617, 3604477, 826493, 3139452, 9190844, 4780565, 1403903, 720417, 7197476, 8926889, 4208833, 1381769, 4822604, 6743183, 1133531, 7714261, 2196118, 2593628, 9686180, 710145, 3440928, 5592198, 1960949, 7340130, 7273533, 6627305, 7782136, 9201807, 7371015, 6521623, 6239716, 3028573, 9713664, 4482006, 5414841, 4900853, 4450126, 8696685, 6892481, 880442, 4702448, 2885752, 3583958, 7607018, 9916327, 2077390, 2030005, 4220416, 1813574, 5267807, 2200809, 8907494, 3437892, 8974448, 9096939, 1745228, 3527162, 9777021, 4283651, 9434942, 9530478, 4951438, 4710618, 3056012, 4938587, 280609, 8357139, 7701532, 501465, 842555, 3304935, 3234144, 5920508, 2880147, 6446514, 7752912, 4418359, 6517294, 7005346, 8684452, 2874223, 5050427, 446001, 1531311, 807815, 1454422, 2965201, 3073788, 9540168, 8055710, 1478210, 2330597, 4365571, 2988008, 4521289, 1420212, 2412281, 4446058, 9705796, 9658005, 2286753, 5580657, 508184, 5551533, 2209073, 4281137, 3870231, 7545568, 6319463, 8053853, 6532922, 4498093, 9839767, 8095036, 8747772, 4591021, 775784, 2663383, 3646810, 9734454, 2704591, 199312, 1492654, 5627845, 273342, 399643, 3846031, 4789697, 923647, 3377772, 6860735, 5120994, 7931974, 7549161, 3476851, 1934516, 2111415, 6018383, 6626166, 642624, 7358292, 4900337, 5215236, 7905573, 9963179, 7617988, 7922120, 9499635, 8147229, 8295518, 5421083, 8085516, 2007129, 8289056, 7773664, 6651445, 8894986, 942892, 6613361, 4328014, 189041, 1202994, 5030465, 7083014, 4658915, 5533718, 4114470, 1872482, 483968, 80967, 3791406, 5587469, 7307890, 5758511, 9692586, 5534951, 1485271, 4822406, 217239, 1472266, 8671251, 9665793, 9078273, 3302910, 4255193, 3652133, 8932368, 2749264, 6069378, 6114949, 5223266, 4552893, 859346, 3400273, 8595843, 4428716, 3170608, 763046, 464432, 5973441, 7484711, 2253429, 189899, 9102004, 2381678, 5848095, 4448016, 7042148, 6458107, 6263731, 4300597, 244652, 8809506, 4184837, 3720247, 6625174, 5349612, 8182196, 2614323, 3907828, 4870998, 3846017, 3057634, 2980797, 1023033, 1022240, 4699190, 4459258, 3984182, 2438288, 4817476, 9450722, 4158835, 2269922, 7427920, 4083061, 9591832, 1112768, 8974514, 6695114, 3101897, 4524556, 5941810, 1299825, 529417, 3224748, 3417182, 8839564, 9152069, 4317997, 4438810, 5592505, 4209587, 3367230, 2604409, 891807, 8497408, 3706631, 4818839, 5687930, 8660052, 1352371, 8191264, 9815424, 6480568, 3463255, 1177709, 8666626, 8927382, 9819804, 9064904, 1189211, 2517689, 7636919, 3824895, 9694344, 6158841, 2549208, 6213444, 7101946, 2876644, 4419781, 1003691, 2506353, 7124167, 6432029, 1084002, 6878614, 6540329, 1053266, 9768232, 2350337, 9186503, 6056407, 8176217, 3947897, 5767133, 6930701, 1960404, 2967926, 332838, 649439, 7256629, 4009010, 3029347, 8580814, 1251764, 7043876, 2593822, 5782994, 8836635, 4371671, 213164, 5774454, 1212152, 6136786, 7374496, 7007474, 776093, 5886825, 213020, 1984110, 3454964, 9616952, 4364443, 950806, 3771829, 8436032, 2191332, 1854124, 8746137, 8628772, 8788460, 4763627, 639815, 2485101, 8031560, 4296766, 1182310, 2812151, 8820731, 9237692, 6666268, 9380143, 3031983, 9022468, 1162904, 2734069, 2014112, 8929640, 9038282, 1597238, 3194029, 3212285, 3757469, 7318342, 6313341, 4384155, 478376, 3941705, 4004054, 6650894, 8402944, 9160500, 7624054, 6663300, 1191167, 9590619, 8661779, 8442310, 7759399, 2457927, 9436437, 2950374, 8849252, 1192427, 5767901, 9717646, 867102, 5134428, 5416931, 7915076, 4987706, 6492900, 8368130, 8312439, 576333, 987753, 9934466, 6939603, 5760120, 8216012, 7281667, 9045543, 3929437, 4464098, 7527489, 989509, 6458037, 3865752, 848543, 6325554, 7941248, 2112899, 9119939, 6876841, 3679984, 9939737, 9191330, 4920514, 321067, 8176450, 6923845, 5787603, 4102220, 2593359, 945439, 5065589, 5242326, 1743277, 2064242, 578454, 5548541, 3648542, 8810219, 6032443, 6034297, 4449718, 584202, 5848614, 784349, 2946828, 6348533, 8162758, 7351172, 5641503, 4455927, 3990609, 5024621, 8203099, 2468640, 2433779, 5593277, 8539162, 9192798, 3655296, 2037089, 2064728, 7636183, 9259128, 1514665, 649042, 9744813, 5603346, 7025573, 7789590, 7573679, 1074755, 4207359, 7829288, 9207269, 9305012, 8671874, 4038375, 5108189, 1386472, 9569358, 5693913, 9276381, 4291561, 9894518, 3318632, 2259876, 7132181, 5382716, 1567250, 7207634, 2976064, 9459034, 7845314, 6440113, 8552424, 6950062, 1062913, 9785026, 2479377, 6262310, 573326, 3318220, 6919852, 9024739, 8145471, 2193682, 5164847, 880049, 3561476, 5181951, 8439368, 2080519, 3193885, 9810569, 1023956, 7356989, 2640339, 9679439, 7415722, 1907853, 4724359, 3914907, 5356558, 3411543, 1352580, 110196, 8674598, 6360324, 7744370, 2439685, 2748265, 3605260, 6764393, 25550, 1394532, 7711270, 6861047, 7019247, 9505930, 9750099, 9923038, 3446574, 4141991, 9862767, 8932190, 3191475, 5029855, 4737665, 9000271, 7267430, 706770, 6722578, 1334924, 6531972, 7777515, 5894661, 5922028, 9481896, 9201575, 3200933, 4295362, 3799848, 8997329, 301973, 5964850, 4394209, 7957413, 5628806, 7507813, 8657114, 6014832, 4240494, 8640365, 5649483, 8618376, 3481730, 9507413, 7200179, 5276336, 9162528, 3716273, 2584647, 2144074, 7416845, 6459868, 9077385, 1151698, 7719136, 4747932, 68779, 3464318, 2386377, 9459058, 2451558, 6859590, 4861386, 6308535, 4099107, 6275185, 1215212, 110164, 3506124, 9119707, 1173584, 7302840, 1772762, 6609806, 4516171, 6048545, 6906401, 6161992, 1559222, 6232850, 2060210, 9695812, 4784795, 7735712, 2872655, 6473313, 515143, 597485, 7616292, 917313, 299099, 4305284, 277407, 9786459, 3111039, 6347495, 4432332, 6672150, 3415600, 4587897, 787646, 9976359, 5850016, 8312896, 2592014, 2791033, 372316, 9009150, 2002342, 7852835, 2630105, 6287133, 1721504, 3512605, 2579084, 4989954, 5052199, 8854478, 7791393, 8740395, 2830419, 6602165, 6087595, 5683053, 9329306, 6685685, 9221553, 3932997, 9998849, 2413379, 2871857, 7148568, 4824903, 9716994, 3189071, 6146539, 995936, 3350441, 4148183, 7939454, 6053095, 2583776, 2258237, 1251097, 3198171, 8159945, 6920692, 8495690, 3057069, 691683, 2961502, 5962651, 1730027, 668369, 9059641, 8722815, 2895296, 1770315, 9505951, 3113986, 2369817, 477455, 9594979, 3256795, 1135839, 6749253, 9427298, 1943370, 3430, 7096635, 817938, 3881981, 3574485, 1739710, 8844618, 7935749, 2276731, 3575849, 9374936, 7793434, 9769473, 3520355, 3681485, 60888, 1340605, 9069612, 6536211, 7837734, 4129480, 3356040, 9309894, 4290027, 2445536, 7989879, 7683866, 3515724, 539449, 7630885, 1310238, 7571487, 5050990, 7320264, 8182384, 3763976, 5864035, 1395660, 9213000, 6822524, 725307, 541846, 7696065, 4325464, 9810478, 5801706, 1045556, 8863807, 3322541, 40563, 7354069, 2806200, 8464942, 2148550, 3786559, 6681070, 2197862, 6152572, 447024, 9711350, 1799223, 3853618, 2099137, 6933016, 9650542, 8751883, 7129382, 191179, 2193405, 5396411, 4559341, 7819283, 8462907, 9718993, 2595988, 8886426, 5511188, 3463070, 7099810, 3293766, 7987734, 9646566, 7765821, 8793679, 7854810, 7529526, 8586419, 9043129, 5772905, 626533, 6587917, 5036983, 8005273, 7346655, 1830932, 4086932, 3449423, 5191223, 6711220, 3862215, 320971, 7512626, 6454208, 3704841, 6044041, 5460853, 4060516, 3617784, 7493363, 6206165, 4540939, 3553695, 6315507, 72439, 5414149, 1062888, 3141767, 6277979, 340025, 5450614, 5512243, 9287286, 9998083, 4003296, 2880614, 3980981, 6320788, 870063, 4216086, 6812942, 816856, 5168581, 9842218, 3677644, 1368250, 5066502, 9930568, 9833583, 3709647, 9009429, 4690837, 7264880, 5512329, 6605302, 1851478, 540550, 125294, 716286, 8437548, 8149669, 4036706, 7284122, 294289, 3215404, 9458474, 8827728, 3009144, 1762748, 4812202, 2744406, 6174209, 977706, 9733736, 321587, 4073159, 362982, 9901856, 1650460, 7825616, 6060060, 2814858, 933872, 2154390, 3823933, 1812452, 1552438, 7092532, 3082583, 4546036, 876856, 7606619, 7203252, 77235, 9015499, 6175533, 4678873, 1753694, 7870804, 3136008, 7989099, 1609032, 3829133, 1154655, 3324139, 2271144, 5302217, 6308258, 8775936, 644248, 6186651, 6326925, 5697719, 8391798, 265368, 5062009, 9913514, 9192801, 2876874, 813224, 373104, 905915, 7160194, 835152, 9255729, 3030268, 7800590, 2539655, 412352, 5248258, 3562889, 5823381, 6622000, 7625680, 6814789, 2537004, 6019399, 2539021, 5490022, 2692938, 7788272, 8070267, 2221453, 4633912, 3741469, 3475219, 7873287, 5414784, 9580116, 6559900, 5545980, 8143076, 506193, 3992848, 9832597, 6893517, 4709811, 3512110, 8352003, 1438870, 6754174, 2730522, 1917288, 4229836, 5793428, 5902367, 619390, 1613114, 2281880, 6157483, 366016, 5026423, 5778128, 7820577, 80429, 5487787, 8781288, 2945365, 5720155, 7325345, 7519546, 7745718, 1563894, 3159087, 3897093, 890574, 5803494, 1867538, 9665229, 5943133, 6966126, 9861087, 9412197, 4692512, 1984877, 2662208, 7209236, 7953590, 954237, 7882342, 2527053, 9851947, 6492212, 3892484, 1690250, 4325488, 4699497, 8253501, 7739549, 7270855, 2743566, 4790177, 815626, 4803802, 9155103, 3486349, 1238548, 3920617, 6303883, 9785651, 5852450, 8622735, 5473341, 7902038, 6716277, 3812862, 2115190, 6780882, 6964327, 4636494, 638701, 8673111, 7377797, 9121514, 1877365, 9673215, 581985, 8258216, 8149070, 4140386, 7512773, 5493354, 8860607, 1512444, 9178607, 1549179, 9820675, 3868139, 4307252, 6962928, 3159081, 6014810, 515767, 4850251, 6067312, 3920562, 6264288, 2468145, 4836782, 387701, 4190559, 9488382, 2846429, 9226132, 1907519, 1988077, 898193, 1233405, 3442016, 8708788, 2756959, 1667607, 9238710, 2601292, 2185531, 7433139, 2824469, 402324, 5739663, 8525710, 5249603, 1244966, 1156674, 3097662, 1065132, 3852178, 3316825, 3877193, 6022342, 3016095, 9578491, 208523, 2438864, 6380712, 5771337, 2480538, 3634422, 6393857, 3551010, 7982445, 2831839, 2278810, 5125683, 2653921, 627832, 5479045, 7632429, 8348598, 2122809, 3013010, 2069026, 1079684, 8540715, 3302503, 5978965, 3823202, 5004337, 1686653, 4215527, 3050866, 6592611, 6350017, 6351913, 2313430, 2136553, 3001181, 7348659, 2408247, 7980785, 5325316, 7367297, 7275985, 4081177, 3342841, 8875769, 9117831, 8271977, 9680745, 74230, 3169665, 5198336, 3843323, 3766659, 1254003, 8269847, 4566331, 7081804, 2598587, 5854395, 2003516, 9005331, 5310203, 4104519, 3309311, 4643394, 7061347, 9774240, 125178, 5858670, 6175319, 569084, 5708485, 9587225, 5492513, 5074655, 9192167, 1300557, 5788025, 9229131, 6230007, 7062993, 8436045, 1411505, 9089253, 7506325, 9514814, 4437234, 7138986, 9728718, 8505461, 6563125, 4680996, 9190941, 5265596, 6689666, 3175088, 563811, 8630038, 243041, 9648933, 3753979, 3572479, 6459517, 2757815, 2789906, 1790188, 5391343, 4871417, 4729324, 4393354, 121578, 28829, 5935271, 9368441, 2614433, 1872124, 9645564, 9806239, 8913754, 1312503, 1568182, 8908149, 5770609, 8838312, 9504540, 4307387, 6554252, 546956, 4001228, 4779773, 7191990, 8387677, 5958282, 2936710, 4069145, 7511190, 5378539, 8033179, 946721, 2300624, 4154830, 2384420, 7746320, 4440596, 8487724, 8540648, 2198880, 3797491, 4370757, 2917689, 7759508, 2476865, 646770, 5283903, 1705970, 351247, 8653772, 8623419, 3591019, 6512164, 407311, 1151531, 8061040, 8418332, 4644410, 9674293, 6882927, 3969934, 9464631, 6721727, 9886533, 3935490, 7274121, 8262829, 3869306, 5004299, 417865, 1165167, 1698925, 5787040, 954541, 5794210, 2465086, 5976713, 3549133, 8837518, 603922, 2531356, 553980, 6300018, 9050077, 6802138, 3169692, 1170125, 1696277, 6249396, 1222784, 9837192, 5718801, 1618976, 3088012, 9287355, 4901398, 2264931, 2296887, 1158589, 9863188, 1152648, 6090363, 9913006, 7502809, 7366326, 3142006, 5791829, 9644491, 3975325, 9700456, 1927891, 8662997, 3211780, 1495486, 8309432, 1982069, 8120235, 7739841, 3510994, 1511632, 5055487, 7444782, 1208485, 6468945, 2869458, 9302181, 6883190, 9821592, 1805983, 7277855, 414733, 8211654, 7580270, 7410126, 8282580, 3005451, 5504302, 9327613, 2737042, 400815, 8207875, 2427426, 7554702, 4503062, 9852662, 4237127, 2448930, 1440446, 9332011, 1571138, 2074057, 8738411, 5794434, 11947, 9924600, 5088295, 6299487, 1662795, 7711448, 8870825, 7475574, 594248, 8284216, 6561983, 8992995, 448178, 5771822, 4640786, 1558594, 4103215, 1886709, 6041866, 756516, 3914771, 9180826, 3248979, 5645938, 8356528, 2535570, 4200962, 3941408, 7751296, 4932846, 6133720, 8600606, 5637505, 3450046, 7543537, 5794910, 9720274, 1689096, 7681024, 3397012, 9905655, 9906606, 6257151, 5545664, 6887899, 1410781, 157660, 1080660, 1994384, 4015998, 8450062, 792175, 374603, 8656227, 5359642, 7119873, 6066987, 553050, 4471389, 4598484, 1382922, 540704, 7745655, 240096, 2763134, 8487352, 9115956, 2730013, 8781158, 1293115, 9672338, 2506377, 506061, 1866432, 9412637, 340310, 2404141, 1901248, 9829400, 5688348, 5195804, 1373070, 2088217, 8225958, 2714582, 8929652, 4553950, 596842, 4779371, 7411460, 8782255, 1940311, 9060573, 8834668, 3355922, 9760789, 3034164, 1645079, 9257557, 1763514, 6301995, 6778713, 2226291, 6042661, 2163152, 7886976, 8020924, 7570065, 2043454, 8308283, 5109660, 8843011, 4931535, 506514, 9731513, 8993561, 3181897, 6890049, 4590537, 3321469, 8247109, 3426071, 8782679, 8870427, 7911394, 7882183, 6166277, 1746255, 8353977, 7511713, 6436110, 5570352, 1966372, 8747645, 310075, 4528097, 6037785, 8311545, 3722276, 4941252, 3236152, 2317459, 5180192, 4224345, 164559, 1949261, 7588688, 481135, 1919193, 1345713, 7919453, 6914497, 6536213, 9183813, 635946, 1081444, 1123151, 2190598, 4701638, 1400651, 5066098, 6475569, 5716895, 6139311, 1652782, 7235598, 5662743, 5269830, 7129779, 2563683, 1819035, 171209, 1134333, 3416726, 6912085, 9855186, 8624119, 7945893, 7480311, 672700, 4095304, 996270, 7236707, 6590563, 3357058, 9765984, 5385645, 6084005, 5056959, 9048661, 1410824, 9322521, 6482336, 5191704, 1411284, 4983931, 4179772, 6433857, 4678528, 5069007, 5051330, 1478499, 5440993, 1523937, 5233523, 5543236, 1608174, 4392294, 8558007, 8101400, 5290709, 8345468, 9478609, 1000398, 8140099, 7740116, 4408740, 186284, 9680616, 8752054, 3501383, 6268647, 4203747, 6437879, 2946326, 8423609, 7328010, 1014864, 9023321, 7004268, 8849686, 5195032, 5288188, 2550893, 5471088, 5196485, 1576373, 9981710, 405022, 9370266, 9881838, 593540, 7146033, 6881138, 1868747, 2592576, 4078888, 1427236, 7848458, 2891860, 8645279, 8700718, 7488074, 5611164, 2870092, 1895186, 5374493, 5344163, 618552, 377288, 6301669, 60836, 9057085, 9283894, 3958639, 5431250, 4652872, 5885503, 8221280, 5926026, 1074622, 7028396, 1319729, 7318565, 6733560, 953854, 3183584, 9758418, 3577375, 9391588, 1821276, 6382620, 4736646, 9855898, 3227600, 6651534, 3734176, 6764158, 5863637, 7037662, 5500342, 7534325, 8372753, 6322418, 5634956, 9055807, 9488338, 6639437, 1940455, 5722744, 5523438, 496352, 6798327, 1718759, 7515329, 7068199, 1530417, 6141319, 2221995, 384713, 5481094, 8142169, 5854644, 9700661, 5293808, 5309250, 2260821, 9027679, 153533, 4102025, 9343754, 4428036, 6565777, 8794397, 9741260, 2019189, 5225803, 4195827, 884089, 6361209, 7021650, 9922890, 2149991, 9797403, 6352464, 5322487, 4867242, 7121067, 6321735, 1906470, 7067903, 6079633, 5007646, 1893596, 5776409, 981890, 6224503, 5375744, 1957983, 899137, 8388915, 4089312, 1254539, 8284314, 7298834, 4476751, 7693826, 5196560, 6265831, 9061192, 1863063, 1634592, 8803879, 9945532, 1387638, 6695282, 9968899, 7320978, 8415184, 1330801, 8435460, 5032635, 6733385, 3203646, 3044874, 4406015, 761587, 4994831, 9549828, 65128, 6036851, 4573854, 3896499, 3998842, 3650321, 919479, 3748401, 1868609, 583135, 4691871, 3847486, 3330272, 1593776, 9718296, 886860, 788660, 4938536, 7814412, 2579175, 6235691, 7558595, 5628147, 8065040, 8111344, 8074692, 6435334, 3031297, 1932562, 3433249, 1018636, 522625, 2551636, 9071766, 6332859, 6615946, 1472142, 4534267, 2880209, 998304, 2691607, 8721641, 4917092, 8366153, 4459607, 4555853, 5284155, 1709634, 1656003, 5614040, 2746038, 1745238, 5698248, 9889031, 615904, 6090487, 7183260, 9793611, 8694998, 3287489, 115647, 3529607, 7232037, 9042984, 3764418, 1590742, 2916286, 5713420, 6295348, 1251258, 6554736, 7483923, 3187289, 2532339, 9885937, 8359572, 3773708, 6176659, 4563041, 2218383, 7552242, 1529541, 889326, 8360722, 3139141, 7397686, 9372663, 3696073, 3703815, 6424780, 6063457, 2915698, 4464220, 6982661, 4689220, 9117234, 4381514, 9881398, 1641900, 7222785, 4529666, 5092277, 5238530, 5775308, 650245, 547578, 5187287, 7098583, 9410869, 6469977, 6120717, 8411588, 3167595, 7355462, 9999450, 1435991, 8102443, 8469868, 7841111, 9266351, 7293746, 6311071, 5386972, 6253475, 5365838, 3016365, 2219028, 8506337, 4058115, 6237766, 3731074, 4621887, 2199378, 8430388, 7070934, 2596801, 2035337, 561379, 5339587, 2505803, 6515073, 2867957, 8045048, 9737789, 8258653, 6581724, 545838, 1689888, 3851656, 5056746, 431609, 8023736, 7775144, 3091068, 7036712, 9107105, 7874448, 1884989, 1549170, 4126573, 5044511, 1789349, 9382890, 8700221, 7879782, 5931080, 6639148, 9796416, 6924390, 1709040, 8815263, 5891491, 110714, 6707263, 4712933, 3440808, 397968, 9121161, 574538, 5720239, 2061068, 4231441, 2183179, 7525035, 8886782, 9016666, 8183944, 4605113, 4731852, 2174188, 3822445, 8908193, 2977796, 7079372, 9716884, 3177719, 3944015, 8951762, 9864010, 4636775, 910654, 3000898, 6846483, 8079068, 4481482, 7496548, 5367385, 8419104, 6723143, 9014688, 3893763, 2447846, 240248, 2688858, 8499714, 3576639, 7232560, 5096982, 2350721, 860951, 9440757, 3744280, 7588091, 9421493, 2099222, 3109805, 5745681, 5104645, 7938326, 9474395, 8696678, 8575380, 5686718, 7030476, 2378339, 5715828, 9447576, 7053033, 7961243, 8913984, 3187129, 4296070, 7445981, 1305504, 114199, 6485983, 4544865, 7841407, 9480131, 7405083, 7581110, 6232937, 1980831, 2289449, 8857248, 5135157, 9819413, 4238922, 5497067, 438586, 8426393, 8726903, 6544494, 2309792, 2321483, 588754, 2270956, 6614629, 2579962, 4194968, 2507286, 7970948, 2173604, 547798, 7985594, 7742270, 1424878, 1966299, 88466, 8045362, 8141337, 8710122, 3807898, 9784555, 9681310, 8482674, 4939888, 7017582, 8468122, 3312026, 1179188, 6326025, 3709675, 4052435, 3187443, 9499729, 6078382, 4814244, 3895350, 5614801, 4098045, 2454105, 5887073, 3932475, 5275679, 7120238, 6047627, 1607408, 1400708, 3183448, 1937364, 9858643, 4005317, 6024814, 5613022, 442013, 155633, 191069, 2769177, 7963303, 6848514, 8515114, 1406329, 2906234, 9331442, 4556473, 5718127, 8607910, 707153, 5337868, 5586974, 8029595, 1030571, 1833086, 4868776, 267468, 9558585, 5822191, 5052356, 772796, 895706, 6354071, 6993585, 3683023, 6575919, 3101747, 851379, 5594371, 5779586, 6048753, 2455354, 9366063, 9240844, 4843362, 6032164, 5247890, 5018726, 842235, 2572428, 7331014, 3899812, 7821112, 6474680, 9611491, 3714356, 4726899, 9068378, 4302326, 3915689, 5771994, 1648915, 8441781, 9982373, 7888011, 2458461, 6501628, 9597288, 9631835, 1223405, 8805134, 7479778, 8568461, 2011572, 4555940, 3789242, 6283484, 4146501, 5851640, 9253675, 3457527, 2710452, 8458005, 9505978, 274136, 1488877, 7231587, 2151819};
// Ordena o array usando OrdenaLinear
OrdenaLinear.ordenaLinear(teste, teste.length);
// Print Vetor Ordenado
System.out.println("\n Vetor Ordenado:");
imprimeArray(teste);
}
// Método para ajudar no print
private static void imprimeArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}