跪求卡常!

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define Re register
#define K (2048)
#define ULL unsigned long long
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
#define MN 20000005
unsigned int st[K][MN/K+3],Log[MN],pre[MN],nex[MN],loc[MN],a[MN],s,l,r,res;
int LOG[26]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,20000001};
ULL ans;
int n,m,T;
inline int Max(unsigned a,unsigned b){return a>b?a:b;}
inline void build(){
    for(Re int i=1;i<=n;++i)loc[i]=(i-1)/K+1;
    for(Re int i=1;i<=n;++i)
        pre[i]=(loc[i]!=loc[i-1])?a[i]:Max(pre[i-1],a[i]);
    for(Re int i=n;i>0;--i)
        nex[i]=(loc[i]!=loc[i+1])?a[i]:Max(nex[i+1],a[i]);
    for(Re int i=1;i<=T;++i)st[0][i]=pre[i*K];
    for(Re int l=1;LOG[l]<=T;++l)
        for(Re int i=1;i+LOG[l]<=T;++i)
            st[l][i]=Max(st[l-1][i],st[l-1][i+(1<<(l-1))]);
}
int vis;
inline void rmq(int l,int r){
    if(loc[l]==loc[r]){
        res=a[l];
        for(Re int i=l+1;i<=r;++i)if(res<a[i])res=a[i];
        return;
    }
    res=(nex[l]<pre[r])?pre[r]:nex[l];
    int L=loc[l]+1,R=loc[r]-1;
    if(L>R)return;
    int k=Log[R-L+1];
    if(res<st[k][L])res=st[k][L];
    if(res<st[k][R-LOG[k]+1])res=st[k][R-LOG[k]+1];
}
int main(){
    freopen("3793.in","r",stdin);
    freopen("3793.out","w",stdout);
    scanf("%d%d%u",&n,&m,&s);T=n/K+1;
    double start=clock();
    int now=0,x=1;
    while(LOG[now]<T){
        ++now;
        for(Re int i=x;i<LOG[now];++i)Log[i]=now-1;
        x=LOG[now];
    }
    srand(s);
    for(Re int i=1;i<=n;++i)a[i]=read();
    build();
    for(Re int i=1;i<=m;++i){
        Re int l=read()%n+1,r=read()%n+1;
        if(r<l)std::swap(l,r);
        rmq(l,r);
    ans+=res;
    }
    printf("%llu\n",ans);
    double endT=clock();    cout<<"take "<<(endT-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl;
 // cout<<"VIS: "<<vis<<endl;
    return 0;
}