#include<bits/stdc++.h>
#define U using
#define N namespace
#define S std
U N S;
int heshu[2065]={0,341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,4371,4681,
	5461,6601,7957,8321,8481,8911,10261,10585,11305,12801,13741,13747,13981,14491,15709,15841,16705,18705,18721,
	19951,23001,23377,25761,29341,30121,30889,31417,31609,31621,33153,34945,35333,39865,41041,41665,42799,46657,49141,
	49981,52633,55245,57421,60701,60787,62745,63973,65077,65281,68101,72885,74665,75361,80581,83333,83665,85489,87249,
	88357,88561,90751,91001,93961,101101,104653,107185,113201,115921,121465,123251,126217,129889,129921,130561
	,137149,149281,150851,154101,157641,158369,161038,162193,162401,164737,172081,176149,181901,188057
	,188461,194221,196021,196093,204001,206601,208465,212421,215265,215326,215749,219781,220729
	,223345,226801,228241,233017,241001,249841,252601,253241,256999,258511,264773,266305,271951,
	272251,275887,276013,278545,280601,282133,284581,285541,289941,294271,294409,314821,318361,
	323713,332949,334153,340561,341497,348161,357761,367081,387731,390937,396271,399001,401401,
	410041,422659,423793,427233,435671,443719,448921,449065,451905,452051,458989,464185,476971,
	481573,486737,488881,489997,493697,493885,512461,513629,514447,526593,530881,534061,552721,
	556169,563473,574561,574861,580337,582289,587861,588745,604117,611701,617093,622909,625921,
	635401,642001,647089,653333,656601,657901,658801,665281,665333,665401,670033,672487,679729,
	680627,683761,688213,710533,711361,721801,722201,722261,729061,738541,741751,742813,743665,
	745889,748657,757945,769567,769757,786961,800605,818201,825265,831405,838201,838861,841681,
	847261,852481,852841,873181,875161,877099,898705,915981,916327,934021,950797,976873,983401,
	997633,1004653,1016801,1018921,1023121,1024651,1033669,1050985,1052503,1052929,1053761,
	1064053,1073021,1082401,1082809,1092547,1093417,1104349,1106785,1109461,1128121,1132657,
	1139281,1141141,1145257,1152271,1157689,1168513,1193221,1194649,1207361,1246785,1251949,
	1252697,1275681,1277179,1293337,1302451,1306801,1325843,1333333,1357441,1357621,1373653,
	1394185,1397419,1398101,1419607,1433407,1441091,1457773,1459927,1461241,1463749,1472065,
	1472353,1472505,1485177,1489665,1493857,1500661,1507561,1507963,1509709,1520905,1529185,
	1530787,1533601,1533961,1534541,1537381,1549411,1569457,1579249,1584133,1608465,1615681,
	1620385,1643665,1678541,1690501,1711381,1719601,1730977,1735841,1746289,1755001,1773289,
	1801969,1809697,1811573,1815465,1826203,1827001,1830985,1837381,1839817,1840357,1857241,
	1876393,1892185,1896961,1907851,1908985,1909001,1937881,1969417,1987021,1993537,1994689,
	2004403,2008597,2035153,2077545,2081713,2085301,2089297,2100901,2113665,2113921,2121301,
	2134277,2142141,2144521,2162721,2163001,2165801,2171401,2181961,2184571,2205967,2213121,
	2232865,2233441,2261953,2264369,2269093,2284453,2288661,2290641,2299081,2304167,2313697,
	2327041,2350141,2387797,2414001,2419385,2433601,2434651,2455921,2487941,2491637,2503501,
	2508013,2510569,2513841,2528921,2531845,2537641,2568226,2603381,2609581,2615977,2617451,
	2626177,2628073,2649029,2649361,2670361,2704801,2719981,2722681,2746477,2746589,2748023,
	2757241,2773981,2780731,2793351,2797921,2811271,2827801,2867221,2880361,2882265,2899801,2909197,2921161,2940337,
	2944261,2953711,2976487,2977217,2987167,3020361,3020626,3048841,3057601,3059101,3073357,3090091,3094273,3116107,
	3125281,3146221,3165961,3181465,3186821,3224065,3225601,3235699,3316951,3336319,3337849,3345773,3363121,3370641,3375041,
	3375487,3400013,3413533,3429037,3435565,3471071,3539101,3542533,3567481,3568661,3581761,3605429,3656449,3664585,3679201,3726541,
	3746289,3755521,3763801,3779185,3814357,3828001,3898129,3911197,3916261,3936691,3985921,4005001,4014361,4025905,4038673,4069297,4072729,4082653,4097791,
	4101637,4151869,4154161,4154977,4181921,4188889,4209661,4229601,4259905,4314967,4335241,4360621,4361389,4363261,4371445,4415251,4463641,4469471,4480477,
	4502485,4504501,4513841,4535805,4567837,4613665,4650049,4670029,4682833,4698001,4706821,4714201,4767841,4806061,4827613,4835209,4863127,4864501,4868701,4869313,
	4877641,4895065,4903921,4909177,4917331,4917781,4922413,4974971,4984001,5016191,5031181,5034601,5044033,5049001,5095177,5131589,5133201,5148001,5173169,5173601,5176153
	,5187637,5193721,5250421,5256091,5258701,5271841,5284333,5310721,5351537,5400489,5423713,5444489,5456881,5481451,5489121,5489641,5524693,5529745,5545145,5551201,5560809,
	5575501,5590621,5599765,5632705,5672041,5681809,5733649,5758273,5766001,5804821,5859031,5872361,5919187,5968261,5968873,5977153,6027193,6049681,6054985,6118141,6122551,6135585,
	6140161,6159301,6183601,6189121,6212361,6226193,6233977,6235345,6236257,6236473,6242685,6255341,6278533,6309901,6313681,6334351,6350941,6368689,6386993,6474691,6539527,6617929,6628385,6631549,
	6658669,6732817,6733693,6749021,6779137,6787327,6836233,6840001,6868261,6886321,6912079,6952037,6955541,6973057,6973063,6998881,7008001,7017193,7040001,7177105,7207201,7215481,7232321,7233265,7259161,
	7273267,7295851,7306261,7306561,7414333,7416289,7428421,7429117,7455709,7462001,7516153,7519441,7546981,7656721,7674967,7693401,7724305,7725901,7759937,7803769,7808593,7814401,7820201,7866046,7883731,
	7995169,8012845,8036033,8041345,8043841,8095447,8134561,8137585,8137633,8180461,8209657,8231653,8239477,8280229,8321671,8322945,8341201,8355841,8362201,8384513,8388607,8462233,8534233,8640661,8646121,8650951,8656705,8719309,8719921,8725753,8727391,8745277,8812273,
	8830801,8902741,8916251,8927101,8992201,9006401,9037729,9040013,9046297,9056501,9063105,9069229,9073513,9084223,9106141,9115426,9131401,9143821,9223401,9224391,9273547,9345541,9371251,9439201,9480461,9494101,9533701,9564169,9567673,9582145,9585541,9588151,9591661,
	9613297,9638785,9692453,9724177,9729301,9774181,9816465,9834781,9863461,9890881,9908921,9920401,9995671,10004681,10024561,10031653,10033777,10079521,10084177,10134601,10185841,10226161,10239985,10251473,10266001,10267951,10275685,10317601,10323769,10331141,10386241,
	10393201,10402237,10402561,10403641,10425511,10505701,10513261,10545991,10606681,10610063,10635751,10655905,10680265,10700761,10712857,10763653,10802017,10818505,10837321,10877581,10956673,10958221,10974385,10974881,11034365,11075857,11081459,11115037,11119105,11157721,
	11205601,11242465,11328409,11335501,11367137,11433301,11473885,11541307,11585293,11592397,11644921,11767861,11776465,11777599,11875821,11921001,11972017,12032021,12067705,12096613,12261061,12262321,12263131,12273769,12322133,12327121,12376813,12407011,12490201,12498061,
	12584251,12599233,12643381,12659989,12702145,12711007,12757361,12783811,12854437,12932989,12936763,12939121,12945745,12979765,13057787,13073941,13187665,13216141,13295281,13333441,13338371,13357981,13421773,13446253,13448593,13500313,13554781,13635289,13635649,13694761,
	13696033,13747361,13757653,13773061,13823601,13838569,13856417,13899565,13942081,13971841,13991647,13992265,13996951,14012797,14026897,14154337,14179537,14282143,14324473,14469841,14556081,14589901,14609401,14671801,14676481,14684209,14709241,14794081,14796289,14865121,
	14870801,14885697,14892153,14898631,14899751,14913991,14980411,15082901,15101893,15124969,15139199,15162941,15188557,15207361,15220951,15247621,15248773,15268501,15403285,15472441,15479777,15510041,15525241,15560461,15583153,15603391,15621409,15698431,15700301,15716041,
	15732721,15757741,15802681,15829633,15888313,15913261,15976747,15978007,16046641,16053193,16070429,16132321,16149169,16149601,16153633,16158331,16263105,16324001,16349477,16360381,16435747,16539601,16666651,16705021,16717061,16773121,16778881,16818877,16822081,16843009,
	16853077,16879501,16973393,16998961,17020201,17098369,17116837,17134043,17208601,17236801,17316001,17327773,17375249,17405537,17429861,17450569,17509501,17585969,17586361,17590957,17641207,17698241,17759681,17777191,17812081,17870561,17895697,18003349,18007345,18067501,18073817,
	18137505,18151861,18162001,18300241,18307381,18366937,18443701,18454921,18468901,18487267,18490381,18535177,
	18541441,18595801,18607009,18653353,18736381,18740971,18779761,18900973,18985627,19020191,19054933,19092921,19149571,19260865,19328653,19384289,19404139,19471033,19523505,19569265,19607561,19683001,
	19734157,19781763,19985269,20081953,20099017,20117467,20140129,20202481,20234341,20261251,20417311,20489239,20494401,20626165,20647621,20770621,20964961,20968501,21042001,21224401,21303343,21306157,21355951,
	21359521,21397381,21400481,21414169,21417991,21459361,21474181,21559741,21584305,21585313,21623659,21654533,21715681,21789901,21814417,21880801,21907009,22066201,22075579,22087477,22137809,22203181,22215961,
	22269745,22351249,22369621,22397497,22432201,22480381,22487101,22509691,22513457,22564081,22591301,22665505,22669501,22711873,22848541,22849481,22885129,22899097,22953673,23054601,23247901,23261713,23283037,
	23286781,23315977,23382529,23386441,23405341,23464033,23517985,23577497,23634181,23734901,23736385,23808721,23822329,23828017,23872213,23963869,23966011,24037021,24158641,24161905,24214051,24356377,24726773,24776557,
	24904153,24913681,24929281,25080101,25150501,25266745,25270105,25276421,25326001,25457833,25520833,25540291,25557121,25603201,25629913,25640641,25696133,25768261,25831585,25840081,25846913,25873381,25909453,25947959,26254801
	,26280073,26296401,26377921,26465089,26470501,26474581,26553241,26634301,26719701,26758057,26813221,26821601,26840269,26877421,26886817,26921089,26932081,26977001,27032545,27062101,27108397,27118601,27128201,27168337,27218269
	,27219697,27271151,27279409,27331921,27336673,27380831,27392041,27401401,27402481,27409541,27476641,27491237,27492581,27509653,27600001,27664033,27700609,27714961,27736345,27798461,27808463,27846721,27966709,27986421,28011001,
	28029001,28071121,28172629,28175001,28312921,28325881,28406953,28449961,28527049,28572961,28629613,28717483,28787185,29020321,29111881,29137021,29143633,29214541,29581501,29593159,29732221,29878381,30022129,30058381,30069721,
	30090817,30185569,30219757,30295141,30296761,30338593,30388753,30411201,30418957,30529693,30576151,30653245,30662497,30718441,30739969,30740417,30881551,30894307,30951181,30958201,30971161,30992401,30996001,31040833,31118221
	,31146661,31150351,31166803,31198693,31405501,31436123,31692805,31735621,31759121,31766983,31794241,31880577,32080651,32091781,32095057,32158621,32168117,32264029,32285041,32368609,32428045,32497921,32676481,32701297,32756581
	,32899201,32914441,33018985,33146717,33193117,33298337,33302401,33408145,33596641,33600533,33627301,33704101,33840397,33848311,33872593,33965261,34003061,34043101,34100821,34111441,34124641,34196401,34386121,34487601,34540801,
	34581457,34603041,34657141,34856167,34890481,34901461,34944001,35428141,35498467,35571601,35576599,35626501,35703361,35820937,35851037,35926801,35932441,35967921,35976721,36121345,36168265,36255451,36291193,36307981,36338653,
	36354449,36448387,36507801,36721021,36724591,36765901,36852481,36861901,36919681,36942157,36974341,36981601,37109467,37167361,37280881,37354465,37376509,37439201,37469701,37491301,37695505,37727341,37769887,37938901,37962541,
	37964809,37988497,38010307,38046817,38118763,38151361,38171953,38210323,38239741,38342071,38404501,38439523,38453151,38560861,38584801,38624041,38637361,38789913,38790753,38801089,38903287,38971661,39016741,39052333,39117439,
	39126313,39353665,39465091,39467377,39512773,39573073,39655153,39684157,39789841,40094341,40160737,40165093,40238797,40280065,40315441,40325041,40361197,40374901,40430401,40622401,40629601,40778989,40782589,40801861,40827473,40841821,
	40886241,40917241,40928701,40933705,40987201,41017681,41067665,41073241,41102601,41121433,41262073,41298985,41341321,41396921,41424801,41471521,41541241,41568101,41590297,41604109,41607721,41642681,41662297,41840809,41866001,41987111,
	42009217,42344609,42485119,42490801,42623017,42689305,42694279,42697873,42702661,42709591,42763501,42984589,42998901,43039501,43136821,43224397,43235641,43286881,43331401,43363601,43397551,43584481,43620409,43661257,43798457,43914949,
	44070841,44081101,44238481,44314129,44347381,44465221,44472001,44482901,44521301,44671001,44695211,44731051,44823241,44824501,44912701,44953441,44963029,45100177,45175201,45219329,45318561,45393601,45414433,45485881,45563027,
	45593065,45769645,45819541,45830161,45877861,45879941,45890209,46045117,46055851,46094401,46104697,46256489,46282405,46325029,46386589,46469809,46483633,46517857,46647745,46657181,46679761,46860001,46878601,47006785,47063611,47220367,47253781,47349373,47356171,47647117,47734141,47744209,47759041,
	47903701,47918581,47930023,47953621,48064021,48191653,48269761,48277081,48316321,48316969,48321001,48369727,48398065,48400753,48448661,48462301,48506581,48551161,48563089,48592393,48628801,48650641,48656869,49075417,49084321,49303801,49333201,49411801,49430305,49439237,49459801,49472281,49664207,
	49699666,50155733,50176477,50193793,50201089,50376019,50443201,50473501,50523661,51030601,51129781,51283501,51302353,51340807,51396865,51500521,51509161,51627817,51803821,51890545,52018341,52072021,52119289,52142221,52181407,52204237,52365457,52452905,52869601,53154337,53245921,53283169,53315605,
	53399449,53542147,53560801,53656021,53661945,53675623,53695721,53711113,53728921,53795521,54029741,54060721,54177949,54215161,54448153,54449431,54468001,54545821,54651961,54767881,54772381,55035001,55109401,55176097,55200181,55318957,55324801,55329985,55462177,55610837,55729957,55961065,56052361,
	56420033,56479897,56608201,56643181,56669041,56687821,56810137,57130161,57172501,57421219,57561085,57707209,57749185,57762433,58003213,58422409,58449847,58489201,58498105,58509977,58679941,58708761,58755877,58903741,59408497,59426221,59469697,59586241,59589973,59631211,59840537,59913157,59953741,
	59955331,59999011,60112885,60155201,60352921,60375745,60514129,60547831,60558841,60566431,60581401,60696661,60738257,60761701,60769051,60925879,60957361,60998653,61198921,61201009,61219789,61309333,61330291,61377109,61679905,61754941,61755751,61794709,61832377,62176661,62248649,62289541,62490901,
	62633371,62656985,62756641,63001801,63002501,63065281,63127681,63167743,63294553,63318169,63328469,63337393,63346999,63388033,63526519,63560685,63729073,63781901,63884521,63919801,64009261,64148717,64162693,64238021,64377991,64477249,64567405,64605041,64644385,64685545,64735897,64774081,64940041,
	65037817,65144501,65241793,65254393,65301013,65350801,65350821,65359477,65427701,65523781,65565457,65919745,66024901,66096253,66296401,66384121,66437841,66760471,66790057,66849091,66886417,66932851,66976273,66977281,67194401,67213801,67371265,67529437,67541761,67559383,67642513,67653433,67763803,
	67902031,67928221,67940449,67968385,67994641,68033801,68075177,68102641,68154001,68165761,68275873,68512867,68621701,68776561,68800501,68830021,68839597,68958681,69030901,69128641,69176647,69228967,69231061,69331969,69414301,69485281,69612061,69615793,69678307,69705529,69741001,69776785,69885649,
	69917371,70006021,70030501,70147561,70149631,70195501,70461331,70463489,70484065,70488001,70541099,70561921,70593931,70626301,70695769,70728121,70938429,71040561,71079661,71107681,71479765,71570017,71572957,71711839,71734417,71804161,72108421,72135505,72192021,72286501,72348409,72498253,72543547,
	72595951,72680431,72734041,72803809,72805981,72884701,72887585,73346365,73439185,73451665,73522051,73562833,73645001,73721341,73988641,74165065,74193769,74217487,74329399,74411131,74658629,74698345,74705401,74874869,74927161,74945953,75140137,75143251,75151441,75187669,75501793,75565873,75676861,
	75681541,75765313,75836905,75927853,76595761,76704433,76725091,76745101,76923461,76969621,77082545,77295961,77334769,77442905,77477401,77518981,77533123,77576401,77594653,77648941,77812153,77817979,77826001,77858221,78073801,78091201,78120001,78206917,78397705,78526729,78671651,78795181,78844801,
	78905989,78939089,79398901,79411201,79417801,79464533,79525261,79539197,79624621,79625701,79739713,79786523,79854409,79895401,80142761,80146909,80282161,80375707,80556337,80687881,80787421,80891009,80918281,80927821,81189433,81433591,81445585,81480601,81612105,81638401,81680941,81722145,81789301,
	81926461,81954133,82023649,82139471,82219801,82268033,82273201,82279741,82416101,82452061,82506439,82847001,82870517,82882753,82929001,82976181,82995421,83058481,83083001,83099521,83103329,83204801,83814151,83966401,84028407,84164033,84234745,84311569,84350561,84375761,84417985,84421081,84487457,
	84758389,84809521,84998503,85030921,85207669,85328717,85374577,85400701,85519337,85759147,85761481,85823401,85875361,86027329,86067241,86114117,86204977,86438857,86484269,86530621,86559045,86968981,86999837,87211573,87318001,87483241,87499651,87558127,87571121,87694261,88099339,88123141,88256449,
	88368853,88407361,88466521,88615801,88661861,88689601,88735921,88930463,89148417,89244901,89308771,89670001,89784581,89816545,89896717,89915365,89961421,90014653,90270613,90278161,90341197,90532141,90626185,90665789,90670861,90698401,90803429,91367431,91433281,91453705,91587289,91659283,92027001,
	92139433,
	92343745,92438581,92625121,92631001,92645437,92677273,92829781,92974921,93030145,93431521,93473953,93541537,93571633,93591721,93614521,93643201,93677761,93839201,93845161,93869665,93926197,93967105,94316401,94502701,94536001,94790401,95053249,95200561,95423329,95451361,95452781,96135601,96259681,
	96271681,
	96386865,96589585,96618397,96653985,96791881,96888641,96895441,96904081,96916279,96925921,97047301,97255801,97420141,97487785,97496449,97655933,97676723,97796953,97863529,97924217,98124481,98523877
	,98586541,98602381,98735209,98756281,99036001,99115297,99486889,99551881,99789673,99830641,99861985,99898801,99945007,99971821
};//2^p%p=2且p不为质数的数列
int zhishu[(int)1e7+10]={};//质数表,为了把已算出的质数记下来,更省时间
bool is(int n)
{
	//(要判断2^p%p等不等于2)
	if(n<4)
	{
		return n>1;
	}
	
	//二分查找heshu数组
	int l=1,r=2064;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(n==heshu[mid]) return false;
		else if(n>heshu[mid]) l=mid+1;
		else r=mid-1;
	}
	
	//快速幂
	int a=2,m=n,ans=1;
	while(m>0)
	{
		if(m%2) ans*=a,ans%=n;
		a*=a;a%=n;m/=2;
	}
	//判断
	return (ans%n)==(2%n);
}
int n,q,k,cnt=0,last=0;
signed main()
{
	scanf("%d%d",&n,&q);
	while(q--)
	{
		scanf("%d",&k);
		if(k<=cnt) printf("%d\n",zhishu[k]);//已经算出来,直接输出
		else
		{
			//没有算出来,算到k个质数为止
			while(cnt<k)
			{
				for(int i=last+1;;i++)
				{
					if(is(i))
					{
						zhishu[++cnt]=i;
						last=i;
						break;
					}
				}
			}
			printf("%d\n",last);
		}
	}
	return 0;
}

虽然用欧拉筛过了,但问一下这样超时在哪里？