php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Request #70442 Slow performance for array_intersect
Submitted: 2015-09-07 00:33 UTC Modified: 2015-09-12 12:51 UTC
Votes:2
Avg. Score:3.0 ± 0.0
Reproduced:1 of 1 (100.0%)
Same Version:1 (100.0%)
Same OS:1 (100.0%)
From: me at ninosego dot de Assigned:
Status: Open Package: Performance problem
PHP Version: 5.6.13 OS: Debian Jessie
Private report: No CVE-ID: None
View Add Comment Developer Edit
Welcome! If you don't have a Git account, you can't do anything here.
You can add a comment by following this link or if you reported this bug, you can edit this bug over here.
(description)
Block user comment
Status: Assign to:
Package:
Bug Type:
Summary:
From: me at ninosego dot de
New email:
PHP Version: OS:

 

 [2015-09-07 00:33 UTC] me at ninosego dot de
Description:
------------
The performance for the function array_intersect() is very slow. You could increase the performance by changing the method just for one-dimensional arrays (a simple check on top of the function).

In the "test script" section you can find a short benchmark script. Here are the results for php v5.6:
---------------------------
array_intersect -> sizeof
---------------------------
bool(true)
array(2) {
  [0]=>
  string(2) "47"
  [1]=>
  string(3) "103"
}
0.0047159194946289

---------------------------
array_fill_keys -> array_intersect_key -> sizeof
---------------------------
bool(true)
array(2) {
  [47]=>
  bool(true)
  [103]=>
  bool(true)
}
0.00086712837219238

---------------------------
array_fill_keys -> array_intersect_key -> array_keys -> sizeof
---------------------------
bool(true)
array(2) {
  [0]=>
  int(47)
  [1]=>
  int(103)
}
0.00063204765319824

---------------------------
foreach -> in_array -> add -> sizeof
---------------------------
bool(true)
array(2) {
  [0]=>
  string(2) "47"
  [1]=>
  string(3) "103"
}
0.0014259815216064

---------------------------
array_fill_keys -> foreach -> isset -> array add -> sizeof
---------------------------
bool(true)
array(2) {
  [0]=>
  string(2) "47"
  [1]=>
  string(3) "103"
}
0.00040912628173828

As you can see "array_fill_keys -> foreach -> isset -> array add -> sizeof" is much faster than "array_intersect -> sizeof" and also do the same job for one-dimensional arrays. I'm sure in C you could more improve that function :)

Test script:
---------------
$array1 = explode( ',', '47,103' );
$array2 = explode( ',', '93299,93280,93300,93282,93302,93284,93304,93286,93306,93288,93308,93290,93310,93292,93312,93293,93295,93297,93258,93260,93242,93262,93244,93264,93246,93266,93248,93268,93249,93270,93251,93272,93253,93274,93255,93276,93256,93278,93238,93218,93240,93220,93222,93202,93224,93204,93226,93206,93228,93208,93230,93210,93232,93212,93234,93214,93236,93216,93174,93196,93176,93198,93178,93200,93180,93182,93162,93184,93164,93186,93166,93188,93168,93190,93170,93192,93172,93194,93132,93154,93134,93156,93136,93158,93138,93160,93140,93142,93123,93144,93124,93146,93126,93148,93128,93150,93130,93152,93111,93091,93113,93093,93115,93095,93117,93097,93119,93099,93121,93101,93103,93083,93105,93085,93107,93087,93109,93089,93047,93069,93049,93071,93051,93073,93053,93075,93055,93077,93057,93079,93059,93081,93061,93063,93043,93065,93045,93067,93016,93028,93017,93030,93018,93032,93019,93034,93020,93036,93021,93038,93022,93040,93023,93042,93024,93025,93014,93026,92995,92976,92996,92978,92998,92980,93000,92982,93002,92984,93004,92986,93006,92988,93008,92990,93010,92992,93012,92993,92954,92956,92936,92958,92938,92960,92940,92962,92942,92964,92944,92966,92946,92968,92948,92970,92950,92972,92952,92974,92932,92912,92934,92914,92916,92896,92918,92898,92920,92900,92922,92902,92924,92904,92926,92906,92928,92908,92930,92910,92868,92890,92870,92892,92872,92894,92874,92876,92856,92878,92858,92880,92860,92882,92862,92884,92864,92886,92866,92888,92826,92848,92828,92850,92830,92852,92832,92854,92834,92836,92817,92838,92819,92840,92821,92842,92822,92844,92824,92846,92805,92785,92807,92787,92809,92789,92811,92791,92813,92793,92815,92795,92797,92777,92799,92779,92801,92781,92803,92783,92741,92763,92743,92765,92745,92767,92747,92769,92749,92771,92751,92773,92753,92775,92755,92757,92737,92759,92739,92761,92699,92721,92701,92723,92703,92725,92705,92727,92707,92729,92709,92731,92711,92733,92713,92735,92715,92717,92697,92719,92677,92658,92679,92660,92681,92662,92683,92663,92685,92665,92687,92667,92689,92669,92691,92671,92693,92673,92695,92675,92636,92638,92618,92640,92620,92642,92622,92644,92624,92646,92626,92648,92628,92650,92630,92652,92632,92654,92634,92656,92614,92594,92616,92596,92598,92578,92600,92580,92602,92582,92604,92584,92606,92586,92608,92588,92610,92590,92612,92592,92551,92572,92553,92574,92555,92576,92557,92559,92539,92561,92541,92563,92543,92565,92545,92567,92547,92569,92549,92570,92509,92531,92511,92533,92513,92535,92515,92537,92517,92519,92499,92521,92501,92523,92503,92525,92505,92527,92507,92529,92487,92467,92489,92469,92491,92471,92493,92473,92495,92475,92497,92477,92479,92459,92481,92461,92483,92463,92485,92465,92424,92445,92426,92447,92428,92449,92430,92451,92432,92453,92434,92455,92436,92457,92438,92440,92420,92442,92422,92443,92382,92404,92384,92406,92386,92408,92388,92410,92390,92412,92392,92414,92394,92416,92396,92418,92398,92400,92380,92402,92360,92340,92362,92342,92364,92344,92366,92346,92368,92348,92370,92350,92372,92352,92374,92354,92376,92356,92378,92358,92318,92320,92300,92322,92302,92324,92304,92326,92306,92328,92308,92330,92310,92332,92312,92334,92314,92336,92316,92338,92296,92276,92298,92278,92280,92260,92282,92262,92284,92264,92286,92266,92288,92268,92290,92270,92292,92272,92294,92274,92232,92254,92234,92256,92236,92258,92238,92240,92220,92242,92222,92244,92224,92246,92226,92248,92228,92250,92230,92252,92210,92190,92212,92192,92214,92194,92216,92196,92218,92198,92200,92180,92202,92182,92204,92184,92206,92186,92208,92188,92146,92168,92148,92170,92150,92172,92152,92174,92154,92176,92156,92178,92158,92160,92140,92162,92142,92164,92144,92166,92104,92126,92106,92128,92108,92130,92110,92132,92112,92134,92114,92136,92116,92138,92118,92120,92100,92122,92102,92124,92082,92062,92084,92064,92086,92066,92088,92068,92090,92070,92092,92072,92094,92074,92096,92076,92098,92078,92080,92060,92040,92020,92042,92022,92044,92024,92046,92026,92048,92028,92050,92030,92052,92032,92054,92034,92056,92036,92058,92038,92018,91998,92000,91980,92002,91982,92004,91984,92006,91986,92008,91988,92010,91990,92012,91992,92014,91994,92016,91996,91954,91976,91956,91978,91958,91960,91940,91962,91942,91964,91944,91966,91946,91968,91948,91970,91950,91972,91952,91974,91912,91934,91914,91936,91916,91938,91918,91920,91900,91922,91902,91924,91904,91926,91906,91928,91908,91930,91910,91932,91890,91870,91892,91872,91894,91874,91896,91876,91898,91878,91880,91860,91882,91862,91884,91864,91886,91866,91888,91868,91826,91848,91828,91850,91830,91852,91832,91854,91834,91856,91836,91858,91838,91840,91820,91842,91822,91844,91824,91846,91786,91807,91788,91809,91790,91811,91792,91813,91794,91815,91796,91816,91798,91818,91800,91802,91782,91804,91784,91805,91764,91744,91766,91746,91768,91748,91770,91750,91772,91752,91774,91754,91776,91756,91778,91758,91780,91760,91762,91742,91722,91702,91724,91704,91726,91706,91728,91708,91730,91710,91732,91712,91734,91714,91736,91716,91738,91718,91740,91720,91700,91680,91682,91662,91684,91664,91686,91666,91688,91668,91690,91670,91692,91672,91694,91674,91696,91676,91698,91678,91636,91658,91638,91660,91640,91642,91623,91644,91625,91646,91627,91648,91629,91650,91631,91652,91632,91654,91634,91656,91595,91617,91597,91619,91599,91621,91601,91603,91583,91605,91585,91607,91587,91609,91589,91611,91591,91613,91593,91615,91573,91553,91575,91555,91577,91557,91579,91559,91581,91561,91563,91543,91565,91545,91567,91547,91569,91549,91571,91551,91509,91531,91511,91533,91513,91535,91515,91537,91517,91539,91519,91541,91521,91523,91503,91525,91505,91527,91507,91529,91467,91489,91469,91491,91471,91493,91473,91495,91475,91497,91477,91499,91479,91501,91481,91483,91463,91485,91465,91487,91445,91425,91447,91427,91449,91429,91451,91431,91453,91433,91455,91435,91457,91437,91459,91439,91461,91441,91443,91423,91403,91383,91405,91385,91407,91387,91409,91389,91411,91391,91413,91393,91415,91395,91417,91397,91419,91399,91421,91401,91381,91361,91363,91343,91365,91345,91367,91347,91369,91349,91371,91351,91373,91353,91375,91355,91377,91357,91379,91359,91318,91339,91320,91341,91322,91324,91304,91326,91306,91328,91308,91330,91310,91332,91312,91334,91314,91336,91316,91337,91276,91298,91278,91300,91280,91302,91282,91284,91264,91286,91266,91288,91268,91290,91270,91292,91272,91294,91274,91296,91254,91234,91256,91236,91258,91238,91260,91240,91262,91242,91244,91224,91246,91226,91248,91228,91250,91230,91252,91232,91191,91212,91193,91214,91195,91216,91197,91218,91199,91220,91200,91222,91202,91204,91185,91206,91187,91208,91189,91210,91149,91171,91151,91173,91153,91175,91155,91177,91157,91179,91159,91181,91161,91183,91163,91165,91145,91167,91147,91169,91127,91107,91129,91109,91131,91111,91133,91113,91135,91115,91137,91117,91139,91119,91141,91121,91143,91123,91125,91105,91085,91065,91087,91067,91089,91069,91091,91071,91093,91073,91095,91075,91097,91077,91099,91079,91101,91081,91103,91083,91063,91043,91045,91025,91047,91027,91049,91029,91051,91031,91053,91033,91055,91035,91057,91037,91059,91039,91061,91041,90999,91021,91001,91023,91003,91005,90985,91007,90987,91009,90989,91011,90991,91013,90993,91015,90995,91017,90997,91019,90958,90980,90960,90982,90962,90983,90964,90966,90946,90968,90948,90970,90950,90972,90952,90974,90954,90976,90956,90978,90936,90916,90938,90918,90940,90920,90942,90922,90944,90924,90926,90906,90928,90908,90930,90910,90932,90912,90934,90914,90872,90894,90874,90896,90876,90898,90878,90900,90880,90902,90882,90904,90884,90886,90866,90888,90868,90890,90870,90892,90831,90852,90832,90854,90834,90856,90836,90858,90838,90860,90840,90862,90842,90864,90844,90846,90827,90848,90829,90850,90809,90789,90811,90791,90813,90793,90815,90795,90817,90797,90819,90799,90821,90801,90823,90803,90825,90805,90807,90787,90767,90747,90769,90749,90771,90751,90773,90753,90775,90755,90777,90757,90779,90759,90781,90761,90783,90763,90785,90765,90745,90725,90727,90707,90729,90709,90731,90711,90733,90713,90735,90715,90737,90717,90739,90719,90741,90721,90743,90723,90681,90703,90683,90705,90685,90687,90668,90689,90670,90691,90672,90693,90674,90695,90676,90697,90678,90699,90679,90701,90640,90662,90642,90664,90644,90666,90646,90648,90628,90650,90630,90652,90632,90654,90634,90656,90636,90658,90638,90660,90618,90598,90620,90600,90622,90602,90624,90604,90626,90606,90608,90589,90610,90591,90612,90593,90614,90595,90616,90597,90555,90577,90557,90579,90559,90581,90561,90583,90563,90585,90565,90587,90567,90569,90549,90571,90551,90573,90553,90575,90514,90535,90516,90537,90517,90539,90519,90541,90521,90543,90523,90545,90525,90547,90527,90529,90510,90531,90512,90533,90496,90476,90498,90478,90500,90480,90501,90482,90503,90484,90504,90486,90506,90488,90507,90490,90509,90492,90494,90474,90454,90434,90456,90436,90458,90438,90460,90440,90462,90442,90464,90444,90466,90446,90468,90448,90470,90450,90472,90452,90432,90412,90414,90394,90416,90396,90418,90398,90420,90400,90422,90402,90424,90404,90426,90406,90428,90408,90430,90410,90368,90390,90370,90392,90372,90374,90354,90376,90356,90378,90358,90380,90360,90382,90362,90384,90364,90386,90366,90388,90326,90348,90328,90350,90330,90352,90332,90334,90314,90336,90316,90338,90318,90340,90320,90342,90322,90344,90324,90346,90304,90284,90306,90286,90308,90288,90310,90290,90312,90292,90294,90274,90296,90276,90298,90278,90300,90280,90302,90282,90240,90262,90242,90264,90244,90266,90246,90268,90248,90270,90250,90272,90252,90254,90234,90256,90236,90258,90238,90260,90198,90220,90200,90222,90202,90224,90204,90226,90206,90228,90208,90230,90210,90232,90212,90214,90195,90216,90197,90218,90180,90160,90182,90162,90184,90164,90186,90166,90188,90168,90189,90170,90190,90172,90192,90174,90194,90176,90178,90158,90138,90118,90140,90120,90142,90122,90144,90124,90146,90126,90148,90128,90150,90130,90152,90132,90154,90134,90156,90136,90116,90096,90098,90078,90100,90080,90102,90082,90104,90084,90106,90086,90108,90088,90110,90090,90112,90092,90114,90094,90052,90074,90054,90076,90056,90058,90038,90060,90040,90062,90042,90064,90044,90066,90046,90068,90048,90070,90050,90072,90010,90032,90012,90034,90014,90036,90016,90018,89998,90020,90000,90022,90002,90024,90004,90026,90006,90028,90008,90030,89988,89969,89990,89971,89992,89973,89994,89975,89996,89977,89978,89959,89980,89961,89982,89963,89984,89965,89986,89967,89926,89948,89928,89950,89930,89952,89932,89953,89934,89955,89936,89957,89938,89940,89920,89942,89922,89944,89924,89946,89884,89906,89886,89908,89888,89910,89890,89912,89892,89914,89894,89916,89896,89918,89898,89900,89880,89902,89882,89904,89862,89843,89864,89845,89866,89847,89868,89849,89870,89851,89872,89853,89874,89854,89876,89856,89878,89858,89860,89841,89821,89801,89823,89803,89825,89805,89827,89807,89829,89809,89831,89811,89833,89813,89835,89815,89837,89817,89839,89819,89799,89779,89781,89761,89783,89763,89785,89765,89787,89767,89789,89769,89791,89771,89793,89773,89795,89775,89797,89777,89735,89757,89737,89759,89739,89741,89721,89743,89723,89745,89725,89747,89727,89749,89729,89751,89731,89753,89733,89755,89693,89715,89695,89717,89697,89719,89699,89701,89681,89703,89683,89705,89685,89707,89687,89709,89689,89711,89691,89713,89671,89651,89673,89653,89675,89655,89677,89657,89679,89659,89661,89641,89663,89643,89665,89645,89667,89647,89669,89649,89607,89629,89609,89631,89611,89633,89613,89635,89615,89637,89617,89639,89619,89621,89601,89623,89603,89625,89605,89627,89566,89587,89567,89589,89569,89591,89571,89593,89573,89595,89575,89597,89577,89599,89579,89581,89562,89583,89564,89585,89544,89524,89546,89526,89548,89528,89550,89530,89552,89532,89554,89534,89556,89536,89558,89538,89560,89540,89542,89522,89504,89485,89506,89487,89508,89488,89510,89490,89512,89492,89514,89494,89516,89496,89517,89498,89519,89500,89521,89502,89483,89462,89465,89467,89446,89469,89448,89471,89450,89473,89452,89475,89454,89477,89456,89479,89458,89481,89460,89419,89440,89421,89442,89422,89444,89424,89426,89407,89428,89409,89430,89411,89432,89413,89434,89415,89436,89417,89438,89377,89399,89379,89401,89381,89403,89383,89405,89385,89387,89367,89389,89369,89391,89371,89393,89373,89395,89375,89397,89355,89335,89357,89337,89359,89339,89361,89341,89363,89343,89365,89345,89347,89327,89349,89329,89351,89331,89353,89333,89291,89313,89293,89315,89295,89317,89297,89319,89299,89321,89301,89323,89303,89325,89305,89307,89287,89309,89289,89311,89249,89271,89251,89273,89253,89275,89255,89277,89257,89279,89259,89281,89261,89283,89263,89285,89265,89267,89247,89269,89227,89207,89229,89209,89231,89211,89233,89213,89235,89215,89237,89217,89239,89219,89241,89221,89243,89223,89245,89225,89185,89187,89167,89189,89169,89191,89171,89193,89173,89195,89175,89197,89177,89199,89179,89201,89181,89203,89183,89205,89163,89120,89165,89144,89124,89147,89126,89129,89150,89153,89111,89132,89155,89135,89114,89158,89117,89138,89161,89141,89078,89142,89123,89102,89060,89084,89148,89064,89108,89130,89088,89112,89071,89156,89136,89095,89118,89098,89057,89101,89059,89080,89083,89104,89063,89107,89086,89066,89069,89090,89092,89072,89052,89074,89096,89055,89077,89035,89015,88994,89038,88997,89018,89021,89042,89000,89045,89003,89024,89026,89048,89006,89029,89009,89032,88991,89012,88971,88992,89036,88952,89016,88976,89040,88998,88958,89023,88982,89046,88940,89004,88964,89051,89030,88988,88946,89010,88951,88972,88931,88975,88954,88934,88957,88978,88937,88981,88939,88960,88963,88984,88942,88987,88945,88966,88969,88948,88906,88928,88886,88908,88888,88911,88891,88914,88894,88917,88874,88897,88877,88920,88900,88922,88880,88903,88925,88882,88865,88822,88845,88867,88824,88827,88848,88870,88851,88830,88833,88854,88856,88836,88859,88816,88838,88819,88841,88862,88842,88846,88868,88932,88912,88828,88892,88873,88852,88810,88918,88834,88898,88815,88879,88860,88905,88926,88821,88885,88779,88801,88758,88761,88782,88804,88785,88807,88764,88787,88809,88767,88790,88812,88770,88793,88772,88796,88776,88799,88736,88716,88739,88718,88698,88721,88742,88701,88703,88724,88746,88727,88748,88706,88751,88709,88730,88733,88754,88712,88715,88694,88780,88802,88697,88740,88762,88722,88745,88788,88704,88768,88728,88794,88752,88710,88774,88690,88734,88757,88672,88652,88675,88655,88678,88658,88681,88638,88660,88640,88684,88643,88664,88687,88667,88689,88646,88669,88649,88693,88587,88650,88632,88613,88676,88593,88656,88637,88617,88597,88682,88578,88663,88622,88644,88603,88583,88608,88670,88628,88609,88630,88589,88612,88592,88634,88614,88573,88595,88576,88618,88599,88621,88579,88602,88582,88624,88605,88627,88585,88523,88545,88503,88569,88527,88549,88507,88530,88510,88554,88534,88513,88558,88516,88538,88561,88519,88541,88500,88565,88568,88525,88547,88506,88572,88487,88551,88531,88511,88493,88555,88535,88559,88517,88539,88498,88563,88522,88543,88501,88481,88461,88484,88441,88464,88486,88444,88446,88467,88489,88470,88449,88492,88473,88496,88453,88476,88455,88478,88458,88395,88376,88400,88359,88422,88382,88405,88365,88429,88388,88412,88370,88417,88418,88397,88355,88420,88379,88360,88403,88425,88384,88364,88408,88368,88430,88389,88433,88351,88413,88394,88373,88437,88459,88354,88440,88419,88377,88337,88401,88465,88361,88447,88426,88385,88472,88452,88409,88347,88393,88371,88435,88479,88332,88290,88334,88314,88271,88295,88276,88339,88298,88256,88319,88323,88280,88344,88303,88262,88327,88285,88266,88309,88311,88269,88336,88293,88252,88274,88318,88341,88300,88257,88324,88282,88346,88239,88306,88263,88329,88287,88352,88245,88267,88225,88247,88206,88292,88315,88231,88253,88212,88277,88236,88194,88301,88260,88325,88219,88284,88242,88200,88307,88161,88227,88186,88249,88207,88167,88170,88233,88192,88213,88152,88238,88196,88218,88175,88156,88222,88180,88243,88201,88203,88183,88141,88166,88229,88123,88146,88209,88191,88150,88172,88129,88216,88154,88134,88197,88177,88159,88223,88118,88140,88078,88099,88121,88144,88081,88104,88061,88126,88063,88087,88110,88068,88131,88091,88114,88136,88096,88117,88073,88095,88119,88165,88079,88060,88187,88039,88147,88105,88127,88085,88045,88173,88111,88069,88029,88157,88051,88137,88181,88076,88055,88036,88059,88016,88102,87998,88083,88041,88021,88107,88066,88004,88026,88089,88047,88071,88009,88031,88097,88011,87970,88033,88015,87993,87974,88038,87997,88020,87980,88043,88001,88024,88006,88028,87985,88049,87965,87990,88053,87947,87929,87888,87952,87910,87977,87935,87893,87959,87917,87876,87941,87983,87899,87964,87923,87988,87881,87904,87969,87883,87887,87950,87907,87931,87911,87870,87891,87955,87914,87958,87874,87937,87897,87920,87878,87942,87901,87945,87925,87906,87927,87991,87971,87889,87954,88017,87976,87934,87871,87999,87916,87896,87982,87962,87922,87879,87943,88007,87863,87841,87799,87822,87865,87781,87846,87804,87826,87785,87807,87830,87851,87789,87812,87856,87835,87794,87860,87817,87776,87821,87864,87758,87779,87802,87869,87847,87764,87827,87786,87809,87832,87853,87770,87791,87814,87858,87774,87796,87840,87756,87778,87716,87845,87823,87739,87805,87721,87850,87701,87765,87787,87747,87833,87707,87772,87815,87839,87731,87797,87714,87738,87695,87759,87762,87719,87741,87700,87681,87746,87767,87725,87706,87728,87686,87751,87710,87689,87755,87733,87692,87737,87632,87717,87675,87698,87656,87679,87743,87638,87724,87704,87661,87685,87749,87643,87730,87668,87650,87711,87628,87649,87631,87588,87674,87653,87611,87635,87593,87616,87597,87659,87640,87619,87664,87601,87624,87645,87606,87669,87563,87543,87607,87671,87693,87651,87589,87633,87658,87680,87573,87553,87617,87534,87641,87599,87665,87687,87581,87625,87522,87587,87565,87610,87547,87591,87615,87571,87530,87552,87510,87598,87577,87535,87559,87622,87517,87540,87604,87583,87524,87546,87503,87567,87507,87572,87527,87550,87532,87511,87576,87555,87515,87580,87537,87560,87498,87562,87519,87542,87459,87439,87482,87420,87464,87444,87402,87468,87424,87488,87490,87449,87406,87429,87473,87454,87412,87477,87434,87415,87417,87480,87501,87396,87440,87400,87462,87485,87422,87446,87405,87469,87427,87491,87451,87411,87474,87433,87496,87456,87438,87500,87395,87375,87461,87418,87525,87442,87401,87487,87508,87470,87386,87410,87430,87493,87452,87516,87368,87478,87308,87353,87312,87376,87334,87358,87316,87380,87340,87363,87321,87385,87344,87367,87348,87326,87390,87371,87329,87394,87372,87288,87332,87356,87313,87378,87337,87294,87361,87318,87383,87278,87343,87366,87302,87324,87388,87283,87307,87350,87224,87247,87269,87291,87229,87273,87252,87276,87296,87255,87234,87214,87238,87300,87280,87260,87219,87242,87265,87286,87203,87266,87331,87248,87292,87355,87314,87230,87339,87213,87277,87298,87194,87258,87322,87240,87305,87220,87285,87349,87245,87183,87164,87227,87206,87270,87251,87189,87211,87233,87170,87257,87195,87217,87239,87176,87262,87201,87158,87222,87181,87138,87160,87142,87204,87165,87123,87186,87208,87147,87168,87191,87128,87152,87174,87196,87156,87134,87199,87179,87116,87055,87099,87122,87080,87144,87039,87104,87062,87126,87044,87088,87150,87067,87131,87110,87049,87093,87073,87137,87075,87035,87118,87057,87101,87061,87081,87038,87042,87106,87085,87065,87108,87047,87070,87091,87113,87052,87031,87096,87054,87098,87077,87037,87184,87143,87166,87125,87083,87063,87149,87107,87045,87173,87089,87132,87071,87030,87157,87115,86990,86947,87013,86971,86995,86953,87018,86976,86935,87000,86957,86939,87023,86981,87005,86963,86943,87009,86966,86987,86927,86992,86950,87015,86973,86934,86998,86956,87021,86979,86940,87003,86962,87026,87029,86921,86985,86945,87010,86968,86925,87011,86969,86993,86888,86951,86910,86933,86870,87020,86978,86894,86915,87001,86959,86920,86983,86942,86879,86901,86884,86842,86905,86864,86908,86929,86846,86869,86889,86851,86914,86871,86895,86919,86876,86856,86900,86859,86924,86881,86798,86862,86824,86885,86804,86868,86848,86911,86891,86831,86810,86873,86855,86897,86792,86878,86837,86816,86841,86904,86800,86758,86825,86783,86805,86762,86830,86787,86745,86809,86768,86791,86749,86813,86834,86773,86795,86753,86819,86778,86757,86820,86780,86844,86741,86826,86806,86722,86766,86789,86852,86746,86832,86814,86730,86774,86839,86797,86860,86713,86779,86694,86716,86739,86760,86676,86699,86721,86784,86743,86765,86681,86704,86726,86772,86750,86710,86688,86733,86755,86670,86734,86692,86715,86674,86737,86696,86655,86718,86678,86701,86660,86724,86683,86706,86665,86729,86687,86711,86650,86564,86651,86611,86570,86635,86592,86657,86617,86575,86640,86598,86662,86557,86622,86580,86646,86604,86668,86627,86586,86606,86567,86630,86588,86633,86591,86612,86615,86572,86595,86553,86638,86620,86578,86643,86601,86558,86624,86582,86562,86629,86587,86609,86652,86547,86675,86569,86636,86658,86702,86597,86555,86619,86577,86684,86645,86602,86666,86560,86691,86543,86522,86480,86503,86462,86485,86548,86528,86508,86468,86533,86490,86513,86494,86472,86538,86518,86477,86499,86457,86478,86500,86545,86460,86524,86482,86505,86465,86551,86445,86530,86488,86510,86471,86535,86451,86495,86517,86455,86541,86414,86458,86396,86526,86443,86506,86421,86487,86466,86382,86404,86428,86514,86536,86452,86476,86496,86390,86434,86520,86417,86375,86438,86442,86398,86422,86380,86403,86360,86446,86427,86384,86449,86364,86408,86389,86432,86413,86370,86394,86436,86330,86395,86354,86418,86376,86336,86358,86401,86381,86424,86341,86362,86406,86324,86387,86430,86411,86367,86348,86288,86352,86333,86312,86270,86293,86317,86275,86338,86298,86321,86343,86280,86303,86325,86284,86347,86307,86265,86329,86286,86350,86374,86310,86269,86335,86230,86294,86359,86252,86318,86276,86236,86300,86344,86368,86263,86326,86220,86243,86244,86309,86202,86266,86226,86290,86208,86251,86314,86272,86232,86297,86256,86215,86278,86238,86261,86219,86304,86285,86222,86182,86246,86204,86227,86250,86229,86187,86209,86192,86254,86212,86235,86174,86258,86217,86196,86240,86200,86179,86097,86119,86139,86163,86123,86102,86083,86145,86106,86168,86128,86150,86109,86088,86132,86153,86093,86114,86157,86138,86160,86099,86184,86142,86082,86167,86125,86189,86148,86105,86086,86172,86130,86194,86112,86135,86155,86178,86094,86117,86161,86120,86078,86101,86058,86185,86144,86127,86084,86210,86169,86066,86152,86110,86195,86090,86049,86176,86137,86201,86055,86077,86034,86015,85994,86039,86060,86019,85999,86043,86065,86024,86047,86005,86070,86029,86073,85990,86052,86010,85968,86032,85991,86057,85974,86016,85997,86040,86062,86022,85980,86045,86002,86069,85962,86027,85985,86051,86008,86075,85904,85926,85949,85970,85908,85931,85952,85975,85913,85934,85957,85978,85916,85939,85961,85983,85898,85921,85965,85944,86012,85992,85950,86036,85932,85891,85976,86021,85914,86000,85895,85959,85940,86006,85922,85986,85881,85903,85966,86030,85862,85884,85906,85930,85845,85867,85889,85912,85954,85851,85873,85936,85897,85918,85856,85879,85942,85901,85924,85948,85842,85864,85823,85886,85846,85805,85850,85869,85828,85892,85810,85874,85833,85854,85814,85878,85837,85859,85818,85882,85776,85734,85799,85820,85759,85803,85825,85783,85742,85765,85808,85832,85789,85748,85771,85729,85815,85794,85838,85754,85713,85756,85779,85737,85761,85718,85741,85784,85786,85766,85724,85746,85770,85728,85792,85751,85709,85774,85732,85796,85714,85843,85800,85782,85738,85870,85762,85826,85806,85722,85744,85852,85791,85834,85708,85772,85730,85753,85816,85860,85648,85692,85673,85630,85653,85697,85635,85678,85658,85617,85702,85661,85683,85640,85622,85688,85645,85666,85626,85669,85670,85650,85610,85695,85716,85633,85676,85721,85657,85615,85700,85681,85638,85619,85706,85663,85644,85710,85627,85690,85544,85628,85589,85675,85654,85612,85572,85698,85553,85636,85596,85620,85684,85579,85537,85665,85562,85689,85646,85606,85586,85607,85545,85568,85611,85527,85590,85549,85573,85532,85595,85554,85577,85535,85599,85557,85581,85539,85603,85563,85521,85565,85588,85503,85526,85547,85570,85530,85593,85509,85491,85555,85515,85578,85536,85600,85560,85497,85583,85542,85479,85438,85461,85505,85465,85485,85443,85488,85447,85511,85469,85493,85452,85516,85474,85495,85433,85456,85519,85500,85416,85395,85459,85482,85377,85442,85400,85422,85466,85383,85405,85427,85449,85471,85410,85432,85389,85454,85477,85436,85457,85501,85525,85376,85439,85483,85507,85402,85359,85423,85445,85467,85492,85385,85430,85367,85517,85413,85475,85392,85393,85375,85354,85417,85397,85357,85421,85379,85339,85403,85361,85425,85384,85344,85407,85366,85388,85349,85412,85371,85265,85353,85290,85270,85333,85314,85337,85358,85297,85320,85278,85341,85363,85302,85260,85326,85283,85347,85369,85309,85310,85268,85332,85247,85291,85294,85252,85315,85273,85318,85277,85256,85299,85259,85323,85281,85305,85263,85328,85286,85329,85287,85246,85311,85205,85271,85230,85338,85295,85189,85253,85214,85321,85279,85239,85195,85346,85303,85261,85223,85202,85160,85222,85227,85184,85164,85207,85188,85169,85231,85212,85150,85235,85194,85173,85217,85198,85155,85241,85179,85182,85204,85142,85228,85186,85250,85165,85209,85148,85170,85233,85191,85152,85215,85175,85240,85221,85199,85157,85245,85095,85118,85076,85140,85100,85058,85144,85123,85081,85127,85105,85063,85109,85066,85087,85131,85090,85113,85071,85136,85074,85034,85097,85056,85121,85079,85040,85103,85062,85085,85128,85023,85110,85069,85047,85133,85092,85029,85052,85115,85137,85053,85161,85120,85077,85035,85016,85102,85059,85145,85086,85043,85171,85129,85025,85153,85111,85068,85177,85094,85032,85012,84971,84993,85037,85017,84975,85020,85042,84999,84960,85024,84981,85046,85004,85028,85050,85008,84965,84987,84947,85009,84970,84991,85014,84908,84931,84954,84997,84913,84978,84936,84958,85003,84918,84941,84901,84963,84985,84924,84882,84925,84948,84906,84929,84866,84887,84953,84890,84910,84933,84871,84915,84938,84895,84899,84920,84877,84943,84902,84903,84967,84863,84990,84884,84949,84930,84911,84973,84995,84870,84955,84893,84979,84876,84939,84962,84984,85005,84921,84840,84799,84864,84822,84885,84782,84846,84804,84867,84827,84892,84851,84809,84873,84789,84833,84794,84857,84816,84879,84817,84775,84797,84821,84779,84841,84845,84802,84825,84783,84786,84849,84807,84830,84812,84770,84791,84855,84835,84860,84736,84694,84780,84823,84717,84847,84806,84763,84788,84745,84703,84831,84853,84727,84813,84708,84771,84753,84838,84795,84690,84754,84711,84734,84692,84755,84715,84672,84757,84716,84675,84737,84695,84760,84739,84697,84762,84719,84678,84742,84699,84721,84681,84744,84702,84765,84724,84682,84769,84726,84748,84705,84687,84749,84729,84688,84709,84773,84732,84671,84584,84607,84630,84652,84590,84655,84612,84635,84595,84617,84660,84576,84640,84600,84622,84580,84603,84666,84626,84646,84627,84587,84651,84567,84610,84632,84571,84592,84615,84638,84658,84575,84555,84599,84621,84664,84560,84645,84582,84604,84648,84543,84566,84628,84609,84588,84677,84657,84552,84573,84639,84598,84619,84662,84684,84579,84642,84537,84561,84670,84563,84522,84479,84502,84546,84526,84484,84568,84550,84507,84531,84489,84554,84512,84493,84536,84558,84517,84497,84542,84500,84438,84523,84482,84461,84547,84443,84505,84468,84529,84487,84510,84534,84494,84452,84516,84474,84539,84457,84478,84437,84396,84459,84419,84441,84400,84464,84423,84446,84405,84469,84428,84387,84451,84472,84410,84432,84455,84392,84415,84395,84458,84416,84377,84503,84528,84485,84444,84383,84467,84427,84448,84407,84513,84366,84388,84495,84476,84436,84519,84354,84375,84335,84398,84420,84358,84380,84403,84425,84363,84385,84343,84323,84408,84430,84368,84391,84349,84414,84329,84374,84331,84289,84312,84336,84356,84378,84295,84317,84341,84361,84322,84301,84365,84346,84326,84283,84307,84370,84352,84245,84309,84269,84291,84355,84251,84315,84337,84234,84297,84320,84277,84342,84257,84282,84303,84347,84263,84328,84286,84267,84247,84314,84230,84293,84210,84273,84191,84255,84299,84217,84280,84237,84197,84261,84242,84306,84203,84224,84287,84204,84228,84186,84249,84207,84271,84232,84190,84254,84276,84213,84235,84194,84259,84218,84239,84199,84222,84244,84265,84120,84143,84100,84163,84166,84124,84147,84105,84129,84171,84152,84110,84133,84155,84175,84095,84158,84116,84180,84138,84181,84079,84142,84098,84161,84225,84121,84184,84205,84122,84081,84144,84102,84188,84168,84126,84085,84149,84211,84107,84170,84151,84108,84131,84088,84173,84196,84092,84114,84072,84134,84093,84156,84219,84115,84178,84073,84137,84096,84160,84056,84017,84080,84060,84040,84082,84043,84022,84065,84026,84087,84068,84047,84071,84009,84030,84052,84013,84075,84035,83951,84014,84057,84039,83997,83957,83977,84020,84063,83984,84046,84004,83964,84027,84008,84050,83946,83991,83970,84032,83974,83995,83953,83933,83999,83979,83938,84002,83959,83982,83961,83942,83945,83966,83987,83925,83928,83992,83949,83971,83994,84036,83931,83911,83976,84019,84061,83958,83896,84045,83939,84003,83922,83985,84028,83904,83967,83948,84010,84053,83889,83909,83868,83847,83892,83851,83914,83873,83917,83876,83897,83855,83836,83901,83880,83860,83841,83905,83864,83885,83865,83930,83824,83845,83890,83870,83937,83830,83894,83852,83915,83835,83920,83878,83857,83902,83924,83839,83883,83907,83738,83803,83825,83784,83807,83763,83829,83743,83789,83811,83769,83749,83793,83774,83754,83817,83798,83821,83757,83779,83782,83761,83742,83871,83766,83809,83831,83853,83748,83791,83815,83837,83881,83775,83862,83755,83737,83800,83822,83844,83801,83760,83741,83698,83785,83808,83724,83746,83705,83767,83790,83814,83772,83730,83753,83710,83795,83735,83778,83717,83718,83677,83656,83700,83722,83681,83704,83662,83643,83728,83686,83708,83667,83733,83648,83713,83692,83672,83696,83652,83610,83632,83697,83655,83721,83678,83594,83616,83638,83661,83727,83685,83706,83600,83622,83646,83605,83669,83691,83715,83676,83591,83612,83637,83658,83575,83596,83618,83683,83641,83664,83645,83625,83688,83582,83606,83670,83587,83651,83631,83549,83570,83634,83593,83614,83574,83554,83599,83620,83578,83538,83604,83560,83626,83584,83543,83629,83608,83566,83589,83569,83526,83485,83550,83508,83531,83468,83490,83576,83535,83514,83473,83559,83581,83496,83564,83520,83479,83544,83502,83546,83505,83466,83486,83552,83532,83448,83512,83493,83557,83537,83474,83454,83518,83541,83498,83565,83480,83460,83525,83482,83441,83462,83506,83528,83446,83467,83424,83488,83511,83472,83450,83430,83494,83517,83477,83434,83456,83500,83522,83421,83442,83400,83360,83382,83447,83365,83426,83406,83388,83453,83411,83370,83432,83394,83459,83354,83416,83376,83438,83356,83377,83317,83338,83381,83342,83403,83362,83322,83387,83346,83408,83368,83326,83351,83373,83393,83414,83332,83397,83418,83315,83336,83399,83359,83379,83423,83321,83343,83405,83384,83366,83429,83349,83392,83412,83330,83353,83374,83437,83296,83253,83232,83318,83277,83259,83344,83302,83324,83283,83243,83264,83328,83308,83227,83290,83248,83314,83270,83334,83250,83272,83233,83213,83295,83300,83256,83278,83237,83219,83242,83305,83262,83284,83224,83246,83289,83310,83268,83228,83229,83292,83188,83274,83254,83235,83215,83301,83195,83280,83240,83260,83221,83180,83307,83201,83286,83267,83247,83208,83145,83209,83167,83128,83191,83149,83212,83109,83175,83133,83197,83155,83218,83115,83181,83139,83203,83161,83121,83185,83126,83189,83148,83106,83169,83194,83174,83132,83154,83111,83178,83199,83138,83160,83117,83122,83183,83143,83205,83164,83166,83123,83104,83084,83108,83171,83065,83129,83151,83046,83090,83114,83071,83135,83158,83052,83097,83078,83058,83144,83059,83082,83041,83063,83022,83045,83087,83007,83069,83028,83049,83093,83011,83074,83032,83054,83036,83099,83016,83079,83101,83039,83061,83020,82978,83085,83002,83067,83027,82985,83047,83091,83008,83096,83055,83075,83033,82992,83014,82972,82975,83038,82933,83018,83000,82939,82960,83024,82982,83005,82922,82945,82966,83031,82988,82969,83012,82928,82994,82952,82911,82996,82954,82976,82935,83001,82959,82916,82981,82940,82963,82921,82943,82986,82924,82991,82948,82907,82971,82930,82846,82826,82891,82848,82913,82870,82828,82958,82872,82936,82895,82853,82811,82832,82855,82920,82877,82834,82898,82814,82900,82964,82858,82816,82880,82839,82861,82882,82946,82840,82905,82927,82821,82885,82864,82951,82844,82868,82825,82888,82805,82869,82892,82850,82914,82810,82831,82874,82897,82813,82856,82879,82837,82903,82818,82862,82843,82824,82887,82908,82784,82742,82806,82722,82746,82766,82788,82769,82727,82793,82750,82774,82732,82755,82798,82779,82737,82802,82718,82761,82719,82783,82740,82701,82764,82724,82683,82790,82748,82771,82729,82708,82689,82753,82796,82713,82776,82735,82694,82758,82698,82763,82720,82677,82787,82747,82705,82662,82684,82772,82730,82795,82670,82692,82756,82714,82653,82782,82738,82803,82654,82678,82636,82659,82681,82702,82641,82620,82706,82664,82686,82625,82646,82711,82669,82691,82650,82672,82630,82697,82590,82656,82614,82572,82638,82597,82661,82619,82577,82559,82644,82603,82668,82626,82584,82564,82651,82608,82674,82632,82526,82571,82592,82552,82575,82532,82555,82598,82558,82579,82537,82601,82583,82562,82542,82606,82567,82588,82547,82611,82613,82634,82529,82551,82508,82594,82617,82534,82642,82622,82518,82580,82560,82540,82604,82498,82628,82587,82525,82568,82462,82484,82549,82507,82444,82467,82530,82490,82449,82512,82472,82496,82538,82455,82517,82479,82437,82524,82544,82502,82442,82464,82488,82447,82510,82469,82493,82515,82452,82474,82497,82435,82457,82520,82478,82500,82439,82460,82482,82505,82399,82360,82422,82486,82383,82405,82343,82470,82428,82450,82367,82389,82434,82349,82413,82459,82354,82480,82377,82440,82336,82421,82402,82382,82340,82361,82427,82407,82366,82388,82345,82412,82371,82331,82393,82351,82416,82376,82398,82356,82357,82379,82338,82404,82424,82342,82363,82323,82386,82409,82430,82348,82369,82328,82392,82414,82374,82397,82333,82418,82271,82316,82253,82297,82320,82277,82235,82258,82324,82282,82240,82303,82262,82306,82244,82266,82287,82291,82248,82311,82230,82251,82274,82296,82213,82234,82257,82279,82239,82302,82219,82263,82285,82308,82245,82225,82207,82269,82292,82314,82206,82293,82187,82167,82232,82317,82275,82301,82216,82259,82197,82325,82283,82177,82241,82224,82309,82268,82332,82250,82166,82145,82209,82189,82149,82214,82171,82194,82153,82217,82176,82199,82158,82222,82179,82202,82205,82162,82184,82227,82103,82126,82147,82169,82191,82110,82175,82132,82196,82154,82093,82116,82159,82181,82139,82098,82143,82164,82121,82186,82101,82060,82123,82083,82105,82065,82129,82088,82111,82070,82133,82092,82114,82052,82137,82096,82075,82056,82119,82079,82144,82037,82017,82081,81999,82063,82128,81979,82107,82046,82090,82027,82155,82071,82138,82009,81989,82053,82117,82099,82080,81977,82062,82019,82041,82085,82001,82024,81982,82068,82047,82006,82051,82030,81988,82073,82013,82036,81994,82057,82018,81975,81996,82039,81978,82000,82021,82044,82003,82026,81983,81963,81986,82008,81966,82031,82012,82035,81991,81971,81888,81953,81911,81870,81934,81892,81956,81916,81937,81875,81897,81920,81880,81943,81901,81925,81884,81947,81906,81930,81952,81910,81868,81889,81872,81935,81894,81958,81917,81940,81962,81877,81899,81922,81883,81945,81904,81861,81969,81927,81825,81806,81931,81849,81913,81873,81833,81895,81960,81815,81942,81858,81797,81923,81968,81841,81885,81949,81907,81865,81827,81848,81787,81809,81832,81792,81853,81814,81856,81836,81796,81837,81860,81819,81799,81822,81864,81783,81843,81804,81761,81845,81785,81807,81767,81830,81746,81790,81852,81812,81835,81795,81751,81774,81818,81756,81840,81779,81801,81824,81698,81720,81741,81763,81744,81723,81768,81703,81707,81728,81749,81772,81710,81753,81733,81777,81693,81715,81737,81759,81636,81700,81679,81725,81661,81641,81684,81708,81730,81623,81647,81667,81691,81713,81736,81672,81631,81695,81654,81719,81675,81784,81613,81721,81657,81701,81639,81748,81620,81685,81769,81665,81732,81775,81712,81692,81649,81758,81630,81740,81612,81633,81656,81677,81638,81659,81617,81682,81664,81622,81643,81687,81626,81648,81605,81669,81628,81609,81651,81674,81572,81594,81552,81576,81597,81557,81580,81562,81585,81588,81567,81549,81530,81512,81534,81517,81539,81522,81544,81526,81548,81570,81527,81615,81510,81532,81595,81555,81514,81577,81600,81537,81560,81604,81520,81583,81542,81565,81610,81589,81422,81486,81508,81592,81423,81445,81509,81467,81426,81490,81573,81491,81554,81450,81472,81430,81451,81473,81535,81495,81454,81515,81602,81433,81582,81477,81435,81499,81458,81500,81563,81482,81440,81461,81525,81483,81545,81441,81504,81463,81443,81465,81487,81449,81407,81470,81427,81493,81432,81412,81475,81498,81455,81481,81437,81460,81418,81502,81421,81401,81337,81403,81360,81383,81342,81365,81408,81388,81347,81411,81392,81370,81351,81374,81415,81396,81355,81334,81399,81378,81358,81381,81296,81276,81339,81363,81321,81386,81345,81301,81281,81369,81326,81393,81307,81288,81352,81376,81332,81314,81252,81317,81404,81233,81297,81384,81277,81366,81260,81284,81348,81305,81328,81413,81244,81395,81375,81269,81356,81335,81295,81253,81316,81275,81232,81320,81299,81258,81279,81238,81324,81304,81242,81263,81285,81309,81268,81289,81247,81272,81231,81187,81167,81147,81255,81213,81173,81237,81194,81153,81218,81261,81199,81265,81225,81181,81245,81205,81162,81250,81146,81190,81169,81131,81149,81215,81196,81175,81155,81220,81136,81180,81201,81161,81141,81226,81185,81207,81164,81211,81165,81124,81083,81210,81106,81212,81044,81191,81045,81108,81066,81132,81176,81092,81154,81239,81071,81135,81197,81050,81114,81177,81095,81158,81221,81074,81330,81077,81057,81122,81312,81144,81227,81292,81058,81186,81145,81104,81060,81021,81043,81084,81065,81089,81047,81110,81028,81072,81032,81052,81116,81096,81014,81099,81078,81039,81123,81042,81062,81126,81022,81107,81086,81070,81133,81049,81113,81093,81029,81010,81138,81056,81118,81035,81015,81100,81080,80955,80977,80935,81002,80960,80940,81025,80984,80921,80944,81008,80965,80989,81012,81033,80949,80971,80929,80995,81017,80912,80934,80998,80957,80916,80979,81005,80920,80941,80963,80901,80924,80987,80947,80906,80968,80928,80993,80951,80973,80975,80913,80999,80937,80918,80983,80875,80899,80962,80858,80945,80969,80925,80883,80992,80907,80868,80931,80891,80954,80783,80869,80892,80831,80851,80809,80873,80789,80856,80795,80815,80880,80838,80843,80800,80863,80821,80886,80804,80825,80850,80807,80872,80893,80787,80897,80855,80833,80791,80879,80839,80903,80797,80861,80820,80844,80867,80887,80782,80909,80720,80847,80806,80829,80786,80744,80767,80726,80812,80837,80752,80710,80774,80794,80818,80737,80781,80801,80823,80761,80743,80703,80765,80723,80685,80707,80749,80771,80669,80731,80691,80713,80755,80777,80696,80674,80736,80760,80719,80677,80680,80764,80658,80722,80704,80664,80747,80769,80730,80686,80709,80753,80775,80670,80733,80692,80757,80716,80698,80739,80614,80700,80597,80682,80745,80577,80832,81023,80666,80814,81006,80900,80728,80986,80860,80881,80715,80633,80652,80846,80595,80617,80681,80639,80660,80556,80580,80602,80667,80625,80688,80647,80564,80586,80608,80673,80632,80655,80573,80699,80594,80657,80551,80574,80636,80619,80557,80579,80642,80600,80622,80646,80583,80605,80562,80629,80651,80567,80589,80612,80554,80575,80532,80640,80599,80620,80537,80560,80519,80626,80584,80649,80606,80544,80568,80526,80590,80549,80613,80634,80528,80486,80467,80446,80512,80534,80451,80473,80431,80494,80517,80541,80499,80457,80521,80436,80480,80442,80505,80463,80423,80530,80469,80491,80448,80429,80516,80408,80453,80538,80433,80414,80477,80500,80441,80461,80524,80483,80547,80507,80464,80444,80425,80490,80510,80407,80470,80367,80388,80346,80496,80454,80434,80416,80478,80502,80398,80358,80484,80379,80401,80359,80380,80338,80406,80362,80343,80387,80324,80410,80368,80391,80348,80329,80373,80395,80352,80417,80334,80421,80336,80275,80297,80360,80318,80384,80322,80365,80345,80304,80284,80371,80392,80350,80331,80310,80397,80290,80377,80270,80272,80253,80235,80299,80258,80278,80240,80285,80305,80263,80267,80245,80309,80225,80288,80248,80269,80314,80230,80293,80316,80508,80404,80341,80428,80386,80300,80492,80282,80558,80219,80475,80327,80542,80458,80523,80374,80356,80418,80443,80167,80231,80296,80214,80276,80195,80260,80323,80177,80241,80222,80306,80159,80286,80268,80205,80333,80187,80251,80315,80212,80233,80192,80255,80170,80239,80218,80175,80261,80156,80199,80158,80244,80224,80181,80204,80165,80228,80186,80250,80189,80148,80213,80171,80128,80193,80153,80216,80176,80197,80135,80115,80179,80202,80161,80184,80122,80143,80207,80166,80146,80104,80125,80021,80086,80044,80067,80132,80111,80028,80093,80052,80073,80138,80098,80119,80014,80080,80037,80060,80017,80081,80040,80107,80063,80002,80024,80087,80090,80047,80071,80029,80009,80095,80053,80076,80035,80059,80101,79996,80061,80083,80043,79999,80149,80108,80025,80069,80133,80092,80051,80114,80007,79990,80140,80033,80077,80099,80016,80124,80019,79936,80130,80045,80109,80003,80068,80154,79919,79963,79988,80032,80118,80012,80055,80142,79929,79994,79952,79973,79955,79976,79892,79915,79939,79959,79981,79899,79921,79987,79880,79943,79966,79904,79927,79948,79970,79886,79909,79931,79889,79911,79935,79998,79956,79978,79871,79917,79896,79877,79962,79983,79941,80006,79903,79924,79882,79969,79991,79949,79827,79847,79957,79979,79918,79938,79898,79878,79793,79837,79859,79817,79947,79928,79907,79972,79887,79782,79804,79868,79762,79870,79828,79786,79852,79809,79768,79833,79792,79858,79816,79774,79840,79797,79756,79864,79822,79780,79803,79846,79805,79787,79849,79769,79894,79873,79831,79813,79857,79730,79752,79795,79883,79778,79841,79906,79866,79759,79824,79740,79783,79763,79722,79743,79807,79829,79791,79853,79749,79770,79729,79814,79836,79754,79776,79861,79819,79735,79799,79844,79679,79637,79701,79723,79745,79662,79727,79685,79707,79645,79668,79650,79712,79733,79692,79674,79694,79717,79739,79655,79699,79593,79656,79720,79615,79741,79638,79601,79623,79687,79751,79771,79667,79646,79709,79731,79609,79631,79758,79676,79635,79572,79595,79659,79621,79682,79704,79643,79665,79580,79563,79604,79690,79629,79651,79713,79589,79675,79697,79612,79698,79680,79576,79660,79640,79598,79556,79537,79708,79624,79688,79670,79587,79566,79526,79652,79547,79610,79633,79719,79530,79552,79616,79596,79577,79535,79622,79515,79559,79602,79582,79540,79564,79628,79520,79608,79524,79546,79569,79590,79550,79512,79468,79533,79491,79429,79450,79411,79519,79476,79435,79498,79415,79542,79459,79505,79484,79440,79527,79420,79570,79465,79529,79445,79508,79406,79428,79555,79578,79495,79516,79475,79538,79454,79584,79436,79565,79416,79483,79549,79444,79507,79423,79404,79466,79427,79488,79449,79409,79471,79432,79496,79414,79456,79478,79500,79438,79460,79418,79485,79318,79381,79385,79342,79299,79365,79324,79345,79389,79306,79369,79287,79329,79395,79351,79311,79376,79336,79293,79358,79274,79403,79341,79297,79364,79321,79387,79280,79305,79284,79347,79327,79392,79371,79290,79355,79333,79313,79378,79399,79316,79296,79275,79363,79343,79302,79259,79386,79281,79368,79325,79349,79265,79309,79373,79331,79396,79291,79356,79250,79379,79338,79359,79486,79253,79319,79446,79513,79494,79410,79474,79430,79455,79243,79307,79289,79272,79397,79506,79463,79252,79231,79193,79277,79237,79258,79215,79197,79220,79177,79242,79263,79182,79247,79203,79269,79225,79187,79209,79273,79192,79149,79170,79235,79255,79213,79175,79155,79241,79135,79198,79261,79221,79180,79141,79162,79185,79248,79205,79228,79125,79169,79084,79106,79129,79150,79067,79153,79134,79091,79113,79071,79159,79138,79096,79118,79078,79144,79164,79103,79188,79083,79146,79104,79063,79126,79211,79240,79068,79093,79157,79114,79178,79136,79200,79222,79053,79077,79168,79229,79040,79021,79001,79065,79087,79045,79109,79025,79007,79051,79072,79094,79116,79033,78993,79014,79123,79102,79059,79080,79061,79020,79210,79000,79132,79194,79090,79111,79176,78986,79049,79031,79076,79201,79160,79223,78971,79098,79124,79145,78998,78979,79043,79024,79004,78985,79048,78963,79028,79009,78990,79011,78970,79054,79034,78994,79060,78975,79018,79039,78977,78936,78960,78919,78878,79006,78898,79026,78860,78987,78945,78968,78928,78887,78909,78951,79016,79036,78869,78995,78871,78891,78956,78913,78853,78917,78938,78896,78876,78858,78921,78880,78943,78901,78926,78884,78906,78865,78950,78932,78933,78895,78875,78854,78918,78983,78939,78962,78967,78923,78882,78903,78861,78947,78868,78888,78847,78954,78912,78976,78806,78744,78831,78791,78769,78749,78813,78772,78836,78753,78796,78818,78840,78757,78779,78845,78803,78762,78825,78784,78743,78827,78725,78787,78809,78768,78748,78835,78730,78794,78816,78774,78754,78712,78800,78717,78738,78759,78823,78781,78849,78872,78765,78958,78832,78685,78811,78899,78790,78856,78944,78777,78841,78695,78822,78802,78931,78910,78890,78700,78764,78785,78807,78659,78683,78746,78726,78709,78837,78691,78775,78734,78797,78755,78821,78672,78718,78741,78848,78681,78724,78704,78641,78707,78664,78728,78686,78711,78670,78733,78648,78692,78715,78737,78655,78676,78699,78658,78720,78576,78660,78619,78682,78640,78703,78602,78561,78666,78626,78689,78584,78646,78610,78568,78654,78674,78633,78696,78595,78618,78534,78554,78577,78598,78558,78624,78582,78540,78544,78606,78564,78629,78588,78613,78571,78528,78594,78550,78634,78490,78637,78535,78515,78662,78622,78581,78603,78644,78562,78503,78524,78481,78546,78671,78630,78653,78590,78614,78572,78469,78596,78621,78578,78536,78494,78559,78516,78643,78475,78604,78587,78609,78567,78504,78632,78462,78527,78548,78486,78552,78513,78429,78493,78452,78539,78477,78498,78520,78437,78459,78417,78526,78483,78547,78506,78423,78444,78467,78531,78425,78514,78492,78449,78473,78430,78410,78434,78496,78455,78518,78413,78479,78502,78461,78419,78441,78485,78468,78508,78298,78382,78342,78366,78323,78389,78304,78347,78371,78288,78330,78395,78352,78311,78377,78293,78337,78399,78359,78317,78360,78318,78341,78300,78363,78426,78320,78408,78301,78387,78450,78280,78409,78282,78348,78368,78327,78390,78287,78307,78436,78328,78392,78350,78416,78308,78372,78334,78290,78356,78400,78314,78378,78442,78274,78294,78380,78275,78338,78402,78447,78276,78405,78386,78470,78345,78302,78367,78325,78457,78266,78289,78376,78438,78397,78313,78335,78357,78420,78252,78253,78212,78170,78235,78194,78278,78258,78262,78219,78176,78241,78200,78224,78183,78247,78206,78268,78272,78231,78189,78190,78131,78257,78216,78173,78236,78196,78154,78138,78265,78222,78182,78244,78202,78162,78250,78166,78230,78145,78210,78232,78149,78109,78090,78174,78069,78133,78197,78263,78156,78220,78242,78077,78100,78122,78184,78142,78208,78168,78254,78106,78064,78130,78086,78066,78088,78153,78113,78071,78134,78094,78159,78118,78076,78141,78101,78060,78081,78125,78146,78042,78024,78068,78111,78006,78091,78049,78030,78074,78097,78054,78012,78120,78036,78058,78079,78103,78063,78019,78085,78021,77979,78044,78001,78005,77963,78026,77984,78048,78008,78052,77968,78031,78035,77991,78013,78016,77973,77996,78039,77913,77977,78169,77935,77999,78107,78150,78047,78132,78218,77919,78239,77900,77964,78027,77986,78198,77901,78115,78178,77945,78009,77988,78140,77970,78098,78161,77927,78056,77907,78228,77993,78207,78037,78123,78186,77890,78018,77891,77955,77937,77896,77959,77918,77981,77876,77943,77965,77924,77989,77904,77883,77949,77971,77889,77931,77954,77911,77976,77997,77893,77957,77916,77939,77898,77877,77921,77944,77860,77882,77926,77947,77905,77887,77865,77930,77952,77910,77871,77934,77807,77829,77790,77853,77748,77813,77770,77835,77776,77795,77755,77818,77840,77823,77781,77802,77760,77846,77765,77784,77785,77850,77767,77811,77834,77857,77751,77772,77732,77793,77798,77819,77779,77863,77759,77843,77739,77825,77746,77805,77745,77703,77788,77852,77875,77730,77814,77689,77752,77711,77839,77778,77861,77737,77801,77696,77718,77868,77826,77766,77872,77724,77747,77768,77833,77792,77688,77859,77815,77879,77712,77734,77758,77841,77782,77677,77804,77847,77701,77827,77660,77723,77681,77704,77727,77687,77643,77666,77647,77710,77670,77733,77693,77630,77653,77716,77676,77740,77637,77699,77596,77618,77685,77641,77665,77706,77602,77623,77692,77651,77672,77629,77714,77609,77590,77635,77700,77658,77721,77679,77594,77617,77554,77577,77534,77599,77620,77515,77559,77581,77605,77522,77586,77542,77564,77547,77610,77527,77591,77571,77531,77639,77513,77493,77560,77578,77539,77667,77625,77648,77606,77588,77675,77502,77567,77524,77657,77549,77614,77532,77661,77491,77516,77474,77603,77583,77541,77562,77627,77501,77523,77650,77484,77592,77551,77616,77509,77572,77638,77490,77553,77512,77575,77449,77472,77536,77431,77497,77561,77455,77519,77481,77544,77438,77568,77506,77464,77528,77444,77446,77469,77426,77429,77451,77473,77494,77411,77434,77499,77456,77414,77478,77436,77419,77483,77441,77505,77462,77488,77403,77296,77340,77362,77386,77345,77325,77304,77369,77390,77329,77351,77395,77335,77355,77312,77376,77399,77317,77381,77338,77360,77425,77318,77405,77385,77302,77367,77452,77347,77433,77326,77412,77309,77373,77396,77460,77420,77442,77295,77383,77300,77344,77406,77365,77322,77410,77388,77306,77393,77330,77352,77416,77374,77292,77358,77315,77337,77400,77422,77275,77467,77255,77320,77301,77283,77240,77264,77350,77476,77370,77459,77224,77246,77311,77336,77293,77378,77232,77359,77211,77233,77192,77215,77278,77258,77239,77262,77220,77199,77285,77181,77245,77289,77268,77226,77206,77273,77187,77251,77146,77257,77238,77195,77216,77282,77175,77154,77180,77136,77265,77223,77202,77160,77186,77248,77229,77209,77274,77166,77191,77212,77276,77172,77234,77153,77091,77135,77221,77114,77242,77201,77286,77266,77182,77141,77103,77163,77124,77253,77082,77167,77086,77149,77128,77109,77173,77133,77070,77092,77155,77157,77116,77076,77138,77098,77162,77122,77144,77104,77105,77088,77152,77045,77025,77069,77134,77196,77113,77177,77050,77094,77205,77034,77078,77142,77123,77059,77189,77126,77022,77044,77106,77065,77089,76983,77111,77006,77030,77072,77052,77096,76991,77118,77014,77037,77060,77080,76998,76955,77020,76977,77041,76999,77062,76982,76961,77004,77026,77048,76966,76987,77010,77031,77055,76971,76993,77016,77038,76935,76956,76979,77002,77023,76917,76875,77068,76896,77046,76946,76967,76988,77033,76885,77012,77077,76906,76928,77056,76890,76894,76852,76915,76874,76936,76940,76899,76856,76921,76878,76862,76883,76841,76905,76927,76948,76847,76911,76868,76958,76938,76925,76947,76968,76953,76931,76974,76873,76895,76853,76918,76838,76858,76881,76903,76865,76888,76844,76909,76848,76913,76789,77001,76876,76963,76984,76943,76900,76922,76839,77011,76863,76973,76994,76825,76889,76954,76805,76933,76763,76742,76788,76809,76830,76746,76769,76834,76813,76793,76750,76774,76797,76754,76818,76778,76824,76803,76760,76783,76699,76786,76808,76765,76828,76745,76726,76706,76794,76752,76816,76775,76734,76822,76714,76800,76759,76780,76740,76718,76826,76701,76723,76681,76768,76810,76790,76855,76749,76836,76815,76733,76713,76777,76798,76692,76756,76842,76866,76741,76721,76679,76658,76639,76702,76705,76664,76644,76729,76686,76627,76711,76691,76670,76651,76674,76736,76696,76716,76632,76592,76656,76615,76637,76725,76621,76685,76770,76600,76665,76560,76580,76710,76646,76628,76735,76608,76676,76569,76698,76635,76574,76597,76660,76682,76641,76557,76622,76689,76582,76605,76669,76648,76564,76629,76546,76590,76654,76613,76677,76571,76550,76595,76617,76510,76532,76556,76576,76515,76539,76602,76519,76561,76584,76543,76566,76610,76505,76526,76591,76507,76572,76555,76618,76598,76492,76579,76516,76645,76667,76562,76540,76607,76500,76586,76630,76525,76483,76547,76655,76466,76528,76423,76508,76448,76491,76513,76536,76429,76474,76454,76496,76521,76415,76480,76437,76460,76503,76442,76485,76487,76445,76469,76426,76490,76450,76431,76494,76475,76435,76455,76414,76478,76499,76458,76418,76482,76439,76463,76422,76360,76382,76405,76384,76364,76387,76409,76366,76346,76369,76391,76350,76372,76394,76397,76354,76376,76378,76401,76358,76381,76443,76338,76363,76406,76427,76345,76472,76389,76451,76413,76370,76436,76352,76375,76332,76399,76461,76357,76419,76316,76340,76299,76320,76302,76323,76283,76305,76326,76285,76308,76329,76331,76290,76311,76314,76334,76293,76336,76296,76254,76276,76256,76236,76217,76279,76239,76259,76262,76221,76244,76266,76225,76268,76248,76270,76228,76251,76273,76233,76234,76297,76319,76215,76277,76260,76220,76282,76241,76303,76324,76265,76289,76246,76309,76226,76209,76271,76252,76315,76191,76211,76170,76173,76194,76197,76154,76176,76157,76200,76180,76203,76160,76182,76205,76164,76185,76207,76188,76168,76126,76106,76129,76150,76088,76111,76132,76135,76092,76115,76095,76138,76118,76141,76098,76101,76123,76144,76147,76104,76148,76192,76087,76109,76130,76153,76174,76091,76198,76178,76136,76159,76116,76097,76142,76186,76080,76102,76167,76124,76063,76085,76402,76043,76530,76066,76342,76470,76046,76069,76029,76049,76112,76071,76028,76410,76537,76243,76222,76052,76074,76392,76032,76351,76055,76077,76035,76122,76079,76523,76165,76291,76058,76038,76231,76061,76082,76212,76041,76548,75999,76021,75979,76001,76024,75982,76004,75984,76007,75987,76009,75990,76012,75969,75972,75993,76015,75996,76018,75975,76064,76044,75961,76025,76005,75985,76050,76072,75968,76030,75991,75949,76013,76057,75973,76036,75997,75955,76019,75977,75957,75916,75937,75960,75919,75941,75963,75922,75943,75965,75946,75925,75948,75928,75951,75910,75931,75954,75934,75913,75871,75874,75895,75853,75898,75856,75877,75901,75859,75881,75862,75883,75905,75886,75865,75846,75868,75889,75892,75850,75935,75893,75851,75917,75875,75940,75899,75857,75880,75923,75903,75842,75863,75844,75907,75929,75887,75847,75911,75869,75808,75830,75810,75832,75812,75834,75814,75836,75816,75838,75818,75840,75820,75822,75802,75824,75804,75826,75806,75828,75766,75788,75768,75790,75770,75792,75772,75794,75774,75796,75776,75798,75778,75800,75780,75782,75762,75784,75764,75786,75744,75724,75746,75726,75748,75728,75750,75730,75752,75732,75754,75734,75756,75736,75758,75738,75760,75740,75742,75722,73794,73638,74470,74468,74466,74464,74462,74460,74458,74456,74454,74452,74450,74448,74438,74436,74434,74432,74430,74428,74426,74424,74422,74420,74418,74416,74414,74412,74410,74408,74406,74404,74402,74400,74398,74396,74394,74392,74390,74388,74386,74384,74382,74380,74378,74376,74374,74372,74370,74368,74366,74364,74362,74360,74358,74356,74354,74352,74350,74348,74346,74344,74342,74340,74338,74336,74334,74332,74330,74328,74326,74320,74318,74316,74314,74312,74310,74308,74306,74304,74302,74300,74298,74296,74294,74292,74290,74288,74286,74284,74282,74280,74278,74276,74274,74270,74268,74266,74264,74262,74260,74258,74240,74238,74236,74234,74232,74230,74228,74226,74224,74222,74220,74218,74216,74214,74212,74210,74208,74206,74204,74202,74200,74198,74196,74194,74192,74190,74188,74186,74184,74182,74180,74178,74176,74174,74172,74170,74168,74166,74164,74162,74160,74158,74156,74154,74152,74150,74148,74146,74144,74142,74140,74138,74136,74134,74132,74130,74128,74126,74124,74122,74120,74118,74116,74114,74112,74110,74108,74106,74104,74102,74100,74098,74096,74094,74092,74090,74088,74086,74084,74082,74080,74078,74076,74074,74072,74070,74068,74066,74064,74062,74060,74058,74056,74054,74052,74050,74048,74046,74044,74042,74040,74038,74036,74034,74032,74030,74028,74026,74024,74022,74020,74018,74016,74014,74012,74010,74473,74008,74006,74004,74002,74000,73998,73996,73994,73992,73990,73988,73986,73984,73982,73980,73978,73976,73974,73972,73970,73968,73966,73964,73962,73960,73958,73956,73954,73952,73950,73948,73946,73944,73942,73940,73938,73936,73934,73932,73930,73928,73926,73924,73922,73920,73918,73916,73914,73912,73910,73908,73906,73904,73902,73900,73898,73896,73894,73892,73890,73888,73886,73884,73882,73880,73878,73876,73874,73872,73870,73868,73866,73864,73862,73860,73858,73856,73854,73852,73850,73848,73846,73844,73842,73840,73838,73836,73834,73832,73830,73828,73826,73824,73822,73820,73818,73816,73814,73812,73810,73808,73806,73804,73802,73800,73798,73796,73792,73790,73788,73786,73784,73782,73780,73778,73776,73774,73772,73770,73768,73766,73764,73762,73760,73758,73756,73754,73752,73750,73748,73746,73744,73742,73740,73738,73736,73734,73732,73730,73728,73726,73724,73722,73720,73718,73716,73714,73712,73710,73708,73706,73704,73702,73700,73698,73696,73694,73692,73690,73688,73686,73684,73682,73680,73678,73676,73674,73672,73670,73668,73666,73664,73662,73660,73658,73656,73654,73652,73650,73648,73646,73644,73642,73640,73636,73634,73632,73630,73628,73626,73624,73622,73620,73618,73616,73614,73612,73610,73608,73606,73604,73602,73600,73598,73596,73594,73592,73590,73588,73586,73584,73582,73580,73578,73576,74645,73574,73572,73570,73568,73566,73564,73562,73560,73558,73556,73554,73552,73550,73548,73546,73544,73542,73540,73538,73536,73534,73532,73530,73528,73526,73524,73522,73520,73518,73516,73514,73512,73510,73508,73506,73504,73502,73500,73498,73496,73494,73492,73490,73488,73486,73484,73482,73480,73478,73476,73474,73472,73470,73468,73466,73464,73462,73460,73458,73456,73454,73452,73450,73448,73446,73444,73442,73440,73438,73436,73434,73432,73430,73428,73426,73424,73422,73420,73418,73416,73414,73412,73410,73408,73406,73404,73402,73400,73398,73396,73394,73392,73390,73388,73386,73384,73382,73380,73378,73376,73374,73372,73370,73368,73366,73364,73362,73360,73358,73356,73354,73352,73350,73348,73346,73344,73342,73340,73338,73336,73334,73332,73330,73328,73326,73324,73322,73320,73318,73316,73314,73312,73310,73308,73306,73304,73302,73300,73298,73296,73294,73292,73290,73288,73286,73284,73282,73280,73278,73276,73274,73272,73270,73268,73266,73264,73262,73260,73258,73256,73254,73252,73250,73248,73246,73244,73242,74324,74272,74256,74254,74252,74250,74248,74246,74244,74242,73229,73209,73231,73211,73233,73213,73235,73215,73237,73217,73239,73219,73221,73223,73225,73227,73207,73187,73189,73169,73191,73171,73193,73173,73195,73175,73197,73177,73199,73179,73201,73181,73203,73183,73205,73185,73144,73166,73146,73167,73148,73150,73130,73152,73132,73154,73134,73156,73136,73158,73138,73160,73140,73162,73142,73164,73102,73124,73104,73126,73106,73128,73108,73110,73090,73112,73092,73114,73094,73116,73096,73118,73098,73120,73100,73122,73080,73060,73082,73062,73084,73064,73086,73066,73088,73068,73070,73050,73072,73052,73074,73054,73076,73056,73078,73058,73016,73038,73018,73040,73020,73042,73022,73044,73024,73046,73026,73048,73028,73030,73010,73032,73012,73034,73014,73036,72975,72996,72977,72998,72979,73000,72981,73002,72983,73004,72985,73006,72986,73008,72988,72990,72971,72992,72973,72994,72953,72933,72955,72935,72957,72937,72959,72939,72961,72941,72963,72943,72965,72945,72967,72947,72969,72949,72951,72931,72911,72891,72913,72893,72915,72895,72917,72897,72919,72899,72921,72901,72923,72903,72925,72905,72927,72907,72929,72909,72889,72870,72872,72852,72874,72854,72876,72856,72878,72858,72880,72860,72882,72862,72884,72864,72886,72866,72888,72868,72826,72848,72828,72850,72830,72832,72812,72834,72814,72836,72816,72838,72818,72840,72820,72842,72822,72844,72824,72846,72784,72806,72786,72808,72788,72810,72790,72792,72772,72794,72774,72796,72776,72798,72778,72800,72780,72802,72782,72804,72762,72742,72764,72744,72766,72746,72768,72748,72770,72750,72752,72732,72754,72734,72756,72736,72758,72738,72760,72740,72698,72720,72700,72722,72702,72724,72704,72726,72706,72728,72708,72730,72710,72712,72692,72714,72694,72716,72696,72718,72656,72678,72658,72680,72660,72682,72662,72684,72664,72686,72666,72688,72668,72690,72670,72672,72652,72674,72654,72676,72634,72614,72636,72616,72638,72618,72640,72620,72642,72622,72644,72624,72646,72626,72648,72628,72650,72630,72632,72612,72592,72572,72594,72574,72596,72576,72598,72578,72600,72580,72602,72582,72604,72584,72606,72586,72608,72588,72610,72590,72570,72550,72552,72533,72554,72534,72556,72536,72558,72538,72560,72540,72562,72542,72564,72544,72566,72546,72568,72548,72508,72529,72510,72531,72511,72513,72494,72515,72496,72517,72498,72519,72500,72521,72502,72523,72504,72525,72506,72527,72466,72488,72468,72490,72470,72492,72472,72474,72455,72476,72456,72478,72458,72480,72460,72482,72462,72484,72464,72486,72447,72449,72451,72453,72445,72437,72439,72441,72443,72429,72431,72433,72435,72427,72425,72417,72419,72421,72423,72407,72409,72411,72413,72415,72403,72405,72397,72399,72401,72387,72389,72391,72393,72395,72381,72383,72385,72377,72379,72367,72369,72371,72373,72375,72361,72363,72365,72357,72359,72347,72349,72351,72353,72355,72339,72341,72343,72345,72337,72326,72328,72330,72332,72334,72315,72317,72319,72322,72324,72305,72307,72309,72311,72313,72295,72297,72299,72301,72303,72285,72287,72289,72291,72293,72275,72277,72279,72281,72283,72273,72265,72267,72269,72271,72255,72257,72259,72261,72263,72251,72253,72245,72247,72249,72235,72237,72239,72241,72243,72231,72233,72225,72227,72229,72217,72219,72221,72223,72215,72209,72211,72213,72205,72207,72195,72197,72199,72201,72203,72187,72189,72191,72193,72185,72175,72177,72179,72181,72183,72167,72169,72171,72173,72165,72155,72157,72159,72161,72163,72145,72147,72149,72151,72153,72135,72137,72139,72141,72143,72125,72127,72129,72131,72133,72123,72115,72117,72119,72121,72105,72107,72109,72111,72113,72103,72095,72097,72099,72101,72086,72087,72089,72091,72093,72084,72085,72081,72082,72077,72076,72074,72079,72083,72053,72031,72041,72064,72066,72030,72068,72033,72036,72043,72045,72058,72025,72013,71979,71985,71991,71997,71974,72018,71959,71993,71965,71967,72003,72005,71975,72008,71977,72012,71987,72015,71952,71957,71969,71946,71927,71932,71937,71941,71894,71926,71955,71899,71901,71929,71904,71907,71909,71939,71911,71914,71915,71947,71917,71949,71920,71861,71866,71872,71879,71857,71867,71869,71839,71842,71875,71845,71847,71892,71849,71855,71832,71837,71813,71803,71780,71787,71821,71789,71827,71793,71829,71795,71798,71801,71774,71805,71775,71809,71777,71811,71767,71720,71740,71743,71748,71752,71765,71693,71695,71769,71703,71712,71713,71635,71652,71583,71604,71613,71623,71576,71582,71639,71645,71587,71649,71591,71601,71559,71562,71620,71567,71571,71625,71539,71547,71513,71503,71507,71530,71535,71468,71471,71481,71498,71459,71466,71491,71441,71424,71429,71377,71380,71453,71385,71389,71392,71397,71402,71409,71417,71375,71350,71359,71367,71372,71330,71337,71315,71322,71325,71284,71327,71289,71332,71294,71306,71345,71310,71349,71313,71320,71285,71250,71259,71267,71233,71193,71245,71196,71248,71201,71205,71253,71210,71257,71265,71230,71235,71270,71240,71274,71279,71211,71217,71190,71146,71173,71180,71110,71114,71151,71115,71156,71119,71159,71129,71163,71132,71136,71137,71183,71141,71188,71144,71107,71149,71096,71046,71061,71049,71068,71073,71076,71081,71029,71092,71032,71037,71102,71044,71020,71027,70964,70973,70981,71005,70943,71008,71012,70948,71017,70958,70961,70930,70935,70984,70939,70994,70941,70949,70923,70892,70899,70907,70877,70886,70851,70894,70856,70859,70867,70911,70871,70921,70876,70926,70884,70839,70842,70889,70847,70770,70778,70784,70763,70722,70728,70742,70725,70775,70743,70747,70755,70786,70758,70790,70796,70800,70762,70693,70700,70708,70654,70679,70711,70662,70666,70672,70620,70676,70681,70628,70634,70639,70652,70611,70618,70623,70630,70603,70606,70539,70615,70575,70577,70583,70593,70597,70601,70566,70507,70503,70447,70451,70459,70473,70477,70481,70485,70499,70455,70439,70410,70360,70378,70385,70389,70392,70406,70424,70322,70334,70314,70298,70271,70301,70272,70305,70338,70274,70307,70279,70311,70280,70316,70283,70321,70287,70325,70290,70328,70292,70333,70296,70217,70191,70199,70207,70183,70190,70195,70221,70226,70229,70198,70232,70236,70202,70238,70241,70177,70208,70245,70182,70212,70248,70186,70216,70251,70157,70163,70136,70171,70145,70096,70100,70127,70160,70131,70104,70135,70165,70170,70110,70139,70112,70142,70174,70117,70147,70120,70151,70123,70156,70126,70102,70108,70118,70092,70050,70058,70068,70078,70086,70028,70075,70034,70080,70038,70085,70042,70089,70047,70052,70010,70055,70012,70060,70018,70064,70021,70067,70026,70072,70016,70023,70032,70043,70006,69980,69989,69962,69998,69972,70005,69944,69974,69946,69979,69949,69923,69953,69984,69924,69954,69987,69926,69958,69931,69963,69992,69932,69996,69935,69966,69939,69970,70000,69940,69864,69873,69881,69847,69854,69841,69889,69845,69892,69850,69896,69855,69899,69859,69902,69862,69905,69867,69908,69871,69911,69876,69880,69838,69885,69809,69817,69825,69801,69835,69763,69771,69777,69785,69791,69749,69811,69753,69816,69757,69820,69762,69766,69794,69826,69770,69797,69829,69775,69834,69780,69803,69784,69806,69789,69754,69716,69725,69735,69743,69671,69679,69689,69696,69705,69740,69697,69745,69701,69707,69662,69711,69665,69715,69669,69719,69674,69724,69678,69728,69683,69731,69688,69737,69692,69623,69661,69632,69640,69650,69622,69653,69590,69656,69595,69626,69596,69631,69600,69604,69635,69575,69606,69639,69576,69608,69579,69613,69644,69583,69614,69649,69585,69618,69588,69506,69539,69511,69543

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2015-09-07 14:38 UTC] cmb@php.net
-Status: Open +Status: Feedback
 [2015-09-07 14:38 UTC] cmb@php.net
Thank you for this bug report. To properly diagnose the problem, we
need a short but complete example script to be able to reproduce
this bug ourselves. 

A proper reproducing script starts with <?php and ends with ?>,
is max. 10-20 lines long and does not require any external 
resources such as databases, etc. If the script requires a 
database to demonstrate the issue, please make sure it creates 
all necessary tables, stored procedures etc.

Please avoid embedding huge scripts into the report.

It seems that your test script has been truncated.
 [2015-09-07 15:05 UTC] me at ninosego dot de
-Status: Feedback +Status: Open
 [2015-09-07 15:05 UTC] me at ninosego dot de
Oh I'm sorry. You can find the benchmark test-script unter following url:
http://pastebin.com/56PuymQi
 [2015-09-07 17:24 UTC] bwoebi@php.net
Just a quick note that it's doing comparison to the usual "weak comparison (==)" rules. Which needs us to do a very slow O(n^2) comparison (comparing each element against the other).
No wonder that it will be trivially sped out by going via array key access.

Hence the only way to get comparable performance is using array_intersect_key which can do it that way.

If we had array_intersect() with strict comparison, it'd surely be the fast solution of all, but that's not the case...

[fyi: the "array_fill_keys -> array_intersect_key -> sizeof" case got at least as fast as "array_fill_keys -> foreach -> isset -> array add -> sizeof" in PHP 7.]
 [2015-09-12 12:51 UTC] me at ninosego dot de
Isn't it better in the array_intersect() function to use array_intersect_key() if possible (if the arrays are one-dimensional)? This could be done with a check before the function is running its own slow comparison checks. So you would also boost the array_intersect() function.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Fri Apr 19 03:01:27 2024 UTC