// DUCK_PUBLIC_SURROGATE_BENCHMARK
// Independent public arrays only; no production seeds or data.
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <algorithm>
#include <cstdint>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace mod_atile {
using u32=uint32_t;using u64=uint64_t;
inline void scalar(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned out_r){for(unsigned j=l+1;j<std::min(r,n-l);++j)for(unsigned p=j;p+l<n;p+=j)for(unsigned k=l;k<std::min({out_r,j,n-p});++k)c[k]+=a[p+k]*b[j];}
template<unsigned ABlock=16384,unsigned Mode=2>
void direct_piece(unsigned n,const u32*__restrict a,const u32*__restrict b,u32*__restrict c,unsigned l,unsigned r,unsigned out_r){
if(n<64){scalar(n,a,b,c,l,r,out_r);return;}
for(unsigned j=l+1;j<std::min(r,65u);++j){u32 sum[64]={};for(unsigned p=j;p+l<n;p+=j)for(unsigned k=l;k<std::min({out_r,j,n-p});++k)sum[k]+=a[p+k];for(unsigned k=l;k<std::min(j,out_r);++k)c[k]+=sum[k]*b[j];}
const unsigned jlo=std::max(l+1,65u),limit=std::min(out_r,n/2);if(jlo>=r||l>=limit)return;
for(unsigned alo=0;alo<n;alo+=ABlock){const unsigned ahi=std::min(n,alo+ABlock);unsigned kend=std::min(limit,(ahi-1)/2+1);
for(unsigned k0=l;k0<kend;k0+=32){
const unsigned first=std::max(jlo,k0+1),last=std::min(r-1,ahi-1-k0);if(first>last)continue;
__m256i z[4],idx[4],maskend[4];for(unsigned v=0;v<4;++v){z[v]=_mm256_loadu_si256((const __m256i*)(c+k0+8*v));idx[v]=_mm256_setr_epi32(k0+8*v,k0+8*v+1,k0+8*v+2,k0+8*v+3,k0+8*v+4,k0+8*v+5,k0+8*v+6,k0+8*v+7);maskend[v]=_mm256_cmpgt_epi32(_mm256_set1_epi32(out_r),idx[v]);}
auto add=[&](unsigned start,unsigned j,__m256i bj){
if(k0+32<=out_r&&k0+32<=j&&start+32<=n){for(unsigned v=0;v<4;++v)z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(a+start+8*v)),bj));}
else for(unsigned v=0;v<4;++v){__m256i mask=_mm256_and_si256(maskend[v],_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(j),idx[v]),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-start+k0),idx[v])));__m256i x=start+8*v<n?_mm256_maskload_epi32((const int*)(a+start+8*v),mask):_mm256_setzero_si256();z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(x,bj));}
};
const unsigned low=alo>k0?alo-k0:0,high=ahi-1-k0;
unsigned qlo=std::max(1u,(low+last-1)/last),qhi=high/first;
if(qlo>qhi)continue;
bool by_j=Mode==0||(Mode==2&&last-first+1<=qhi-qlo+1);
if(by_j){for(unsigned j=first;j<=last;++j){unsigned begin=std::max(1u,(low+j-1)/j),end=high/j;if(begin>end)continue;__m256i bj=_mm256_set1_epi32(b[j]);unsigned at=begin*j+k0;for(unsigned q=begin;q<=end;++q,at+=j)add(at,j,bj);}}
else {for(unsigned q=qlo;q<=qhi;++q){unsigned begin=std::max(first,(low+q-1)/q),end=std::min(last,high/q);for(unsigned j=begin;j<=end;++j)add(q*j+k0,j,_mm256_set1_epi32(b[j]));}}
for(unsigned v=0;v<4;++v)_mm256_storeu_si256((__m256i*)(c+k0+8*v),z[v]);
}
}
}
template<unsigned ABlock=16384,unsigned Mode=2>void direct_range(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r){direct_piece<ABlock,Mode>(n,a,b,c,l,r,r);}
}
#include <vector>
namespace mod_dtile {
using u32=uint32_t;using u64=uint64_t;
struct Group{u32 j,begin,end,b;};
template<unsigned DBlock=4096>
void direct_piece(unsigned n,const u32*__restrict a,const u32*__restrict b,u32*__restrict c,unsigned l,unsigned r,unsigned out_r){
if(n<64){mod_atile::scalar(n,a,b,c,l,r,out_r);return;}
for(unsigned j=l+1;j<std::min(r,65u);++j){u32 sum[64]={};for(unsigned p=j;p+l<n;p+=j)for(unsigned k=l;k<std::min({out_r,j,n-p});++k)sum[k]+=a[p+k];for(unsigned k=l;k<std::min(j,out_r);++k)c[k]+=sum[k]*b[j];}
const unsigned first=std::max(l+1,65u),jend=std::min(r,n-l),limit=std::min(out_r,n/2);if(first>=jend||l>=limit)return;
std::vector<Group>groups;
for(unsigned lo=0;lo<n-l;lo+=DBlock){unsigned hi=std::min(n-l,lo+DBlock);groups.clear();
unsigned qlo=std::max(1u,(lo+jend-2)/(jend-1)),qhi=(hi-1)/first;if(qlo>qhi)continue;
if(first<=DBlock){for(unsigned j=first;j<jend&&j<hi;++j){unsigned qb=std::max(1u,(lo+j-1)/j),qe=(hi-1)/j;if(qb<=qe)groups.push_back({j,qb*j,qe*j,b[j]});}}
else {for(unsigned q=qlo;q<=qhi;++q){unsigned jb=std::max(first,(lo+q-1)/q),je=std::min(jend-1,(hi-1)/q);for(unsigned j=jb;j<=je;++j)groups.push_back({j,q*j,q*j,b[j]});}}
if(groups.empty())continue;
unsigned kend=std::min(limit,n-lo);
for(unsigned k0=l;k0<kend;k0+=32){
__m256i z[4];
#pragma GCC unroll 4
for(unsigned v=0;v<4;++v)z[v]=_mm256_loadu_si256((const __m256i*)(c+k0+8*v));
for(const Group&g:groups){if(g.j<=k0||g.begin>=n-k0)continue;unsigned end=std::min(g.end,n-1-k0);const __m256i bj=_mm256_set1_epi32(g.b);
if(k0+32<=out_r&&k0+32<=g.j&&end<=n-k0-32){
for(unsigned d=g.begin;d<=end;d+=g.j){const u32*x=a+d+k0;
#pragma GCC unroll 4
for(unsigned v=0;v<4;++v)z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+8*v)),bj));}
}else{
for(unsigned d=g.begin;d<=end;d+=g.j){
#pragma GCC unroll 4
for(unsigned v=0;v<4;++v){__m256i idx=_mm256_setr_epi32(k0+8*v,k0+8*v+1,k0+8*v+2,k0+8*v+3,k0+8*v+4,k0+8*v+5,k0+8*v+6,k0+8*v+7);__m256i mask=_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(out_r),idx),_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(g.j),idx),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-d),idx)));__m256i x=d+k0+8*v<n?_mm256_maskload_epi32((const int*)(a+d+k0+8*v),mask):_mm256_setzero_si256();z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(x,bj));}
}
}
}
#pragma GCC unroll 4
for(unsigned v=0;v<4;++v)_mm256_storeu_si256((__m256i*)(c+k0+8*v),z[v]);
}
}
}
template<unsigned DBlock=4096>void direct_range(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r){direct_piece<DBlock>(n,a,b,c,l,r,r);}
}
namespace mod_count {
using u32=uint32_t;
struct Group{u32 d,cap,b;};
template<unsigned DBlock=4096>
void direct_piece(unsigned n,const u32*__restrict a,const u32*__restrict b,u32*__restrict c,unsigned l,unsigned r,unsigned out_r){
unsigned first=std::max(l+1,65u);
if(n<64||first<=DBlock){mod_dtile::direct_piece<DBlock>(n,a,b,c,l,r,out_r);return;}
unsigned jend=std::min(r,n-l),limit=std::min(out_r,n/2);if(first>=jend||l>=limit)return;
std::vector<Group>groups,temp;const unsigned buckets=(out_r-l+31)/32;std::vector<unsigned>hist(buckets),offset(buckets+1),cursor(buckets);
for(unsigned lo=0;lo<n-l;lo+=DBlock){unsigned hi=std::min(n-l,lo+DBlock);groups.clear();unsigned qb=std::max(1u,(lo+jend-2)/(jend-1)),qe=(hi-1)/first;
for(unsigned q=qb;q<=qe;++q){unsigned jb=std::max(first,(lo+q-1)/q),je=std::min(jend-1,(hi-1)/q);for(unsigned j=jb;j<=je;++j){unsigned d=q*j,cap=std::min({j-1,n-1-d,out_r-1});if(cap>=l)groups.push_back({d,cap,b[j]});}}
if(groups.empty())continue;
std::fill(hist.begin(),hist.end(),0u);for(const Group&g:groups)++hist[(g.cap-l)/32];offset[0]=0;for(unsigned i=0;i<buckets;++i)offset[i+1]=offset[i]+hist[i];cursor.assign(offset.begin(),offset.end()-1);temp.resize(groups.size());for(const Group&g:groups)temp[cursor[(g.cap-l)/32]++]=g;groups.swap(temp);
unsigned kend=std::min(limit,n-lo);
for(unsigned k0=l;k0<kend;k0+=32){size_t bucket=(k0-l)/32,begin=offset[bucket],stop=offset[bucket+1];if(begin==groups.size())break;
__m256i z0=_mm256_loadu_si256((const __m256i*)(c+k0)),z1=_mm256_loadu_si256((const __m256i*)(c+k0+8)),z2=_mm256_loadu_si256((const __m256i*)(c+k0+16)),z3=_mm256_loadu_si256((const __m256i*)(c+k0+24));size_t at=begin;
for(;at<stop;++at){const Group&g=groups[at];unsigned cnt=g.cap-k0+1;const u32*x=a+g.d+k0;__m256i bj=_mm256_set1_epi32(g.b);
#define MASKADD(V,Z) if(cnt>V*8){__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(cnt),_mm256_setr_epi32(V*8,V*8+1,V*8+2,V*8+3,V*8+4,V*8+5,V*8+6,V*8+7));Z=_mm256_add_epi32(Z,_mm256_mullo_epi32(_mm256_maskload_epi32((const int*)(x+V*8),mask),bj));}
MASKADD(0,z0)MASKADD(1,z1)MASKADD(2,z2)MASKADD(3,z3)
#undef MASKADD
}
for(;at<groups.size();++at){const Group&g=groups[at];const u32*x=a+g.d+k0;__m256i bj=_mm256_set1_epi32(g.b);z0=_mm256_add_epi32(z0,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)x),bj));z1=_mm256_add_epi32(z1,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+8)),bj));z2=_mm256_add_epi32(z2,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+16)),bj));z3=_mm256_add_epi32(z3,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+24)),bj));}
_mm256_storeu_si256((__m256i*)(c+k0),z0);_mm256_storeu_si256((__m256i*)(c+k0+8),z1);_mm256_storeu_si256((__m256i*)(c+k0+16),z2);_mm256_storeu_si256((__m256i*)(c+k0+24),z3);
}
}
}
}
#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
namespace mod_dynamicbits64 {
using u32=uint32_t;
template<unsigned DBlock=2048>
void direct_piece(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned out_r){
if(n<128){for(unsigned j=l+1;j<std::min(r,n-l);++j)for(unsigned d=j;d<n-l;d+=j)for(unsigned k=l;k<std::min({out_r,j,n-d});++k)c[k]+=a[d+k]*b[j];return;}
for(unsigned j=l+1;j<std::min(r,65u);++j){u32 sum[64]={};for(unsigned d=j;d+l<n;d+=j)for(unsigned k=l;k<std::min({out_r,j,n-d});++k)sum[k]+=a[d+k];for(unsigned k=l;k<std::min(j,out_r);++k)c[k]+=sum[k]*b[j];}
const unsigned jend=std::min(r,n-l),limit=std::min(out_r,n/2);if(l>=limit||std::max(l+1,65u)>=jend)return;
std::vector<u32>w(DBlock),count(DBlock);std::vector<uint64_t>bits((DBlock+63)/64);
for(unsigned lo=0;lo<n-l;lo+=DBlock){unsigned hi=std::min(n-l,lo+DBlock),sz=hi-lo,first=std::max(l+64,65u);std::fill(w.begin(),w.end(),0u);std::fill(count.begin(),count.end(),0u);std::fill(bits.begin(),bits.end(),0ull);
auto add=[&](unsigned at,u32 value){w[at]+=value;if(count[at]++==0)bits[at/64]|=1ull<<(at%64);};auto sub=[&](unsigned at,u32 value){w[at]-=value;if(--count[at]==0)bits[at/64]&=~(1ull<<(at%64));};
if(first<jend){unsigned qb=std::max(1u,(lo+jend-2)/(jend-1)),qe=(hi-1)/first;
if(qb<=qe&&qe-qb+1<jend-first){for(unsigned q=qb;q<=qe;++q){unsigned jb=std::max(first,(lo+q-1)/q),je=std::min(jend-1,(hi-1)/q);for(unsigned j=jb;j<=je;++j)add(q*j-lo,b[j]);}}
else for(unsigned j=first;j<jend&&j<hi;++j)for(unsigned d=std::max(1u,(lo+j-1)/j)*j;d<hi;d+=j)add(d-lo,b[j]);
}
unsigned kend=std::min(limit,n-lo);
for(unsigned k0=l;k0<kend;k0+=64){
__m256i z0=_mm256_loadu_si256((const __m256i*)(c+k0+0)), z1=_mm256_loadu_si256((const __m256i*)(c+k0+8)), z2=_mm256_loadu_si256((const __m256i*)(c+k0+16)), z3=_mm256_loadu_si256((const __m256i*)(c+k0+24)), z4=_mm256_loadu_si256((const __m256i*)(c+k0+32)), z5=_mm256_loadu_si256((const __m256i*)(c+k0+40)), z6=_mm256_loadu_si256((const __m256i*)(c+k0+48)), z7=_mm256_loadu_si256((const __m256i*)(c+k0+56));
#define ADDVAL(D,B,CNT) {unsigned cnt=(CNT);const u32*x=a+(D)+k0;__m256i bj=_mm256_set1_epi32(B);if(cnt>=64){z0=_mm256_add_epi32(z0,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+0)),bj));z1=_mm256_add_epi32(z1,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+8)),bj));z2=_mm256_add_epi32(z2,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+16)),bj));z3=_mm256_add_epi32(z3,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+24)),bj));z4=_mm256_add_epi32(z4,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+32)),bj));z5=_mm256_add_epi32(z5,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+40)),bj));z6=_mm256_add_epi32(z6,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+48)),bj));z7=_mm256_add_epi32(z7,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+56)),bj));}else {MASKADD(0,z0)MASKADD(1,z1)MASKADD(2,z2)MASKADD(3,z3)MASKADD(4,z4)MASKADD(5,z5)MASKADD(6,z6)MASKADD(7,z7)}}
#define MASKADD(V,Z) if(cnt>V*8){__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(cnt),_mm256_setr_epi32(V*8,V*8+1,V*8+2,V*8+3,V*8+4,V*8+5,V*8+6,V*8+7));Z=_mm256_add_epi32(Z,_mm256_mullo_epi32(_mm256_maskload_epi32((const int*)(x+V*8),mask),bj));}
unsigned use=std::min(sz,n-k0-lo);
for(unsigned u=0;u<use;u+=64){uint64_t mask=bits[u/64];if(use-u<64)mask&=(1ull<<(use-u))-1;while(mask){unsigned t=__builtin_ctzll(mask),d=lo+u+t;mask&=mask-1;ADDVAL(d,w[u+t],std::min(out_r-k0,n-d-k0));}}
for(unsigned j=std::max(k0+1,65u);j<std::min(jend,k0+64);++j)for(unsigned d=std::max(1u,(lo+j-1)/j)*j;d<hi&&d+k0<n;d+=j){ADDVAL(d,b[j],std::min({j-k0,out_r-k0,n-d-k0}));}
#undef ADDVAL
#undef MASKADD
_mm256_storeu_si256((__m256i*)(c+k0+0),z0);_mm256_storeu_si256((__m256i*)(c+k0+8),z1);_mm256_storeu_si256((__m256i*)(c+k0+16),z2);_mm256_storeu_si256((__m256i*)(c+k0+24),z3);_mm256_storeu_si256((__m256i*)(c+k0+32),z4);_mm256_storeu_si256((__m256i*)(c+k0+40),z5);_mm256_storeu_si256((__m256i*)(c+k0+48),z6);_mm256_storeu_si256((__m256i*)(c+k0+56),z7);
if(k0+64<kend)for(unsigned j=std::max(k0+64,65u);j<std::min(jend,k0+128);++j)for(unsigned d=std::max(1u,(lo+j-1)/j)*j;d<hi;d+=j)sub(d-lo,b[j]);
}
}
}
}
#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
namespace mod_filtered {
using u32=uint32_t;using u64=uint64_t;
struct Group{u32 d,b;};
template<unsigned DBlock=2048>
void cross_filtered(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned qmin=1,unsigned qmax=~0u){
unsigned m=l+(r-l)/2,jend=std::min(r,n-l);qmin=std::max(1u,qmin);
if(m<=l||m>=jend||qmin>qmax)return;
if(n<128){for(unsigned j=m;j<jend;++j)for(unsigned q=qmin;q<=std::min(qmax,(n-1-l)/j);++q)for(unsigned k=l;k<std::min(m,n-q*j);++k)c[k]+=a[q*j+k]*b[j];return;}
const unsigned limit=std::min(m,n-m);std::vector<u32>weights(DBlock);std::vector<Group>groups;groups.reserve(DBlock);
for(unsigned lo=0;lo<n-l;lo+=DBlock){unsigned hi=std::min(n-l,lo+DBlock),qb=std::max(qmin,(lo+jend-2)/(jend-1)),qe=std::min(qmax,(hi-1)/m);if(qb>qe)continue;
std::fill(weights.begin(),weights.end(),0u);
if(qe-qb+1<jend-m){for(unsigned q=qb;q<=qe;++q){unsigned jb=std::max(m,(lo+q-1)/q),je=std::min(jend-1,(hi-1)/q);for(unsigned j=jb;j<=je;++j)weights[q*j-lo]+=b[j];}}
else {unsigned je=std::min(jend-1,(hi-1)/qmin);for(unsigned j=m;j<=je;++j){unsigned bq=std::max(qmin,(lo+j-1)/j),eq=std::min(qmax,(hi-1)/j);if(bq<=eq)for(unsigned d=bq*j;d<=eq*j;d+=j)weights[d-lo]+=b[j];}}
groups.clear();for(unsigned u=0;u<hi-lo;++u)if(weights[u])groups.push_back({lo+u,weights[u]});if(groups.empty())continue;
unsigned kend=std::min(limit,n-groups.front().d);
for(unsigned k0=l;k0<kend;k0+=64){
__m256i z0=_mm256_loadu_si256((const __m256i*)(c+k0+0)), z1=_mm256_loadu_si256((const __m256i*)(c+k0+8)), z2=_mm256_loadu_si256((const __m256i*)(c+k0+16)), z3=_mm256_loadu_si256((const __m256i*)(c+k0+24)), z4=_mm256_loadu_si256((const __m256i*)(c+k0+32)), z5=_mm256_loadu_si256((const __m256i*)(c+k0+40)), z6=_mm256_loadu_si256((const __m256i*)(c+k0+48)), z7=_mm256_loadu_si256((const __m256i*)(c+k0+56));
size_t stop=0;if(k0+64<=m){u32 maxd=n-k0-64;if(groups.back().d<=maxd)stop=groups.size();else{stop=std::upper_bound(groups.begin(),groups.end(),maxd,[](u32 d,const Group&g){return d<g.d;})-groups.begin();}}
for(size_t at=0;at<stop;++at){const Group&g=groups[at];const u32*x=a+g.d+k0;__m256i bj=_mm256_set1_epi32(g.b);
z0=_mm256_add_epi32(z0,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+0)),bj));
z1=_mm256_add_epi32(z1,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+8)),bj));
z2=_mm256_add_epi32(z2,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+16)),bj));
z3=_mm256_add_epi32(z3,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+24)),bj));
z4=_mm256_add_epi32(z4,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+32)),bj));
z5=_mm256_add_epi32(z5,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+40)),bj));
z6=_mm256_add_epi32(z6,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+48)),bj));
z7=_mm256_add_epi32(z7,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+56)),bj));
}
for(size_t at=stop;at<groups.size();++at){const Group&g=groups[at];if(g.d+k0>=n)break;unsigned cnt=std::min(m-k0,n-g.d-k0);const u32*x=a+g.d+k0;__m256i bj=_mm256_set1_epi32(g.b);
#define MASKADD(V,Z) if(cnt>V*8){__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(cnt),_mm256_setr_epi32(V*8,V*8+1,V*8+2,V*8+3,V*8+4,V*8+5,V*8+6,V*8+7));Z=_mm256_add_epi32(Z,_mm256_mullo_epi32(_mm256_maskload_epi32((const int*)(x+V*8),mask),bj));}
MASKADD(0,z0)
MASKADD(1,z1)
MASKADD(2,z2)
MASKADD(3,z3)
MASKADD(4,z4)
MASKADD(5,z5)
MASKADD(6,z6)
MASKADD(7,z7)
#undef MASKADD
}
_mm256_storeu_si256((__m256i*)(c+k0+0),z0);
_mm256_storeu_si256((__m256i*)(c+k0+8),z1);
_mm256_storeu_si256((__m256i*)(c+k0+16),z2);
_mm256_storeu_si256((__m256i*)(c+k0+24),z3);
_mm256_storeu_si256((__m256i*)(c+k0+32),z4);
_mm256_storeu_si256((__m256i*)(c+k0+40),z5);
_mm256_storeu_si256((__m256i*)(c+k0+48),z6);
_mm256_storeu_si256((__m256i*)(c+k0+56),z7);
}
}
}
}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <immintrin.h>
namespace adaptive_mod {using u32=uint32_t;
inline void direct_range(unsigned n,const unsigned* __restrict a,const unsigned* __restrict b,unsigned* __restrict c,unsigned l,unsigned r){
if(n<64){for(unsigned j=l+1;j<std::min(r,n-l);++j)for(unsigned start=j;start+l<n;start+=j)for(unsigned k=l;k<std::min(r,std::min(j,n-start));++k)c[k]+=a[start+k]*b[j];return;}
for(unsigned j=l+1;j<std::min(r,65u);++j){u32 sum[64]={};for(unsigned start=j;start+l<n;start+=j){unsigned end=std::min(j,n-start);for(unsigned k=l;k<end;++k)sum[k]+=a[start+k];}for(unsigned k=l;k<j;++k)c[k]+=sum[k]*b[j];}
const unsigned limit=std::min(r,n/2+1),jlo=std::max(l+1,65u);if(jlo>=r)return;
for(unsigned k0=l;k0<limit;k0+=32){__m256i z[4],idx[4],endmask[4];for(unsigned v=0;v<4;++v){z[v]=_mm256_loadu_si256((const __m256i*)(c+k0+8*v));idx[v]=_mm256_setr_epi32(k0+8*v,k0+8*v+1,k0+8*v+2,k0+8*v+3,k0+8*v+4,k0+8*v+5,k0+8*v+6,k0+8*v+7);endmask[v]=_mm256_cmpgt_epi32(_mm256_set1_epi32(r),idx[v]);}
unsigned first=std::max(jlo,k0+1),first_full=std::max(jlo,k0+32),qmax=(n-1-k0)/first;
for(unsigned q=1;q<=qmax;++q){unsigned last=std::min(r-1,(n-1-k0)/q),full_last=std::min(r-1,(n-k0-32)/q),j=first;
for(;j<=last&&j<first_full;++j){__m256i bj=_mm256_set1_epi32(b[j]);unsigned start=q*j+k0;for(unsigned v=0;v<4;++v){__m256i mask=_mm256_and_si256(endmask[v],_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(j),idx[v]),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-q*j),idx[v])));__m256i x=start+8*v<n?_mm256_maskload_epi32((const int*)(a+start+8*v),mask):_mm256_setzero_si256();z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(x,bj));}}
for(;j<=full_last;++j){__m256i bj=_mm256_set1_epi32(b[j]);const u32*x=a+q*j+k0;for(unsigned v=0;v<4;++v){__m256i value=_mm256_loadu_si256((const __m256i*)(x+8*v));if(k0+32>r)value=_mm256_and_si256(value,endmask[v]);z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(value,bj));}}
for(;j<=last;++j){__m256i bj=_mm256_set1_epi32(b[j]);unsigned start=q*j+k0;for(unsigned v=0;v<4;++v){__m256i mask=_mm256_and_si256(endmask[v],_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(j),idx[v]),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-q*j),idx[v])));__m256i x=start+8*v<n?_mm256_maskload_epi32((const int*)(a+start+8*v),mask):_mm256_setzero_si256();z[v]=_mm256_add_epi32(z[v],_mm256_mullo_epi32(x,bj));}}
}
for(unsigned v=0;v<4;++v)_mm256_storeu_si256((__m256i*)(c+k0+8*v),z[v]);
}
}
}
#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace mod_karatsuba {
using u32=uint32_t;using u64=uint64_t;
// out[t] = sum_i a[i+t]*b[i], 0<=t<h. a has at least 2h words.
__attribute__((noinline)) inline void middle(const u32* __restrict a,const u32* __restrict b,u32* __restrict out,unsigned h,u32*scratch){
if(h<=32){
if(h<8){for(unsigned t=0;t<h;++t){u32 z=0;for(unsigned i=0;i<h;++i)z+=a[i+t]*b[i];out[t]=z;}return;}
for(unsigned t=0;t<h;t+=8){__m256i z=_mm256_setzero_si256();for(unsigned i=0;i<h;++i)z=_mm256_add_epi32(z,_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(a+i+t)),_mm256_set1_epi32(b[i])));_mm256_storeu_si256((__m256i*)(out+t),z);}return;
}
const unsigned s=h/2;u32*x=scratch,*y=x+h,*bs=y+h,*tmp=bs+s,*next=tmp+s;
for(unsigned i=0;i<h;++i){x[i]=a[i]-a[s+i];y[i]=a[h+i]-a[s+i];}
for(unsigned i=0;i<s;++i)bs[i]=b[i]+b[s+i];
middle(x,b,out,s,next);middle(y,b+s,out+s,s,next);middle(a+s,bs,tmp,s,next);
for(unsigned i=0;i<s;++i){out[i]+=tmp[i];out[s+i]+=tmp[i];}
}
__attribute__((noinline)) inline void cross(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned qlo=1,unsigned qhi=~0u){
const unsigned w=(r-l)/2,m=l+w,jend=std::min(r,n);if(!w||m>=jend||l+m>=n)return;
qhi=std::min(qhi,(n-1-l)/m);
for(unsigned q=qlo;q<=qhi;++q){unsigned wanted=std::min(w,n-q*m-l),h=1;while(h<(wanted+q-1)/q)h*=2;
std::vector<u32>bb(h),aa(2*h+8),z(h),scratch(6*h+32);
for(unsigned jb=m;jb<jend;jb+=h){unsigned count=std::min(h,jend-jb);std::fill(bb.begin(),bb.end(),0);std::copy(b+jb,b+jb+count,bb.data());
for(unsigned rho=0;rho<std::min(q,wanted);++rho){unsigned len=(wanted-1-rho)/q+1;u64 start=u64(q)*jb+l+rho;
for(unsigned i=0;i<2*h;++i){u64 at=start+u64(q)*i;aa[i]=at<n?a[at]:0;}
middle(aa.data(),bb.data(),z.data(),h,scratch.data());
for(unsigned t=0;t<len;++t)c[l+rho+q*t]+=z[t];
}
}
}
}
}
namespace mod_karatsuba {
}
namespace mod_karatsuba {
}
namespace mod_fused {
using mod_karatsuba::u32;using mod_karatsuba::u64;using mod_karatsuba::cross;
template<unsigned H>__attribute__((always_inline))inline void tiny_vec(const u32*a,const u32*b,u32*out){
__m256i z[H];for(unsigned t=0;t<H;++t)z[t]=_mm256_setzero_si256();for(unsigned i=0;i<H;++i){__m256i bb=_mm256_set1_epi32(b[i]);for(unsigned t=0;t<H;++t)z[t]=_mm256_add_epi32(z[t],_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(i+t))),bb));}for(unsigned t=0;t<H;++t)_mm256_storeu_si256((__m256i*)(out+8*t),z[t]);
}
__attribute__((always_inline))inline void fused8(const u32*a,const u32*b,u32*out){
__m256i z0=_mm256_setzero_si256(), z1=_mm256_setzero_si256(), z2=_mm256_setzero_si256(), z3=_mm256_setzero_si256(), z4=_mm256_setzero_si256(), z5=_mm256_setzero_si256(), z6=_mm256_setzero_si256(), z7=_mm256_setzero_si256();
for(unsigned i=0;i<4;++i){__m256i b0=_mm256_set1_epi32(b[i]),b1=_mm256_set1_epi32(b[4+i]),bs=_mm256_add_epi32(b0,b1);
{__m256i am=_mm256_loadu_si256((const __m256i*)(a+8*(4+i+0))),prod=_mm256_mullo_epi32(am,bs);
z0=_mm256_add_epi32(z0,prod);z4=_mm256_add_epi32(z4,prod);
z0=_mm256_add_epi32(z0,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(i+0))),am),b0));
z4=_mm256_add_epi32(z4,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(8+i+0))),am),b1));}
{__m256i am=_mm256_loadu_si256((const __m256i*)(a+8*(4+i+1))),prod=_mm256_mullo_epi32(am,bs);
z1=_mm256_add_epi32(z1,prod);z5=_mm256_add_epi32(z5,prod);
z1=_mm256_add_epi32(z1,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(i+1))),am),b0));
z5=_mm256_add_epi32(z5,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(8+i+1))),am),b1));}
{__m256i am=_mm256_loadu_si256((const __m256i*)(a+8*(4+i+2))),prod=_mm256_mullo_epi32(am,bs);
z2=_mm256_add_epi32(z2,prod);z6=_mm256_add_epi32(z6,prod);
z2=_mm256_add_epi32(z2,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(i+2))),am),b0));
z6=_mm256_add_epi32(z6,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(8+i+2))),am),b1));}
{__m256i am=_mm256_loadu_si256((const __m256i*)(a+8*(4+i+3))),prod=_mm256_mullo_epi32(am,bs);
z3=_mm256_add_epi32(z3,prod);z7=_mm256_add_epi32(z7,prod);
z3=_mm256_add_epi32(z3,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(i+3))),am),b0));
z7=_mm256_add_epi32(z7,_mm256_mullo_epi32(_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(8+i+3))),am),b1));}
}
_mm256_storeu_si256((__m256i*)(out+0),z0);
_mm256_storeu_si256((__m256i*)(out+8),z1);
_mm256_storeu_si256((__m256i*)(out+16),z2);
_mm256_storeu_si256((__m256i*)(out+24),z3);
_mm256_storeu_si256((__m256i*)(out+32),z4);
_mm256_storeu_si256((__m256i*)(out+40),z5);
_mm256_storeu_si256((__m256i*)(out+48),z6);
_mm256_storeu_si256((__m256i*)(out+56),z7);
}
__attribute__((noinline)) inline void middle_vec(const u32*a,const u32*b,u32*out,unsigned h,u32*scratch){
if(h==8){fused8(a,b,out);return;}
if(h<=4){if(h==1)tiny_vec<1>(a,b,out);else if(h==2)tiny_vec<2>(a,b,out);else tiny_vec<4>(a,b,out);return;}
unsigned s=h/2;u32*x=scratch,*y=x+8*h,*tmp=y+8*h,*bs=tmp+8*s,*next=bs+s;
for(unsigned i=0;i<h;++i){__m256i mid=_mm256_loadu_si256((const __m256i*)(a+8*(s+i)));_mm256_storeu_si256((__m256i*)(x+8*i),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*i)),mid));_mm256_storeu_si256((__m256i*)(y+8*i),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(a+8*(h+i))),mid));}
for(unsigned i=0;i<s;++i)bs[i]=b[i]+b[s+i];
middle_vec(x,b,out,s,next);middle_vec(y,b+s,out+8*s,s,next);middle_vec(a+8*s,bs,tmp,s,next);
for(unsigned i=0;i<s;++i){__m256i t=_mm256_loadu_si256((const __m256i*)(tmp+8*i));_mm256_storeu_si256((__m256i*)(out+8*i),_mm256_add_epi32(t,_mm256_loadu_si256((const __m256i*)(out+8*i))));_mm256_storeu_si256((__m256i*)(out+8*(s+i)),_mm256_add_epi32(t,_mm256_loadu_si256((const __m256i*)(out+8*(s+i)))));}
}
__attribute__((noinline)) inline void cross_vec(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned qlo=1,unsigned qhi=~0u){
const unsigned w=(r-l)/2,m=l+w,jend=std::min(r,n);if(!w||m>=jend||l+m>=n)return;
qhi=std::min(qhi,(n-1-l)/m);if(qlo<=7)cross(n,a,b,c,l,r,qlo,std::min(qhi,7u));qlo=std::max(8u,qlo);
for(unsigned q=qlo;q<=qhi;++q){unsigned wanted=std::min(w,n-q*m-l),h=1;while(h<(wanted+q-1)/q)h*=2;
std::vector<u32>bb(h),aa(16*h+8),z(8*h),scratch(48*h+32);unsigned jhi=std::min(jend,(n-1-l)/q+1);
for(unsigned jb=m;jb<jhi;jb+=h){unsigned count=std::min(h,jhi-jb);std::fill(bb.begin(),bb.end(),0);std::copy(b+jb,b+jb+count,bb.data());
for(unsigned rho=0;rho<std::min(q,wanted);rho+=8){u64 start=u64(q)*jb+l+rho;
for(unsigned i=0;i<2*h;++i){u64 at=start+u64(q)*i;__m256i v;if(at+8<=n)v=_mm256_loadu_si256((const __m256i*)(a+at));else if(at<n){unsigned rem=n-at;__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(rem),_mm256_setr_epi32(0,1,2,3,4,5,6,7));v=_mm256_maskload_epi32((const int*)(a+at),mask);}else v=_mm256_setzero_si256();_mm256_storeu_si256((__m256i*)(aa.data()+8*i),v);}
middle_vec(aa.data(),bb.data(),z.data(),h,scratch.data());
for(unsigned t=0;t<h;++t){unsigned k=rho+q*t;if(k>=wanted)break;unsigned rem=std::min(8u,std::min(q-rho,wanted-k));__m256i value=_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(c+l+k)),_mm256_loadu_si256((const __m256i*)(z.data()+8*t)));if(rem==8)_mm256_storeu_si256((__m256i*)(c+l+k),value);else{__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(rem),_mm256_setr_epi32(0,1,2,3,4,5,6,7));_mm256_maskstore_epi32((int*)(c+l+k),mask,value);}}
}
}
}
}
__attribute__((noinline)) inline void vec_triangle(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned cutoff=256){
if(r-l<=cutoff||2ull*l+1>=n){adaptive_mod::direct_range(n,a,b,c,l,r);return;}
unsigned w=(r-l)/2,m=l+w;vec_triangle(n,a,b,c,l,m,cutoff);vec_triangle(n,a,b,c,m,r,cutoff);cross_vec(n,a,b,c,l,r);
}
}
namespace current_native {
using u32=uint32_t;
// Exactly partition positive quotients; scalar residue Karatsuba remains inside
// mod_fused for q<8. Native D aggregation handles short middle products.
__attribute__((noinline))inline void mixed(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r){
if(r-l<=512||2ull*l+1>=n){adaptive_mod::direct_range(n,a,b,c,l,r);return;}
unsigned w=(r-l)/2,m=l+w;mixed(n,a,b,c,l,m);mixed(n,a,b,c,m,r);unsigned qmax=(n-1-l)/m;if(!qmax)return;unsigned cut=std::min(qmax,w/128);
if(cut)mod_fused::cross_vec(n,a,b,c,l,r,1,cut);
if(cut<qmax)mod_filtered::cross_filtered<2048>(n,a,b,c,l,r,cut+1,qmax);
}
inline void run(unsigned n,const u32*a,const u32*b,u32*c,unsigned l,unsigned r,unsigned method=0){
if(method==1){mod_count::direct_piece<2048>(n,a,b,c,l,r,r);return;}
if(method==2){mixed(n,a,b,c,l,r);return;}
if(method==3){mod_dynamicbits64::direct_piece<2048>(n,a,b,c,l,r,r);return;}
if(l==0&&r-l>=1024)mod_dynamicbits64::direct_piece<2048>(n,a,b,c,l,r,r);
else if(l>=65536&&r-l>=4096&&uint64_t(r-l)>=128ull*((n-1-l)/(l+1)))mixed(n,a,b,c,l,r);
else mod_count::direct_piece<2048>(n,a,b,c,l,r,r);
}
}
#pragma GCC push_options
#pragma GCC optimize("fp-contract=off")
#include <bits/stdc++.h>
namespace mod_plan_count {using u64=uint64_t;
inline u64 direct_count(unsigned n,unsigned l,unsigned r){u64 total=0,A=n-1-l,end=std::min<u64>(r-1,A);for(u64 j=l+1;j<=end;){u64 q=A/j,hi=std::min(end,A/q),cut=std::min(hi,u64(n)/(q+1));if(cut>=j){u64 count=cut-j+1;total+=q*((j+cut)*count/2-u64(l)*count);}u64 lo=std::max(j,cut+1);if(lo<=hi){u64 count=hi-lo+1;total+=count*(n-q*l)-(lo+hi)*count/2;}j=hi+1;}return total;}}
// Cost-model research only. No unmeasured model duration is acceptance evidence.
namespace calibrated_plan {
using u64=uint64_t;
enum Method{GROUPED=0,MERGED=1,TILED=2};
struct Cross{unsigned l,r;Method method;unsigned H=0;};struct Range{unsigned l,r;};
inline u64 term_count(unsigned n,unsigned k,unsigned first,unsigned last){u64 total=0,A=n-1-k,lastj=std::min<u64>(last,A);for(u64 j=first;j<=lastj;){u64 q=A/j,hi=std::min(lastj,A/q);total+=q*(hi-j+1);j=hi+1;}return total;}
// Upper bound on nonempty D tiles, exact whenever consecutive q*j differ <=H.
// Intervals from successive q are monotonically ordered, so union is linear in q.
inline u64 tile_cover(unsigned n,unsigned l,unsigned r,unsigned H){unsigned w=(r-l)/2,m=l+w,jlast=std::min(r-1,n-l-1);if(!w||m>jlast)return 0;u64 count=0,end=0;bool any=false;unsigned qmax=(n-1-l)/m;
for(unsigned q=1;q<=qmax;++q){u64 lo=u64(q)*m/H,hi=std::min<u64>(n-1-l,u64(q)*jlast)/H;if(!any||lo>end+1){count+=hi-lo+1;end=hi;any=true;}else if(hi>end){count+=hi-end;end=hi;}}
return count;
}
struct Costs{
double native_pair=1.157129381204629/12e9,native_record=0,group_unit=2.77e-9*1.0469382184428717,merge_unit=1.76e-9*1.063637380615047;
// Must be supplied from the actual tiled backend before interpreting seconds.
double tile_forward=30e-6,tile_inverse=49e-6,tile_record=0;
unsigned H=4096;
};
inline double tile_seconds(unsigned n,unsigned l,unsigned r,unsigned H,const Costs&cost){
unsigned w=(r-l)/2,m=l+w,wk=std::min(w,n-l-m),outputs=(l%H+wk+H-1)/H;double ratio=double(H)*__builtin_ctz(H)/(4096.*12),partial=1.;if(wk<=H/4){unsigned power=1;while(power<wk)power*=2;partial=.25+.75*std::max(4u,unsigned(__builtin_ctz(power)))/double(__builtin_ctz(2*H));}
double penalty=1.;if(H==16384){double density=double(w)/r;double refusal=density>=.38?1.:std::min(1.,3.*w/(n-l));double fallback=wk>H/2?2.2:1.28;penalty=1.+refusal*(fallback-1.);}
const double measured_scale[3]={1.3771538032523578,1.2382085846342463,1.4349022790994899};return tile_cover(n,l,r,H)*(30e-6*ratio+outputs*49e-6*ratio*partial)*penalty*measured_scale[__builtin_ctz(H)-12];
}
struct Plan{
unsigned n;Costs cost;std::vector<Range>direct;std::vector<Cross>cross;double estimate=0;
double build(unsigned l,unsigned r){if(r-l<2||2ull*l+1>=n)return 0;u64 native=mod_plan_count::direct_count(n,l,r);unsigned width=r-l,qrow=(n-1-l)/(l+1);double factor=(l==0&&width>=1024)||(l>=65536&&width>=4096&&uint64_t(width)>=128ull*qrow)?.68:1.;double nc=factor*native*cost.native_pair+cost.native_record*term_count(n,l,l+1,r-1);if(r-l<=64){direct.push_back({l,r});return nc;}
size_t ds=direct.size(),cs=cross.size();unsigned w=(r-l)/2,m=l+w;double child=build(l,m)+build(m,r);unsigned qmax=(n-1-l)/m;if(!qmax)return child;
double gu=0;for(unsigned lo=1;lo<=qmax;){unsigned len=8;while(len<u64(lo)*(w-1)+w)len*=2;unsigned hi=std::min(qmax,(len-w)/(w-1));gu+=double(hi-lo+3)/3.*len*__builtin_ctz(len);lo=hi+1;}
unsigned span=n-l-m,wk=std::min(w,span),len=8;while(len<u64(span)+wk-1)len*=2;double mg=double(len)*__builtin_ctz(len)*cost.merge_unit,gp=gu*cost.group_unit;
Method kind=gp<mg?GROUPED:MERGED;double xc=std::min(mg,gp);unsigned chosenH=0;
for(unsigned H:{4096u,8192u,16384u}){double tc=tile_seconds(n,l,r,H,cost);if(tc<xc){xc=tc;kind=TILED;chosenH=H;}}
if(nc<child+xc){direct.resize(ds);cross.resize(cs);direct.push_back({l,r});return nc;}
cross.push_back({l,r,kind,chosenH});return child+xc;
}
Plan(unsigned size,Costs model):n(size),cost(model){unsigned r=1;while(r<n)r*=2;estimate=build(0,r);}
};
// Uniform, seed-independent positive-integer coefficient bound for the subset
// of pairs assigned to the prime fields. TILED/native pairs are already mod32.
inline u64 field_pair_bound(unsigned n,const std::vector<Cross>&nodes){
std::vector<std::pair<unsigned,int64_t>>events;for(auto node:nodes){if(node.method==TILED)continue;unsigned m=node.l+(node.r-node.l)/2,end=std::min(m,n-m);if(end<=node.l)continue;u64 count=term_count(n,node.l,m,std::min(node.r-1,n-node.l-1));if(!count)continue;events.push_back({node.l,int64_t(count)});events.push_back({end,-int64_t(count)});}
std::sort(events.begin(),events.end());u64 best=0;int64_t value=0;for(size_t i=0;i<events.size();){unsigned at=events[i].first;while(i<events.size()&&events[i].first==at)value+=events[i++].second;assert(value>=0);best=std::max(best,u64(value));}return best;
}
// Exact maximum of the selected-field pair counts. Between any two start/end
// events the active node set is fixed and every floor((n-1-k)/j) decreases with
// k, hence an interval maximum occurs at its first event coordinate.
inline u64 field_pair_maximum(unsigned n,const std::vector<Cross>&nodes){
struct E{unsigned at,id;bool start;};std::vector<E>events;for(unsigned id=0;id<nodes.size();++id){auto node=nodes[id];if(node.method==TILED)continue;unsigned m=node.l+(node.r-node.l)/2,end=std::min(m,n-m);if(end<=node.l)continue;events.push_back({node.l,id,true});events.push_back({end,id,false});}
std::sort(events.begin(),events.end(),[](E a,E b){return a.at<b.at;});std::set<unsigned>active;u64 best=0;for(size_t i=0;i<events.size();){unsigned at=events[i].at;while(i<events.size()&&events[i].at==at){auto e=events[i++];if(e.start)active.insert(e.id);else active.erase(e.id);}u64 total=0;for(unsigned id:active){auto node=nodes[id];unsigned m=node.l+(node.r-node.l)/2;total+=term_count(n,at,m,node.r-1);}best=std::max(best,total);}return best;
}
}
#pragma GCC pop_options
#ifndef DUCK_SHA256_HPP
#define DUCK_SHA256_HPP
#include <stddef.h>
#include <stdint.h>
#include <string.h>
// Portable SHA-256; input is the exact byte sequence, with no native-word hashing.
namespace duck_sha256 {
static inline uint32_t rotate(uint32_t x,unsigned n) {return (x>>n)|(x<<(32-n));}
static void compress(uint32_t h[8],const unsigned char block[64]) {
static const uint32_t k[64]={
0x428a2f98u,0x71374491u,0xb5c0fbcfu,0xe9b5dba5u,0x3956c25bu,0x59f111f1u,0x923f82a4u,0xab1c5ed5u,
0xd807aa98u,0x12835b01u,0x243185beu,0x550c7dc3u,0x72be5d74u,0x80deb1feu,0x9bdc06a7u,0xc19bf174u,
0xe49b69c1u,0xefbe4786u,0x0fc19dc6u,0x240ca1ccu,0x2de92c6fu,0x4a7484aau,0x5cb0a9dcu,0x76f988dau,
0x983e5152u,0xa831c66du,0xb00327c8u,0xbf597fc7u,0xc6e00bf3u,0xd5a79147u,0x06ca6351u,0x14292967u,
0x27b70a85u,0x2e1b2138u,0x4d2c6dfcu,0x53380d13u,0x650a7354u,0x766a0abbu,0x81c2c92eu,0x92722c85u,
0xa2bfe8a1u,0xa81a664bu,0xc24b8b70u,0xc76c51a3u,0xd192e819u,0xd6990624u,0xf40e3585u,0x106aa070u,
0x19a4c116u,0x1e376c08u,0x2748774cu,0x34b0bcb5u,0x391c0cb3u,0x4ed8aa4au,0x5b9cca4fu,0x682e6ff3u,
0x748f82eeu,0x78a5636fu,0x84c87814u,0x8cc70208u,0x90befffau,0xa4506cebu,0xbef9a3f7u,0xc67178f2u};
uint32_t w[64];
for(unsigned i=0;i<16;++i)w[i]=(uint32_t(block[4*i])<<24)|(uint32_t(block[4*i+1])<<16)|(uint32_t(block[4*i+2])<<8)|block[4*i+3];
for(unsigned i=16;i<64;++i){uint32_t a=w[i-15],b=w[i-2];w[i]=w[i-16]+(rotate(a,7)^rotate(a,18)^(a>>3))+w[i-7]+(rotate(b,17)^rotate(b,19)^(b>>10));}
uint32_t a=h[0],b=h[1],c=h[2],d=h[3],e=h[4],f=h[5],g=h[6],v=h[7];
for(unsigned i=0;i<64;++i){
uint32_t t1=v+(rotate(e,6)^rotate(e,11)^rotate(e,25))+((e&f)^(~e&g))+k[i]+w[i];
uint32_t t2=(rotate(a,2)^rotate(a,13)^rotate(a,22))+((a&b)^(a&c)^(b&c));
v=g;g=f;f=e;e=d+t1;d=c;c=b;b=a;a=t1+t2;
}
h[0]+=a;h[1]+=b;h[2]+=c;h[3]+=d;h[4]+=e;h[5]+=f;h[6]+=g;h[7]+=v;
}
inline void digest(const void*data,size_t length,unsigned char out[32]) {
uint32_t h[8]={0x6a09e667u,0xbb67ae85u,0x3c6ef372u,0xa54ff53au,0x510e527fu,0x9b05688cu,0x1f83d9abu,0x5be0cd19u};
const unsigned char*p=(const unsigned char*)data;
size_t whole=length/64;
for(size_t i=0;i<whole;++i)compress(h,p+64*i);
unsigned char tail[128]={};size_t remain=length%64;
if(remain)memcpy(tail,p+64*whole,remain);
tail[remain]=0x80;size_t padded=remain<56?64:128;
uint64_t bits=uint64_t(length)*8;
for(unsigned i=0;i<8;++i)tail[padded-1-i]=(unsigned char)(bits>>(8*i));
compress(h,tail);if(padded==128)compress(h,tail+64);
for(unsigned i=0;i<8;++i)for(unsigned j=0;j<4;++j)out[4*i+j]=(unsigned char)(h[i]>>(24-8*j));
}
}
#endif
static uint64_t ticks(){_mm_lfence();return __rdtsc();}
struct PublicRng{uint64_t state;unsigned next(){uint64_t z=(state+=0x9e3779b97f4a7c15ULL);z=(z^(z>>30))*0xbf58476d1ce4e5b9ULL;z=(z^(z>>27))*0x94d049bb133111ebULL;return unsigned(z^(z>>31));}};
static void emit_sha(const unsigned*c,unsigned n){unsigned char h[32];duck_sha256::digest(c,size_t(n)*4,h);for(unsigned char x:h)printf("%02x",x);puts("");}
int main(){constexpr unsigned n=10000000,STAGE=1;std::vector<unsigned>a(n+64),b(n+64),c(n+64);auto t0=ticks();PublicRng ar{0x1357214865430012ULL},br{0x2143658730024589ULL};for(unsigned i=0;i<n;++i){a[i]=ar.next();b[i]=br.next();}auto t1=ticks();calibrated_plan::Plan plan(n,{});std::sort(plan.direct.begin(),plan.direct.end(),[](auto a,auto b){return a.l<b.l;});std::vector<double>prefix(1);for(auto r:plan.direct){unsigned width=r.r-r.l,q=(n-1-r.l)/(r.l+1);double f=(r.l==0&&width>=1024)||(r.l>=65536&&width>=4096&&uint64_t(width)>=128ull*q)?.68:1.;prefix.push_back(prefix.back()+f*mod_plan_count::direct_count(n,r.l,r.r)*plan.cost.native_pair);}unsigned split=std::lower_bound(prefix.begin(),prefix.end(),prefix.back()/2)-prefix.begin();unsigned lo=STAGE?split:0,hi=STAGE?plan.direct.size():split;auto t2=ticks();for(unsigned at=lo;at<hi;++at){auto r=plan.direct[at];current_native::run(n,a.data(),b.data(),c.data(),r.l,r.r);}auto t3=ticks();emit_sha(c.data(),n);auto t4=ticks();printf("G%llu P%llu R%llu H%llu jobs%u lo%u hi%u\n",(unsigned long long)(t1-t0),(unsigned long long)(t2-t1),(unsigned long long)(t3-t2),(unsigned long long)(t4-t3),hi-lo,lo,hi);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 7.107 s | 114 MB + 944 KB | Accepted | Score: 100 | 显示更多 |