void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII> > heap;
heap.push({0,1});
while(heap.size()){
int t=heap.top().second;
heap.pop();
if(st[t]) continue;
st[t]=true;
for (int i=h[t];~i;i=ne[i]){
int j=e[i];
if (dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
heap.push({dist[j],j});
}
}
}
return dist[n];
}
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void eval(node &root,int add,int mul)
{
root.sum=root.sum*mul+(root.r-root.l+1)*add;
root.mul=root.mul*mul;
root.add=root.add*mul+add;
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u]={l,l,a[l],0,1};
}
else
{
tr[u]={l,r,0,0,1};
int mid= l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void pushdown(int u)
{
eval(tr[u<<1],tr[u].add,tr[u].mul);
eval(tr[u<<1|1],tr[u].add,tr[u].mul);
tr[u].add=0;
tr[u].mul=1;
}
void modify(int u,int l,int r,int add,int mul)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
eval(tr[u],add,mul);
}
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
modify(u<<1,l,r,add,mul);
if(r>mid)
modify(u<<1|1,l,r,add,mul);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
return tr[u].sum;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int ans=0;
if(l<=mid)
{
ans=query(u<<1,l,r);
}
if(r>mid)
{
ans=ans+query(u<<1|1,l,r);
}
return ans;
}
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}