luoguP1865

题面

给定一个m,和若干个l,r 若l或r 不属于[1,m]输出Crossing the line 否则,输出l到r之间有多少个质数

样例

样例输入:

2 5
1 3
2 6

样例输出

2
Crossing the line

解答

今天借这道题给大家介绍一下一种编程方法:面向储存的源码级轻量预处理编程 其实这道题很简单,数论什么的,我数学差,不会。我用的面向储存的源码级轻量预处理编程。这样的话时间非常短,只有80ms,并且内存只用了788KB,我看过提交记录,是最少的。以下是对它的定义

面向储存的源码级轻量预处理编程是一种在算法竞赛(competitive programming)中常用技巧(skill),它是一种基于预处理的思想尔演变出来的编程方法。要采用这种方法,首先可以把整个程序分为两部分:1.生成器(genernater) 2.结果程序(result)。我们通常使用生成器把一定的结果预处理出来,然后再把它结合到结果程序里面,这样可以很快的针对算法竞赛中的各种数据而采用最合适的策略。并且这种方法对使用者思维水平要求较低。但是它的缺点就是当生成器的运行时间过长或者结果过于繁杂会导致这种方法不适应。 ——沃·镃基德·百科

说白了就是打表

面向储存的源码级轻量预处理编程预处理出从1到kn的质数个数,类似于前缀和的样子。这样子呢,就可以把这道题做成分块的题,直接判断l和r在哪个区间内然后求出1-r的质数个数再减去1-l的质数个数就是答案。 以下是生成器代码:

# include <cstdio>
# include <iostream>
# include <fstream>
using namespace std;
int read(){
	int f = 1,x = 0;
	static char c = getchar();
	while(c<'0'||c>'9'){if(c=='-')f = -1;c = getchar();}
	while(c>='0'&&c<='9')x = (x<<1)+(x<<3)+c-'0';
	return f*x;
}
bool judge(int x){
	if(x==1)return false;
	for(int i = 2;i*i<=x;i++){
		if(x%i==0)return false;
	}
	return true;
}
const int block_length = 125;
int main(){
	ofstream out("data");//C++自带的流输出,不懂得可以查一下,推荐使用必应而不是百度
	int cnt = 0;
	int tot = 0;
	for(int i = 1;i<=1000000;i++){
		if(judge(i)){
			cnt++;
		}
		tot++;
		if(tot == block_length){
			out<<cnt<<',';
			tot = 0;
			printf("%.2lf\n",(double)i/(double)1000000);//输出处理进度 
		}
	}
	out.close();
	return 0;
}

然后我们可以做出一个预处理结果打表 把这个结果和结果程序有机结合在一起,于是我们就成功的使用面向储存的源码级轻量预处理编程
以下是AC代码:

# pragma GCC optimize("Ofast")
# include <fstream>
# include <stdlib.h>
# include <algorithm>
# include <cstdio>//打表程序
using namespace std;
inline int read(){
    char ch = getchar();
    int f = 1 ,x = 0;
    while(ch > '9' || ch < '0'){if(ch == '-')f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}
    return x * f;
}
int table[10000]= {30,53,74,95,114,132,150,168,188,204,220,239,257,272,287,303,319,334,351,367,381,401,416,430,445,457,476,489,507,522,536,550,566,582,597,610,624,639,652,669,685,697,708,725,739,757,773,783,798,812,831,842,855,869,885,900,912,927,938,950,968,982,994,1007,1022,1035,1048,1059,1073,1091,1106,1117,1130,1146,1159,1177,1188,1203,1218,1229,1242,1256,1272,1284,1295,1310,1322,1335,1348,1359,1373,1387,1398,1409,1423,1438,1452,1463,1476,1492,1508,1521,1532,1547,1561,1575,1586,1600,1610,1625,1638,1652,1663,1674,1684,1698,1711,1727,1742,1754,1766,1779,1796,1810,1821,1837,1848,1862,1876,1888,1899,1912,1922,1936,1945,1960,1974,1985,1996,2014,2026,2038,2048,2064,2076,2090,2105,2118,2129,2140,2149,2158,2170,2183,2192,2212,2225,2234,2248,2262,2276,2289,2302,2313,2324,2337,2347,2360,2374,2388,2397,2412,2429,2439,2454,2464,2480,2491,2504,2515,2527,2542,2554,2564,2581,2592,2606,2613,2628,2641,2655,2668,2686,2698,2706,2718,2728,2738,2749,2762,2773,2786,2799,2810,2822,2835,2847,2860,2872,2884,2897,2910,2918,2936,2947,2961,2974,2982,2993,3004,3014,3027,3042,3055,3069,3077,3087,3100,3116,3130,3144,3153,3164,3179,3190,3203,3214,3224,3236,3245,3258,3270,3282,3293,3302,3315,3330,3340,3352,3368,3380,3389,3401,3414,3424,3432,3447,3458,3474,3487,3502,3512,3524,3538,3551,3562,3574,3586,3603,3613,3628,3638,3645,3657,3674,3685,3698,3711,3722,3732,3745,3754,3767,3778,3793,3798,3811,3824,3836,3846,3859,3870,3882,3896,3909,3923,3935,3945,3958,3968,3985,3995,4005,4017,4025,4037,4050,4058,4068,4085,4096,4107,4119,4134,4146,4155,4167,4178,4192,4203,4214,4227,4235,4246,4257,4265,4280,4291,4302,4319,4328,4339,4354,4365,4376,4392,4403,4417,4429,4447,4455,4470,4483,4494,4505,4514,4522,4534,4545,4555,4566,4579,4593,4604,4615,4624,4638,4650,4662,4675,4683,4694,4707,4717,4728,4738,4752,4761,4771,4783,4794,4806,4817,4830,4843,4851,4861,4871,4884,4895,4909,4923,4934,4946,4956,4966,4976,4990,5002,5010,5027,5035,5050,5061,5073,5086,5096,5109,5121,5133,5147,5157,5169,5179,5191,5199,5211,5222,5230,5244,5255,5270,5283,5295,5308,5319,5329,5341,5352,5359,5372,5385,5394,5408,5420,5432,5442,5452,5465,5476,5487,5500,5510,5518,5531,5545,5559,5569,5579,5590,5602,5614,5624,5632,5643,5657,5671,5683,5695,5706,5714,5728,5741,5754,5766,5782,5792,5805,5818,5827,5836,5850,5863,5873,5885,5901,5909,5922,5932,5943,5949,5963,5979,5992,6001,6016,6026,6040,6048,6057,6069,6079,6091,6100,6110,6123,6133,6145,6155,6163,6174,6186,6198,6212,6221,6232,6243,6256,6265,6275,6286,6297,6308,6320,6329,6338,6350,6365,6378,6393,6406,6413,6424,6434,6443,6453,6463,6473,6482,6493,6507,6518,6529,6540,6554,6569,6580,6591,6602,6610,6619,6630,6642,6653,6663,6675,6686,6701,6710,6725,6738,6746,6760,6774,6783,6793,6800,6811,6821,6834,6842,6854,6864,6877,6885,6902,6906,6914,6926,6935,6949,6964,6973,6985,6997,7006,7016,7033,7041,7053,7068,7082,7091,7102,7113,7128,7140,7150,7162,7172,7181,7195,7203,7218,7229,7236,7247,7257,7270,7281,7291,7301,7311,7325,7336,7347,7361,7371,7384,7393,7402,7415,7426,7435,7450,7463,7473,7484,7494,7504,7514,7525,7536,7545,7558,7567,7577,7589,7602,7613,7629,7643,7653,7662,7671,7684,7694,7702,7715,7724,7735,7746,7753,7766,7778,7789,7800,7810,7825,7837,7844,7858,7870,7879,7888,7903,7915,7925,7941,7952,7964,7970,7982,7996,8005,8017,8028,8044,8054,8065,8078,8086,8097,8106,8118,8128,8137,8152,8162,8171,8181,8190,8199,8214,8222,8237,8245,8258,8269,8277,8290,8302,8311,8321,8333,8344,8355,8362,8372,8385,8400,8411,8421,8430,8441,8450,8461,8470,8482,8492,8507,8522,8531,8543,8552,8559,8567,8577,8584,8595,8610,8619,8635,8644,8653,8665,8679,8688,8701,8713,8728,8741,8750,8761,8771,8782,8791,8802,8810,8825,8835,8848,8857,8864,8877,8887,8897,8910,8921,8935,8944,8959,8974,8984,8994,9005,9018,9030,9040,9047,9055,9070,9082,9089,9101,9113,9127,9135,9148,9157,9170,9182,9193,9206,9218,9229,9240,9252,9260,9271,9282,9295,9303,9313,9326,9336,9345,9356,9364,9375,9389,9395,9408,9418,9427,9434,9445,9459,9468,9480,9490,9505,9516,9527,9537,9547,9559,9570,9582,9592,9600,9610,9621,9632,9645,9654,9663,9673,9685,9696,9708,9719,9732,9745,9755,9766,9781,9793,9804,9814,9826,9834,9844,9853,9865,9872,9879,9890,9902,9911,9920,9933,9946,9957,9966,9976,9987,10001,10013,10024,10031,10040,10054,10064,10077,10086,10094,10106,10115,10125,10141,10151,10159,10174,10187,10198,10210,10218,10228,10234,10242,10253,10264,10274,10285,10299,10308,10319,10328,10337,10348,10365,10375,10386,10397,10409,10423,10430,10443,10453,10462,10468,10479,10487,10503,10512,10521,10536,10546,10555,10566,10576,10586,10595,10611,10620,10630,10643,10657,10662,10674,10680,10689,10701,10717,10733,10742,10750,10759,10767,10777,10789,10800,10811,10821,10830,10839,10851,10863,10871,10882,10893,10906,10913,10924,10933,10952,10964,10973,10983,10993,11004,11012,11023,11032,11045,11055,11066,11078,11086,11097,11108,11121,11135,11143,11154,11163,11174,11183,11194,11204,11214,11226,11237,11246,11252,11263,11277,11290,11301,11313,11323,11331,11339,11351,11364,11376,11389,11400,11408,11424,11434,11448,11457,11463,11475,11488,11499,11510,11522,11534,11542,11554,11563,11574,11583,11591,11606,11617,11630,11640,11651,11658,11671,11684,11693,11701,11712,11725,11734,11745,11756,11766,11776,11785,11800,11808,11818,11831,11843,11853,11865,11873,11884,11894,11901,11909,11920,11932,11940,11951,11968,11979,11987,11995,12006,12017,12032,12042,12053,12063,12076,12088,12097,12107,12120,12132,12142,12149,12159,12171,12180,12193,12205,12215,12227,12238,12244,12254,12263,12274,12285,12294,12306,12316,12327,12336,12346,12358,12367,12379,12393,12403,12414,12426,12434,12447,12458,12465,12478,12487,12496,12506,12517,12532,12539,12548,12557,12567,12576,12587,12597,12609,12623,12636,12648,12656,12665,12675,12686,12699,12713,12727,12737,12747,12761,12767,12779,12790,12802,12811,12821,12831,12841,12851,12863,12873,12885,12897,12907,12916,12926,12934,12941,12955,12967,12977,12988,12997,13010,13017,13029,13039,13051,13062,13075,13088,13097,13106,13117,13129,13138,13148,13162,13175,13184,13196,13208,13214,13222,13237,13243,13255,13266,13272,13280,13289,13299,13313,13324,13334,13343,13350,13360,13370,13382,13392,13401,13411,13422,13433,13440,13449,13462,13474,13485,13496,13507,13520,13530,13540,13549,13560,13570,13580,13591,13600,13611,13623,13634,13645,13656,13668,13674,13682,13695,13702,13713,13722,13735,13746,13757,13772,13782,13793,13806,13818,13827,13838,13848,13860,13873,13880,13891,13904,13910,13919,13933,13942,13955,13964,13976,13990,14003,14014,14023,14036,14046,14052,14065,14076,14085,14099,14111,14120,14125,14138,14150,14162,14171,14176,14188,14200,14211,14223,14231,14242,14252,14263,14272,14282,14293,14302,14313,14326,14341,14353,14357,14367,14376,14387,14394,14403,14417,14424,14433,14444,14459,14473,14482,14490,14501,14511,14521,14529,14540,14551,14558,14572,14580,14590,14598,14607,14619,14627,14639,14650,14662,14677,14683,14696,14706,14714,14724,14733,14747,14758,14768,14779,14788,14798,14806,14819,14829,14840,14852,14861,14865,14875,14885,14897,14911,14922,14933,14941,14954,14963,14974,14982,14993,15005,15016,15026,15037,15048,15059,15069,15078,15086,15093,15103,15112,15121,15132,15146,15157,15164,15173,15181,15191,15202,15211,15221,15233,15246,15254,15271,15280,15289,15302,15310,15319,15328,15337,15347,15355,15365,15375,15383,15394,15401,15410,15422,15433,15445,15453,15461,15473,15485,15497,15508,15520,15533,15542,15551,15562,15576,15584,15595,15603,15612,15623,15632,15645,15657,15665,15675,15688,15700,15709,15722,15734,15745,15754,15762,15773,15783,15789,15798,15812,15823,15833,15846,15854,15866,15877,15885,15896,15905,15916,15925,15929,15939,15950,15956,15967,15979,15991,16003,16016,16028,16040,16055,16064,16075,16086,16095,16104,16112,16124,16131,16137,16146,16159,16169,16180,16190,16201,16215,16222,16235,16248,16260,16269,16279,16293,16305,16318,16327,16342,16351,16361,16374,16383,16393,16400,16409,16413,16423,16433,16441,16450,16460,16469,16480,16492,16506,16518,16526,16537,16549,16561,16571,16583,16592,16597,16611,16624,16636,16644,16651,16662,16674,16684,16695,16703,16713,16726,16734,16745,16756,16768,16779,16786,16799,16812,16824,16836,16849,16860,16869,16879,16886,16899,16909,16915,16927,16943,16952,16964,16971,16982,16990,17002,17007,17016,17029,17040,17048,17059,17072,17082,17089,17099,17110,17125,17137,17147,17156,17170,17177,17184,17196,17201,17213,17223,17237,17245,17256,17266,17273,17284,17296,17308,17318,17326,17338,17348,17360,17369,17382,17391,17402,17415,17424,17435,17443,17455,17467,17474,17489,17499,17511,17518,17525,17532,17540,17553,17564,17573,17584,17595,17607,17618,17625,17635,17644,17658,17668,17678,17686,17694,17705,17716,17726,17734,17746,17755,17770,17778,17789,17799,17808,17821,17831,17840,17851,17864,17874,17883,17895,17907,17915,17922,17931,17944,17952,17963,17975,17984,17994,18005,18016,18025,18033,18041,18050,18061,18071,18081,18088,18100,18110,18120,18134,18148,18159,18167,18176,18185,18193,18204,18213,18226,18233,18243,18255,18266,18273,18281,18293,18304,18313,18321,18333,18343,18355,18362,18372,18381,18391,18403,18411,18426,18437,18445,18452,18464,18476,18488,18500,18512,18521,18527,18535,18547,18557,18567,18579,18591,18604,18615,18624,18634,18645,18655,18666,18680,18690,18701,18707,18719,18726,18738,18752,18762,18774,18784,18796,18807,18817,18832,18843,18855,18862,18871,18882,18891,18901,18915,18926,18934,18943,18956,18965,18977,18984,18995,19000,19010,19018,19026,19036,19046,19055,19068,19080,19089,19099,19107,19115,19127,19139,19151,19158,19170,19180,19192,19205,19213,19218,19228,19238,19250,19258,19266,19277,19287,19296,19305,19314,19322,19331,19341,19353,19363,19373,19383,19397,19408,19416,19428,19435,19443,19454,19464,19469,19481,19493,19506,19517,19527,19540,19546,19556,19566,19578,19590,19604,19618,19625,19634,19645,19653,19664,19673,19684,19696,19706,19717,19724,19736,19746,19759,19767,19776,19788,19798,19810,19818,19827,19834,19845,19857,19868,19879,19893,19903,19911,19919,19930,19937,19947,19959,19971,19980,19990,20001,20008,20020,20029,20041,20054,20062,20074,20083,20094,20104,20113,20124,20131,20142,20151,20161,20173,20180,20188,20200,20208,20222,20236,20248,20254,20260,20268,20278,20290,20301,20316,20324,20336,20349,20355,20370,20379,20389,20401,20413,20428,20437,20449,20459,20472,20482,20491,20499,20512,20521,20531,20536,20549,20560,20573,20580,20590,20599,20611,20618,20625,20637,20646,20655,20666,20675,20681,20691,20704,20711,20720,20730,20735,20746,20754,20768,20780,20788,20799,20810,20822,20833,20845,20854,20861,20868,20880,20887,20896,20906,20915,20923,20931,20942,20950,20963,20971,20982,20991,21002,21014,21019,21026,21036,21044,21055,21067,21081,21093,21103,21109,21122,21131,21142,21150,21160,21169,21179,21192,21201,21212,21221,21234,21242,21254,21261,21271,21282,21291,21301,21312,21320,21334,21343,21355,21366,21378,21392,21400,21409,21417,21430,21439,21451,21461,21468,21477,21488,21494,21506,21518,21527,21538,21545,21554,21565,21577,21591,21602,21614,21625,21633,21641,21649,21659,21669,21681,21693,21702,21713,21720,21733,21744,21750,21762,21773,21784,21797,21805,21813,21822,21831,21844,21854,21865,21876,21888,21899,21910,21920,21931,21942,21955,21964,21972,21983,21991,22004,22015,22024,22035,22044,22057,22061,22069,22077,22081,22092,22106,22115,22126,22140,22150,22162,22175,22182,22191,22203,22210,22222,22232,22243,22252,22260,22268,22281,22288,22295,22303,22314,22326,22337,22350,22362,22372,22381,22388,22398,22403,22413,22425,22438,22450,22464,22472,22482,22492,22503,22513,22525,22535,22546,22554,22564,22573,22581,22588,22597,22606,22615,22627,22638,22645,22656,22665,22675,22685,22695,22706,22718,22730,22743,22751,22761,22768,22780,22785,22796,22806,22818,22829,22837,22846,22856,22862,22874,22884,22893,22904,22914,22925,22931,22940,22950,22961,22971,22979,22987,22997,23008,23019,23027,23038,23052,23057,23066,23077,23087,23096,23107,23121,23128,23139,23150,23161,23170,23182,23188,23197,23206,23218,23230,23239,23251,23259,23270,23283,23290,23302,23308,23324,23332,23343,23353,23358,23371,23380,23395,23399,23412,23422,23437,23451,23468,23478,23489,23497,23505,23512,23517,23528,23536,23551,23564,23573,23586,23594,23606,23617,23627,23632,23642,23651,23664,23675,23684,23697,23708,23717,23726,23736,23746,23757,23766,23775,23783,23795,23804,23812,23824,23839,23849,23859,23866,23874,23887,23898,23906,23918,23921,23930,23939,23946,23958,23969,23981,23990,23998,24004,24014,24029,24038,24046,24057,24067,24079,24091,24101,24107,24121,24133,24143,24155,24164,24175,24182,24194,24204,24213,24223,24233,24240,24250,24260,24269,24278,24288,24299,24307,24316,24329,24339,24350,24359,24368,24378,24384,24393,24406,24415,24424,24432,24443,24454,24464,24470,24484,24494,24504,24519,24526,24537,24549,24554,24567,24579,24593,24604,24615,24623,24631,24644,24651,24661,24671,24681,24693,24702,24707,24714,24726,24734,24747,24753,24763,24777,24785,24796,24808,24824,24835,24843,24854,24862,24870,24879,24890,24903,24913,24920,24929,24935,24940,24955,24966,24975,24986,24991,25000,25012,25024,25030,25038,25046,25057,25062,25070,25080,25089,25100,25108,25118,25128,25139,25152,25166,25177,25187,25195,25204,25215,25224,25237,25248,25254,25266,25278,25289,25299,25308,25319,25327,25340,25348,25357,25367,25376,25385,25394,25404,25413,25424,25432,25444,25455,25463,25471,25481,25490,25499,25505,25516,25524,25531,25540,25554,25567,25577,25582,25590,25604,25616,25626,25634,25644,25652,25660,25665,25679,25691,25700,25710,25720,25727,25739,25752,25763,25773,25782,25789,25796,25807,25818,25826,25835,25846,25855,25867,25877,25884,25892,25903,25914,25919,25930,25938,25949,25959,25969,25980,25986,25997,26005,26017,26027,26038,26046,26060,26071,26082,26090,26103,26111,26123,26131,26141,26151,26165,26169,26178,26186,26193,26205,26212,26224,26237,26249,26255,26269,26281,26293,26305,26313,26321,26333,26342,26352,26364,26375,26384,26396,26409,26421,26429,26438,26453,26463,26471,26483,26489,26497,26508,26518,26530,26540,26550,26560,26571,26581,26590,26603,26611,26620,26631,26639,26644,26654,26662,26673,26681,26694,26701,26710,26720,26733,26741,26754,26764,26775,26784,26793,26800,26810,26820,26828,26838,26848,26860,26870,26879,26887,26896,26907,26913,26923,26935,26942,26948,26961,26971,26984,26992,27005,27015,27023,27034,27041,27053,27065,27071,27085,27097,27103,27120,27128,27140,27150,27159,27170,27179,27187,27196,27206,27213,27221,27233,27246,27256,27263,27273,27283,27295,27305,27315,27323,27334,27347,27357,27368,27375,27388,27398,27409,27420,27430,27441,27447,27460,27473,27482,27490,27503,27513,27522,27533,27544,27554,27568,27578,27589,27597,27608,27622,27632,27641,27651,27660,27670,27680,27687,27697,27708,27720,27729,27739,27748,27759,27767,27781,27791,27798,27806,27820,27828,27837,27848,27858,27866,27874,27884,27895,27902,27910,27919,27929,27940,27948,27962,27972,27982,27994,28006,28017,28029,28037,28047,28055,28068,28078,28091,28100,28110,28117,28123,28136,28147,28154,28164,28172,28181,28193,28207,28218,28228,28241,28250,28261,28268,28279,28287,28296,28304,28314,28323,28333,28342,28354,28362,28372,28385,28394,28404,28414,28427,28436,28445,28453,28466,28476,28484,28491,28504,28516,28522,28537,28544,28553,28566,28575,28586,28593,28605,28614,28621,28628,28638,28649,28657,28669,28682,28690,28701,28711,28719,28727,28737,28745,28756,28765,28776,28786,28796,28810,28819,28826,28836,28845,28857,28865,28873,28883,28895,28903,28910,28923,28933,28947,28957,28967,28974,28988,28995,29004,29015,29027,29037,29041,29055,29070,29082,29090,29098,29108,29114,29122,29133,29141,29146,29155,29166,29177,29182,29196,29203,29211,29222,29232,29241,29251,29266,29275,29283,29296,29303,29314,29324,29333,29343,29353,29364,29376,29386,29394,29402,29414,29420,29427,29438,29450,29459,29471,29480,29490,29500,29507,29522,29535,29542,29548,29557,29569,29580,29589,29597,29603,29612,29623,29637,29647,29656,29665,29675,29687,29700,29710,29721,29728,29736,29746,29761,29770,29775,29787,29795,29804,29818,29827,29837,29845,29859,29868,29876,29885,29895,29905,29914,29923,29937,29945,29952,29965,29977,29986,29994,29999,30010,30019,30031,30040,30051,30064,30071,30084,30095,30102,30112,30124,30132,30144,30152,30164,30178,30187,30194,30205,30214,30224,30233,30241,30251,30259,30271,30281,30290,30303,30311,30326,30338,30345,30356,30366,30377,30392,30397,30406,30414,30427,30436,30447,30456,30463,30472,30480,30488,30498,30505,30511,30523,30531,30541,30551,30557,30571,30585,30596,30603,30610,30620,30632,30642,30651,30663,30673,30686,30694,30705,30716,30726,30736,30745,30752,30757,30765,30775,30785,30792,30799,30803,30815,30825,30833,30842,30853,30864,30872,30882,30892,30904,30914,30925,30937,30948,30953,30963,30969,30980,30989,30998,31011,31022,31035,31041,31052,31064,31070,31080,31091,31102,31112,31122,31129,31141,31150,31160,31170,31182,31194,31203,31212,31218,31227,31242,31253,31265,31272,31282,31291,31303,31314,31325,31335,31341,31353,31364,31376,31382,31393,31404,31413,31420,31430,31439,31448,31454,31464,31473,31483,31489,31493,31502,31511,31522,31533,31544,31546,31560,31571,31579,31586,31592,31600,31612,31625,31634,31641,31649,31658,31668,31677,31685,31697,31708,31714,31726,31740,31749,31756,31770,31781,31789,31796,31804,31812,31822,31835,31844,31854,31861,31867,31880,31891,31904,31918,31929,31941,31950,31962,31971,31980,31989,31999,32009,32015,32023,32034,32045,32059,32069,32076,32085,32097,32103,32116,32124,32135,32140,32148,32160,32168,32176,32188,32197,32206,32217,32228,32237,32246,32257,32267,32279,32288,32300,32305,32316,32328,32338,32345,32352,32362,32372,32382,32390,32400,32412,32421,32432,32440,32448,32458,32464,32473,32479,32491,32502,32515,32522,32535,32542,32551,32559,32570,32580,32593,32603,32613,32623,32636,32646,32656,32664,32674,32681,32691,32702,32711,32721,32734,32742,32751,32761,32770,32783,32794,32804,32814,32826,32830,32839,32848,32858,32867,32874,32882,32893,32900,32908,32917,32928,32939,32948,32954,32963,32972,32983,32995,33005,33013,33021,33034,33044,33053,33067,33078,33087,33098,33113,33118,33129,33138,33148,33159,33170,33179,33189,33195,33206,33216,33227,33237,33249,33264,33273,33282,33290,33302,33313,33326,33337,33346,33355,33368,33382,33391,33400,33408,33418,33427,33433,33443,33456,33465,33475,33486,33496,33505,33515,33524,33534,33539,33547,33558,33567,33577,33585,33597,33608,33610,33622,33631,33640,33652,33660,33670,33678,33689,33697,33710,33719,33732,33743,33754,33762,33770,33779,33789,33801,33807,33820,33831,33841,33850,33860,33870,33880,33889,33898,33905,33915,33923,33930,33941,33949,33958,33965,33973,33982,33990,34001,34011,34019,34032,34038,34052,34056,34071,34077,34088,34096,34107,34113,34124,34133,34142,34152,34163,34172,34181,34194,34202,34206,34215,34222,34232,34242,34252,34262,34271,34284,34295,34305,34313,34319,34329,34336,34349,34359,34366,34372,34377,34389,34402,34409,34420,34432,34442,34453,34460,34473,34482,34495,34501,34513,34523,34532,34542,34548,34560,34571,34580,34589,34600,34614,34621,34631,34641,34653,34662,34673,34681,34687,34700,34709,34718,34727,34739,34752,34760,34768,34782,34795,34803,34811,34820,34828,34834,34842,34854,34865,34871,34877,34886,34895,34905,34911,34924,34933,34944,34955,34964,34979,34990,35001,35011,35022,35027,35036,35047,35060,35069,35081,35087,35097,35103,35119,35129,35134,35142,35148,35157,35169,35178,35188,35199,35210,35219,35230,35241,35250,35264,35272,35278,35287,35303,35315,35321,35331,35339,35352,35366,35372,35382,35390,35398,35404,35420,35430,35439,35446,35458,35465,35476,35485,35493,35505,35511,35526,35531,35538,35551,35561,35571,35578,35587,35594,35605,35615,35628,35637,35649,35661,35671,35678,35690,35698,35710,35722,35731,35739,35748,35757,35770,35779,35789,35796,35807,35818,35827,35832,35844,35853,35861,35869,35876,35884,35891,35903,35914,35924,35935,35944,35952,35965,35975,35981,35988,36002,36011,36023,36031,36037,36047,36058,36069,36073,36080,36091,36101,36113,36125,36138,36146,36162,36172,36175,36185,36192,36202,36212,36225,36238,36248,36257,36268,36277,36287,36295,36307,36317,36329,36340,36352,36363,36374,36384,36392,36401,36413,36422,36436,36444,36451,36464,36473,36481,36491,36501,36511,36523,36532,36540,36553,36566,36572,36584,36595,36604,36617,36628,36637,36648,36656,36664,36674,36683,36693,36704,36712,36721,36729,36739,36748,36756,36765,36776,36784,36791,36797,36806,36815,36825,36836,36845,36854,36866,36871,36879,36888,36898,36908,36918,36931,36941,36948,36959,36969,36978,36990,37001,37010,37020,37032,37041,37050,37057,37068,37075,37084,37092,37104,37118,37126,37135,37146,37153,37167,37177,37188,37203,37213,37223,37234,37242,37253,37265,37275,37284,37295,37305,37317,37325,37336,37347,37357,37364,37373,37380,37389,37398,37407,37415,37423,37432,37442,37452,37460,37465,37473,37483,37492,37503,37511,37521,37529,37537,37547,37556,37566,37578,37586,37591,37596,37606,37617,37626,37634,37647,37659,37668,37677,37687,37696,37706,37717,37728,37740,37753,37763,37771,37785,37798,37807,37814,37824,37831,37840,37852,37862,37874,37882,37892,37898,37904,37915,37922,37932,37937,37943,37956,37966,37971,37979,37991,37998,38009,38018,38029,38038,38045,38055,38063,38072,38083,38091,38101,38112,38126,38136,38146,38154,38165,38175,38182,38188,38197,38212,38221,38229,38238,38250,38259,38270,38280,38290,38300,38308,38315,38325,38333,38340,38347,38358,38368,38375,38390,38400,38408,38419,38429,38437,38445,38452,38458,38469,38479,38486,38495,38502,38512,38521,38535,38544,38552,38563,38573,38581,38590,38595,38604,38613,38620,38628,38640,38649,38663,38669,38678,38683,38693,38704,38713,38722,38733,38745,38755,38764,38775,38786,38796,38807,38814,38826,38840,38853,38863,38874,38881,38888,38897,38905,38914,38926,38934,38945,38950,38960,38969,38976,38983,38993,39002,39010,39021,39032,39048,39055,39066,39079,39089,39098,39107,39118,39131,39141,39151,39157,39167,39178,39185,39193,39203,39213,39223,39231,39244,39254,39267,39279,39290,39298,39310,39317,39327,39336,39345,39357,39369,39378,39388,39397,39407,39418,39426,39433,39444,39453,39461,39467,39478,39487,39499,39511,39519,39526,39539,39549,39559,39568,39579,39589,39597,39607,39619,39627,39636,39648,39659,39668,39679,39692,39705,39718,39727,39734,39743,39752,39763,39772,39780,39789,39795,39804,39810,39822,39829,39841,39849,39857,39868,39876,39891,39898,39910,39922,39934,39939,39951,39960,39970,39980,39984,39995,40005,40019,40026,40035,40046,40058,40065,40072,40082,40095,40108,40115,40123,40131,40141,40154,40160,40172,40180,40188,40198,40209,40223,40235,40242,40247,40259,40267,40278,40287,40296,40310,40317,40327,40337,40346,40356,40364,40370,40378,40382,40392,40400,40406,40415,40423,40431,40437,40445,40455,40465,40474,40485,40496,40508,40518,40527,40538,40546,40553,40568,40574,40586,40597,40605,40613,40627,40640,40649,40657,40671,40679,40688,40697,40707,40716,40727,40734,40744,40756,40766,40777,40787,40795,40804,40816,40824,40831,40844,40850,40859,40873,40881,40891,40903,40914,40920,40933,40934,40941,40953,40961,40972,40981,40987,40999,41014,41022,41031,41040,41050,41059,41069,41079,41086,41098,41107,41118,41133,41141,41149,41158,41168,41180,41191,41204,41213,41225,41236,41244,41251,41261,41273,41278,41286,41293,41304,41314,41321,41333,41342,41354,41366,41376,41385,41393,41399,41407,41418,41428,41437,41447,41457,41465,41478,41488,41497,41507,41523,41528,41538,41548,41560,41569,41579,41587,41597,41605,41617,41628,41642,41650,41658,41666,41674,41683,41691,41702,41709,41715,41723,41732,41742,41752,41758,41764,41775,41784,41794,41805,41811,41823,41834,41842,41853,41863,41871,41881,41888,41898,41910,41923,41933,41945,41954,41965,41976,41985,41993,41999,42006,42018,42027,42039,42049,42058,42069,42078,42086,42096,42104,42112,42121,42130,42140,42150,42159,42170,42178,42189,42195,42203,42216,42224,42231,42240,42248,42260,42273,42282,42291,42303,42314,42322,42331,42342,42347,42356,42363,42374,42387,42396,42407,42418,42426,42436,42445,42452,42457,42464,42470,42485,42495,42504,42515,42528,42536,42549,42558,42563,42576,42584,42592,42606,42616,42625,42632,42641,42653,42667,42673,42677,42686,42694,42699,42708,42719,42731,42739,42745,42759,42770,42782,42794,42804,42812,42824,42833,42846,42855,42868,42883,42892,42897,42907,42916,42930,42936,42946,42955,42964,42976,42983,42994,43002,43013,43021,43033,43042,43049,43061,43071,43076,43088,43098,43107,43117,43125,43134,43144,43154,43165,43175,43186,43196,43207,43217,43226,43237,43247,43256,43264,43276,43287,43296,43303,43309,43316,43326,43336,43347,43356,43365,43376,43386,43396,43403,43410,43418,43427,43442,43448,43461,43469,43482,43491,43502,43510,43521,43532,43542,43550,43561,43570,43585,43595,43605,43613,43623,43631,43642,43651,43659,43667,43677,43685,43695,43702,43712,43718,43728,43737,43747,43759,43769,43779,43786,43795,43807,43815,43825,43833,43844,43856,43862,43875,43886,43898,43905,43913,43922,43933,43937,43947,43954,43965,43973,43981,43991,44002,44012,44024,44033,44045,44052,44062,44073,44084,44090,44096,44106,44113,44126,44139,44147,44157,44163,44172,44183,44190,44198,44206,44217,44224,44231,44240,44250,44259,44269,44279,44290,44300,44313,44322,44333,44345,44356,44367,44378,44386,44391,44398,44407,44416,44423,44433,44443,44454,44462,44474,44482,44494,44501,44511,44521,44533,44538,44545,44558,44566,44572,44578,44589,44600,44608,44621,44629,44640,44645,44652,44663,44673,44680,44694,44703,44713,44722,44735,44746,44754,44762,44773,44780,44789,44800,44806,44820,44833,44839,44849,44858,44871,44881,44891,44899,44905,44912,44919,44928,44937,44949,44958,44967,44972,44981,44992,45001,45009,45018,45030,45040,45052,45056,45066,45077,45082,45091,45100,45108,45118,45129,45140,45150,45161,45167,45176,45185,45193,45203,45214,45223,45236,45244,45255,45266,45273,45281,45294,45308,45314,45322,45331,45342,45350,45359,45368,45380,45391,45401,45412,45420,45428,45436,45446,45458,45467,45476,45488,45495,45503,45512,45520,45528,45539,45547,45559,45569,45576,45585,45598,45609,45618,45627,45636,45646,45653,45661,45668,45680,45694,45704,45715,45719,45730,45738,45743,45753,45761,45765,45776,45783,45797,45804,45815,45827,45843,45853,45863,45867,45878,45885,45894,45905,45915,45921,45931,45940,45947,45959,45969,45976,45986,45995,46003,46014,46023,46029,46042,46054,46063,46072,46085,46101,46109,46119,46128,46137,46149,46158,46170,46176,46185,46191,46198,46202,46209,46219,46225,46232,46247,46257,46268,46281,46290,46302,46315,46322,46328,46338,46347,46352,46360,46369,46378,46388,46402,46414,46419,46428,46434,46446,46453,46463,46474,46487,46501,46507,46514,46524,46532,46543,46547,46557,46567,46580,46587,46596,46606,46611,46617,46629,46635,46645,46656,46668,46676,46690,46697,46706,46712,46721,46728,46739,46751,46763,46770,46778,46788,46798,46811,46819,46834,46843,46847,46862,46873,46886,46894,46904,46913,46923,46931,46939,46946,46955,46970,46976,46987,46995,47005,47017,47027,47040,47050,47061,47068,47074,47084,47096,47103,47111,47123,47133,47141,47150,47160,47168,47176,47189,47195,47203,47212,47224,47232,47240,47251,47262,47271,47280,47290,47302,47308,47319,47330,47346,47350,47358,47369,47377,47387,47396,47408,47414,47424,47435,47443,47450,47461,47472,47484,47493,47504,47511,47520,47525,47535,47544,47558,47569,47577,47588,47594,47603,47613,47620,47627,47640,47651,47661,47669,47681,47692,47702,47711,47721,47732,47740,47748,47761,47766,47775,47783,47793,47804,47813,47820,47833,47842,47853,47864,47872,47883,47891,47899,47905,47912,47922,47932,47943,47952,47963,47977,47982,47992,48000,48011,48022,48032,48044,48054,48061,48071,48081,48091,48100,48111,48123,48135,48144,48153,48164,48178,48189,48198,48210,48221,48231,48238,48247,48255,48266,48273,48283,48290,48302,48310,48318,48327,48332,48345,48351,48360,48369,48380,48388,48395,48405,48414,48422,48430,48438,48446,48456,48465,48474,48482,48489,48498,48507,48519,48529,48540,48551,48559,48569,48579,48591,48600,48612,48622,48631,48638,48646,48653,48664,48674,48685,48695,48705,48713,48724,48737,48748,48762,48768,48777,48785,48790,48801,48813,48821,48832,48837,48848,48858,48869,48880,48885,48893,48903,48914,48925,48934,48946,48953,48961,48971,48977,48988,48993,49005,49013,49025,49032,49040,49050,49060,49070,49080,49088,49098,49106,49115,49128,49138,49145,49154,49161,49174,49183,49194,49205,49213,49219,49226,49238,49247,49258,49268,49280,49290,49299,49310,49320,49330,49338,49347,49352,49360,49372,49380,49392,49406,49414,49420,49431,49439,49449,49458,49471,49479,49489,49499,49507,49515,49528,49534,49542,49553,49566,49572,49579,49587,49597,49607,49616,49625,49638,49650,49663,49668,49674,49684,49691,49703,49711,49719,49730,49742,49750,49760,49770,49781,49789,49800,49811,49821,49836,49842,49850,49861,49865,49874,49881,49889,49899,49911,49924,49934,49944,49950,49957,49968,49977,49983,49992,50005,50018,50028,50039,50046,50052,50061,50073,50081,50088,50102,50111,50123,50132,50142,50151,50160,50167,50176,50183,50190,50201,50215,50223,50231,50239,50245,50255,50269,50278,50287,50298,50306,50315,50329,50338,50349,50360,50369,50381,50391,50401,50412,50424,50434,50440,50453,50464,50472,50479,50485,50498,50505,50516,50523,50531,50539,50550,50558,50569,50573,50584,50592,50604,50612,50619,50629,50639,50650,50660,50670,50680,50689,50699,50707,50717,50725,50732,50743,50751,50759,50770,50782,50790,50797,50810,50817,50824,50833,50842,50845,50858,50867,50874,50888,50896,50908,50917,50928,50938,50948,50958,50968,50980,50986,50994,51004,51014,51020,51028,51037,51046,51055,51062,51071,51079,51085,51096,51108,51116,51125,51135,51143,51152,51161,51169,51179,51187,51195,51204,51215,51223,51233,51237,51245,51257,51266,51274,51281,51288,51298,51309,51319,51329,51341,51348,51358,51365,51372,51383,51392,51399,51408,51413,51425,51433,51445,51458,51467,51478,51489,51499,51507,51522,51530,51538,51549,51556,51566,51573,51580,51589,51603,51610,51615,51626,51636,51644,51657,51669,51676,51687,51699,51709,51718,51725,51731,51747,51757,51766,51775,51783,51796,51805,51813,51825,51832,51841,51850,51860,51869,51875,51884,51897,51907,51917,51928,51938,51943,51951,51959,51967,51974,51980,51988,51994,52002,52009,52017,52029,52036,52046,52060,52066,52074,52086,52098,52107,52114,52121,52131,52139,52151,52158,52167,52174,52185,52193,52200,52213,52222,52230,52243,52248,52254,52264,52269,52279,52290,52302,52310,52315,52324,52332,52344,52350,52360,52371,52383,52392,52402,52414,52425,52437,52446,52458,52464,52470,52482,52492,52504,52512,52521,52529,52539,52549,52557,52567,52573,52582,52595,52606,52613,52625,52633,52644,52656,52666,52674,52687,52696,52707,52715,52720,52730,52737,52747,52758,52764,52773,52785,52796,52807,52822,52831,52838,52843,52852,52859,52870,52873,52885,52892,52901,52913,52923,52931,52936,52946,52959,52966,52975,52983,52996,53005,53018,53029,53038,53051,53057,53064,53072,53076,53089,53100,53107,53120,53130,53143,53151,53158,53171,53180,53190,53198,53210,53218,53229,53236,53248,53258,53263,53271,53277,53284,53297,53306,53314,53325,53333,53342,53353,53359,53369,53381,53390,53398,53404,53412,53421,53431,53443,53452,53462,53469,53479,53491,53499,53508,53516,53523,53535,53546,53555,53564,53576,53586,53596,53603,53618,53626,53637,53647,53660,53668,53676,53684,53693,53699,53704,53717,53726,53733,53746,53753,53762,53772,53781,53791,53799,53809,53819,53823,53838,53846,53855,53868,53879,53887,53895,53903,53918,53929,53938,53945,53958,53969,53979,53985,53997,54005,54014,54022,54034,54043,54048,54057,54065,54078,54087,54095,54102,54111,54120,54129,54139,54150,54161,54169,54178,54187,54190,54193,54208,54217,54226,54235,54244,54251,54260,54272,54277,54289,54299,54309,54317,54329,54338,54347,54358,54367,54375,54384,54394,54403,54414,54422,54431,54439,54446,54460,54470,54483,54493,54500,54505,54512,54526,54536,54547,54556,54564,54580,54590,54597,54605,54613,54621,54631,54640,54646,54652,54665,54678,54686,54694,54706,54715,54723,54736,54741,54751,54761,54773,54780,54790,54799,54804,54813,54820,54835,54846,54854,54861,54869,54876,54885,54892,54898,54905,54916,54924,54937,54947,54959,54971,54980,54988,54999,55009,55018,55027,55037,55048,55063,55072,55082,55092,55103,55114,55120,55129,55138,55149,55156,55168,55179,55188,55196,55205,55216,55223,55233,55245,55255,55261,55271,55277,55282,55290,55296,55306,55319,55325,55337,55351,55360,55369,55376,55386,55396,55405,55412,55425,55432,55446,55453,55462,55471,55481,55492,55499,55506,55519,55528,55538,55545,55552,55560,55568,55580,55594,55602,55612,55626,55635,55645,55654,55662,55672,55681,55688,55699,55706,55719,55728,55736,55747,55754,55765,55774,55783,55789,55802,55815,55821,55827,55835,55846,55855,55861,55869,55875,55883,55894,55903,55911,55917,55931,55941,55954,55963,55971,55983,55995,56004,56014,56022,56031,56039,56047,56055,56064,56074,56088,56098,56104,56114,56119,56134,56144,56156,56162,56171,56180,56192,56198,56211,56220,56230,56241,56250,56257,56267,56270,56283,56292,56302,56311,56321,56330,56342,56350,56358,56370,56381,56392,56397,56409,56417,56421,56433,56443,56452,56459,56464,56471,56481,56492,56502,56512,56522,56529,56537,56543,56553,56563,56573,56582,56590,56598,56608,56618,56625,56633,56641,56655,56666,56677,56683,56689,56696,56707,56720,56730,56744,56753,56763,56770,56777,56789,56798,56808,56812,56824,56832,56841,56853,56864,56874,56883,56895,56904,56920,56928,56939,56950,56956,56966,56970,56975,56988,56996,57008,57019,57031,57038,57046,57056,57067,57078,57086,57095,57102,57109,57115,57128,57140,57152,57165,57175,57188,57196,57205,57211,57217,57229,57234,57244,57253,57262,57272,57283,57295,57306,57314,57318,57329,57340,57354,57360,57371,57384,57393,57402,57410,57418,57427,57439,57448,57460,57467,57475,57484,57495,57503,57513,57520,57532,57538,57551,57562,57572,57580,57587,57596,57605,57611,57620,57625,57631,57643,57648,57660,57671,57680,57692,57701,57710,57719,57728,57740,57754,57760,57766,57772,57785,57793,57806,57814,57823,57831,57839,57847,57855,57865,57873,57880,57888,57895,57902,57911,57923,57931,57940,57947,57955,57964,57977,57983,57990,57998,58011,58020,58029,58037,58048,58061,58069,58077,58084,58094,58107,58118,58133,58144,58152,58161,58170,58175,58184,58194,58203,58216,58225,58233,58241,58248,58257,58270,58281,58292,58305,58316,58320,58331,58343,58353,58357,58365,58376,58389,58399,58409,58418,58427,58434,58445,58453,58461,58470,58477,58487,58497,58506,58514,58525,58535,58544,58553,58563,58573,58583,58594,58603,58610,58620,58630,58638,58645,58651,58660,58668,58676,58690,58701,58714,58720,58728,58739,58747,58760,58771,58778,58789,58796,58802,58809,58817,58827,58834,58848,58858,58865,58876,58887,58891,58903,58913,58924,58934,58942,58955,58965,58972,58978,58987,58996,59005,59012,59022,59034,59044,59051,59056,59069,59080,59087,59098,59105,59118,59123,59135,59144,59154,59165,59177,59188,59201,59206,59216,59223,59233,59246,59253,59262,59273,59276,59284,59292,59302,59312,59320,59332,59339,59351,59361,59372,59380,59389,59397,59405,59416,59424,59430,59440,59450,59463,59472,59485,59495,59505,59512,59524,59531,59540,59549,59558,59565,59575,59587,59589,59598,59611,59620,59627,59638,59645,59654,59664,59672,59680,59692,59701,59707,59719,59728,59734,59745,59752,59765,59775,59779,59786,59794,59803,59812,59818,59826,59833,59842,59849,59860,59869,59876,59885,59895,59902,59907,59916,59927,59934,59943,59953,59967,59975,59982,59990,59999,60009,60019,60025,60032,60040,60053,60063,60070,60082,60090,60097,60106,60115,60124,60133,60144,60157,60166,60173,60186,60195,60207,60210,60219,60228,60238,60246,60259,60263,60271,60278,60289,60300,60306,60315,60328,60343,60350,60357,60370,60381,60391,60400,60409,60420,60428,60436,60445,60456,60464,60471,60480,60487,60497,60506,60518,60528,60535,60549,60560,60571,60581,60588,60597,60603,60618,60626,60635,60646,60656,60665,60672,60682,60688,60694,60704,60714,60721,60729,60741,60747,60754,60760,60768,60778,60788,60797,60805,60813,60822,60831,60842,60852,60860,60870,60882,60891,60901,60910,60919,60927,60936,60949,60962,60968,60978,60985,60998,61008,61017,61029,61035,61044,61055,61063,61074,61083,61099,61110,61118,61127,61135,61145,61151,61159,61168,61177,61184,61192,61203,61214,61221,61229,61241,61253,61259,61269,61282,61293,61301,61311,61317,61327,61335,61342,61354,61364,61378,61388,61398,61408,61414,61424,61436,61445,61456,61467,61477,61486,61493,61504,61514,61522,61529,61539,61545,61558,61566,61578,61582,61590,61603,61615,61626,61633,61640,61652,61659,61670,61678,61687,61697,61707,61716,61723,61733,61745,61755,61762,61769,61782,61789,61801,61810,61821,61829,61837,61848,61859,61868,61874,61885,61893,61902,61910,61921,61928,61938,61946,61955,61966,61974,61982,61991,62002,62010,62021,62031,62040,62054,62060,62066,62075,62084,62097,62103,62113,62121,62130,62135,62144,62154,62162,62170,62179,62191,62197,62206,62215,62222,62231,62240,62249,62263,62271,62283,62290,62299,62309,62316,62329,62338,62346,62353,62365,62377,62387,62397,62406,62415,62423,62427,62441,62450,62459,62468,62475,62484,62491,62501,62507,62518,62528,62538,62548,62559,62570,62581,62592,62600,62608,62620,62631,62642,62650,62660,62665,62674,62680,62688,62697,62707,62718,62724,62734,62749,62760,62763,62772,62783,62793,62805,62815,62823,62831,62838,62847,62858,62872,62879,62890,62898,62908,62915,62925,62934,62943,62950,62956,62967,62973,62985,62995,63002,63011,63020,63031,63037,63049,63058,63069,63078,63089,63101,63111,63117,63127,63138,63149,63156,63162,63171,63181,63193,63199,63206,63217,63224,63234,63243,63254,63265,63274,63284,63295,63302,63312,63321,63328,63334,63343,63355,63367,63376,63387,63396,63406,63420,63426,63437,63442,63450,63458,63466,63477,63488,63498,63508,63521,63536,63539,63550,63560,63570,63572,63581,63592,63602,63611,63617,63626,63639,63649,63660,63666,63676,63686,63695,63705,63713,63727,63737,63749,63755,63763,63770,63784,63794,63800,63809,63819,63831,63839,63848,63856,63866,63873,63880,63888,63894,63905,63913,63923,63933,63943,63951,63962,63973,63981,63991,64005,64019,64025,64036,64046,64053,64062,64070,64080,64088,64096,64102,64110,64122,64129,64136,64145,64154,64165,64172,64180,64186,64195,64207,64216,64226,64231,64241,64252,64261,64271,64278,64291,64297,64307,64319,64333,64342,64354,64363,64373,64381,64391,64398,64410,64418,64429,64436,64444,64449,64457,64466,64475,64485,64491,64504,64512,64520,64527,64536,64542,64551,64562,64570,64579,64590,64598,64605,64612,64624,64633,64645,64654,64663,64675,64683,64692,64700,64711,64725,64736,64742,64750,64761,64767,64778,64786,64794,64803,64814,64823,64833,64840,64851,64863,64873,64880,64892,64898,64902,64914,64923,64934,64942,64952,64958,64967,64974,64987,64999,65004,65014,65024,65032,65042,65052,65058,65065,65075,65085,65096,65106,65112,65121,65130,65143,65150,65157,65165,65173,65185,65196,65207,65216,65226,65233,65239,65249,65260,65271,65279,65287,65299,65306,65313,65320,65325,65333,65342,65351,65362,65378,65387,65397,65408,65416,65423,65435,65446,65455,65462,65474,65481,65491,65503,65511,65518,65530,65535,65542,65555,65563,65571,65583,65595,65602,65615,65627,65637,65647,65653,65665,65674,65683,65692,65706,65716,65725,65734,65743,65747,65758,65765,65776,65785,65796,65808,65817,65829,65839,65849,65860,65867,65877,65886,65894,65904,65914,65924,65935,65944,65955,65961,65969,65977,65985,65993,66002,66015,66024,66035,66043,66047,66054,66061,66073,66083,66093,66103,66113,66118,66123,66131,66144,66154,66161,66168,66176,66189,66200,66211,66219,66228,66237,66246,66254,66263,66270,66282,66296,66307,66316,66324,66332,66343,66355,66362,66377,66385,66398,66406,66413,66422,66432,66439,66449,66457,66466,66471,66480,66490,66495,66506,66514,66524,66533,66542,66548,66555,66566,66574,66584,66594,66606,66611,66625,66633,66641,66649,66660,66670,66677,66687,66692,66701,66710,66718,66727,66734,66741,66751,66762,66766,66779,66790,66797,66807,66821,66827,66833,66841,66853,66863,66870,66878,66890,66896,66907,66917,66924,66931,66940,66950,66960,66971,66982,66993,67000,67006,67014,67020,67029,67041,67051,67063,67077,67087,67092,67101,67112,67118,67127,67137,67148,67157,67164,67174,67180,67190,67202,67210,67223,67235,67242,67251,67258,67267,67278,67288,67296,67300,67308,67315,67328,67333,67342,67350,67363,67367,67376,67384,67397,67408,67420,67430,67436,67447,67457,67463,67474,67480,67488,67495,67506,67515,67526,67538,67549,67557,67568,67575,67582,67591,67600,67608,67617,67628,67639,67650,67661,67666,67673,67679,67687,67697,67707,67719,67729,67738,67748,67758,67764,67771,67783,67792,67798,67809,67815,67829,67838,67847,67854,67860,67868,67874,67884,67895,67904,67916,67922,67932,67944,67952,67958,67963,67975,67982,67991,68001,68011,68018,68032,68038,68048,68057,68068,68076,68087,68095,68106,68116,68126,68138,68145,68156,68163,68171,68185,68192,68202,68210,68219,68229,68237,68243,68251,68260,68271,68282,68287,68297,68305,68315,68323,68333,68342,68355,68357,68370,68379,68391,68397,68407,68419,68432,68440,68446,68453,68463,68472,68481,68493,68502,68516,68527,68540,68549,68557,68564,68576,68583,68589,68596,68601,68608,68617,68627,68636,68651,68661,68672,68679,68690,68699,68705,68716,68727,68736,68749,68757,68764,68775,68789,68796,68810,68816,68822,68830,68835,68847,68856,68864,68874,68883,68894,68905,68917,68927,68936,68942,68953,68961,68971,68982,68991,68999,69010,69022,69030,69038,69050,69060,69069,69076,69085,69095,69104,69117,69125,69136,69144,69153,69162,69174,69180,69188,69194,69199,69208,69216,69223,69232,69242,69256,69265,69278,69288,69297,69302,69308,69318,69323,69332,69342,69351,69362,69367,69373,69384,69391,69401,69410,69417,69430,69441,69448,69455,69464,69477,69487,69498,69511,69520,69528,69541,69551,69563,69569,69577,69586,69598,69603,69612,69620,69631,69639,69648,69652,69662,69670,69681,69693,69699,69708,69717,69729,69741,69748,69758,69767,69778,69784,69793,69808,69815,69823,69835,69845,69855,69861,69872,69883,69893,69903,69912,69924,69933,69943,69951,69959,69963,69972,69982,69992,69999,70009,70018,70027,70033,70044,70054,70065,70073,70084,70091,70102,70108,70117,70125,70135,70148,70157,70164,70170,70177,70186,70194,70204,70213,70223,70233,70239,70248,70263,70272,70282,70290,70301,70313,70319,70328,70339,70346,70354,70361,70371,70380,70395,70402,70410,70419,70428,70438,70451,70455,70465,70477,70487,70497,70503,70516,70523,70528,70538,70543,70555,70565,70573,70579,70586,70593,70601,70612,70623,70632,70639,70646,70658,70671,70681,70692,70703,70713,70721,70729,70737,70747,70755,70764,70772,70785,70794,70803,70813,70820,70828,70835,70844,70852,70868,70876,70885,70896,70905,70912,70918,70926,70938,70950,70958,70965,70978,70989,70998,71007,71011,71022,71030,71041,71049,71054,71062,71073,71081,71093,71102,71113,71122,71128,71137,71146,71160,71170,71180,71189,71196,71206,71213,71218,71230,71235,71244,71249,71257,71266,71274,71283,71293,71302,71308,71321,71330,71340,71348,71357,71369,71376,71388,71396,71404,71411,71421,71430,71436,71446,71454,71464,71472,71483,71491,71498,71505,71514,71525,71532,71539,71547,71554,71566,71574,71582,71588,71598,71612,71625,71635,71643,71656,71663,71671,71678,71689,71697,71705,71715,71723,71734,71746,71755,71765,71776,71785,71792,71805,71815,71827,71834,71846,71856,71865,71873,71883,71889,71899,71914,71923,71935,71944,71957,71965,71978,71987,71996,72005,72016,72026,72036,72047,72052,72058,72066,72074,72083,72088,72099,72113,72125,72130,72137,72149,72159,72169,72178,72186,72193,72207,72214,72218,72231,72240,72247,72253,72261,72270,72275,72281,72287,72294,72299,72307,72320,72327,72339,72347,72360,72367,72376,72387,72395,72401,72412,72421,72428,72437,72447,72458,72467,72477,72486,72492,72500,72509,72521,72532,72540,72546,72556,72566,72581,72588,72596,72607,72619,72628,72635,72643,72653,72663,72673,72683,72691,72699,72707,72713,72723,72734,72740,72750,72760,72772,72777,72787,72798,72806,72815,72827,72834,72843,72850,72861,72869,72878,72892,72898,72910,72918,72927,72940,72945,72950,72958,72972,72979,72989,73003,73011,73019,73031,73043,73049,73057,73068,73076,73088,73100,73107,73122,73132,73141,73150,73161,73170,73176,73187,73196,73206,73214,73223,73234,73244,73252,73261,73269,73277,73285,73291,73298,73309,73321,73324,73332,73341,73351,73361,73369,73377,73388,73394,73408,73417,73425,73435,73446,73458,73466,73474,73484,73493,73501,73510,73519,73527,73536,73543,73549,73560,73568,73573,73582,73590,73600,73612,73620,73632,73639,73649,73661,73668,73676,73688,73695,73703,73712,73721,73728,73735,73746,73756,73769,73776,73783,73795,73807,73814,73824,73837,73846,73855,73861,73871,73881,73891,73901,73905,73911,73921,73929,73940,73949,73960,73967,73976,73984,73994,73999,74006,74014,74027,74036,74047,74061,74067,74079,74086,74095,74100,74108,74119,74128,74136,74145,74154,74161,74169,74179,74187,74195,74205,74216,74222,74233,74241,74251,74261,74271,74281,74290,74301,74313,74324,74330,74340,74352,74361,74370,74376,74385,74394,74404,74412,74423,74433,74445,74453,74461,74467,74482,74488,74495,74504,74511,74523,74535,74545,74552,74561,74566,74573,74580,74591,74597,74607,74615,74627,74638,74645,74652,74661,74668,74678,74688,74699,74703,74710,74717,74729,74736,74748,74758,74765,74775,74783,74791,74803,74810,74816,74822,74832,74841,74850,74854,74866,74875,74886,74893,74907,74916,74926,74934,74944,74953,74965,74975,74983,74997,75002,75013,75023,75030,75038,75045,75053,75063,75074,75082,75090,75099,75109,75119,75131,75139,75147,75154,75161,75171,75180,75187,75196,75203,75213,75224,75234,75241,75250,75260,75269,75277,75287,75298,75308,75314,75322,75331,75345,75352,75357,75366,75374,75380,75386,75393,75403,75414,75424,75431,75438,75447,75455,75463,75472,75482,75488,75502,75510,75520,75530,75538,75549,75553,75564,75574,75585,75591,75599,75609,75618,75627,75636,75645,75652,75660,75670,75677,75686,75700,75712,75718,75727,75737,75752,75765,75774,75783,75790,75796,75806,75817,75827,75837,75845,75852,75863,75874,75883,75887,75899,75912,75919,75926,75934,75949,75954,75965,75972,75981,75993,76001,76014,76021,76032,76041,76047,76056,76063,76069,76080,76091,76103,76112,76118,76125,76136,76141,76146,76157,76166,76173,76181,76193,76202,76213,76222,76233,76243,76252,76261,76268,76277,76286,76293,76302,76314,76321,76331,76341,76350,76360,76369,76377,76387,76393,76401,76413,76426,76437,76446,76457,76468,76476,76484,76493,76504,76515,76525,76537,76547,76555,76562,76570,76578,76589,76595,76605,76613,76620,76626,76636,76641,76650,76661,76669,76682,76693,76702,76713,76726,76733,76741,76751,76761,76769,76779,76787,76796,76805,76812,76821,76831,76841,76849,76855,76862,76869,76879,76888,76893,76902,76909,76917,76922,76938,76949,76959,76969,76977,76986,76995,77002,77012,77022,77034,77041,77048,77053,77059,77067,77074,77083,77089,77100,77109,77118,77124,77134,77144,77154,77163,77175,77184,77193,77199,77209,77219,77229,77238,77244,77252,77259,77272,77279,77285,77297,77306,77316,77326,77330,77342,77349,77358,77364,77376,77389,77397,77404,77410,77419,77429,77435,77444,77457,77465,77475,77483,77495,77501,77513,77521,77528,77541,77551,77561,77571,77583,77591,77597,77604,77613,77618,77625,77634,77644,77654,77663,77670,77680,77689,77698,77705,77713,77718,77728,77737,77744,77753,77765,77777,77783,77791,77806,77814,77823,77830,77837,77848,77859,77869,77875,77885,77895,77905,77912,77927,77934,77942,77952,77959,77968,77975,77984,77992,78001,78011,78019,78029,78035,78040,78050,78060,78069,78080,78091,78099,78108,78117,78128,78138,78145,78152,78161,78170,78182,78192,78196,78207,78215,78225,78236,78242,78251,78259,78268,78276,78293,78302,78314,78321,78330,78341,78348,78359,78369,78378,78384,78394,78402,78413,78422,78433,78442,78451,78458,78466,78475,78483,78489,78498};
const int block_length = 150;
bool judge(int x){
    if(x==1)return false;
    for(int i = 2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}
int cal(int a,int b){
    int ba = a/block_length;int bb = b/block_length;
    if(bb-ba<=1){//ab在同一块内,上暴力
        int cnt = 0;
        for(int i = a;i<=b;i++){
            if(judge(i))cnt++;
        }
        return cnt;
    }else{//ab不在同一块内,分块+打表
        int sum1 = 0;
        int sum2 = 0;
        for(int i = ba*block_length+1;i<=a-1;i++){if(judge(i)){sum1++; }} 

        if(a>=block_length)sum1+=table[ba-1];
        for(int i = bb*block_length+1;i<=b;i++)if(judge(i))sum2++;
        sum2+=table[bb-1];
        return sum2-sum1;
    }
}
int main(void){
    freopen("a.txt","r",stdin);
    freopen("b.txt","w",stdout);
    int n,m;
    n = read(),m = read();
    int l,r;
    while(n--){
        l = read(),r = read();
        if(l>m||l<1||r<1||r>m||l>=m){
            printf("Crossing the line\n");
            continue;
        }else{
            printf("%d\n",cal(l,r));
        }
    }
    return 0;
}

注意,两份代码中的block_legth表示的是每一块的长度,必须保持一致(虽然数据比较水,不一致也可以过好几个点)

结果