#pragma GCC optimize ("Ofast") #include using namespace std; void *wmem; char memarr[96000000]; template inline S min_L(S a,T b){ return a<=b?a:b; } template inline void walloc1d(T **arr, int x, void **mem = &wmem){ static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] ); (*arr)=(T*)(*mem); (*mem)=((*arr)+x); } inline void rd(int &x){ int k; int m=0; x=0; for(;;){ k = getchar_unlocked(); if(k=='-'){ m=1; break; } if('0'<=k&&k<='9'){ x=k-'0'; break; } } for(;;){ k = getchar_unlocked(); if(k<'0'||k>'9'){ break; } x=x*10+k-'0'; } if(m){ x=-x; } } inline void wt_L(char a){ putchar_unlocked(a); } inline void wt_L(long long x){ int s=0; int m=0; char f[20]; if(x<0){ m=1; x=-x; } while(x){ f[s++]=x%10; x/=10; } if(!s){ f[s++]=0; } if(m){ putchar_unlocked('-'); } while(s--){ putchar_unlocked(f[s]+'0'); } } int Prime_L(int N, int res[], void *mem=wmem){ int i; int a; int b; int sz = 1; const int r = 23000; bool *isprime; int *sf; int ss = 1; walloc1d(&isprime, r, &mem); walloc1d(&sf, r, &mem); isprime = (bool*)mem; sf = (int*)(isprime + r); N /= 2; res[0] = 2; b =min_L(r, N); for(i=(1);i<(b);i++){ isprime[i] = 1; } for(i=(1);i<(b);i++){ if(isprime[i]){ res[sz++] = 2*i+1; sf[ss] = 2*i*(i+1); if(sf[ss] < N){ while(sf[ss] < r){ isprime[sf[ss]] = 0; sf[ss] += res[ss]; } ss++; } } } for(a=r; a