萌新刚学OI，求卡常

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int MAXN=20000001;
int a[MAXN],s1[150001][200],s2[150001][200],st[150001][25],x[MAXN];
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;
}
int main(){
    int i,j,n,m,s,llen,l,r;unsigned long long sum=0;
    scanf("%d %d %d",&n,&m,&s);
    srand(s);
    for(i=1;i<=n;i++)a[i]=read();
    llen=8*(log2(n));
    for(i=1;i<=(n-1)/llen+1;i++){
      for(j=1;j<=llen;j++)s1[i][j]=max(s1[i][j-1],a[(i-1)*llen+j]);
      for(j=llen;j>=1;j--)s2[i][j]=max(s2[i][j+1],a[(i-1)*llen+j]);
      st[i][0]=s1[i][llen];
    }
    for(i=1;i<=log2(n);i++)
      for(j=1;j<=(n-1)/llen-(1<<i)+2;j++)st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    int y=1;x[1]=0;
    for(i=2;i<=(n-1)/llen+1;i++){x[i]=x[i-1];if(i==2*y){y*=2;x[i]++;}}
    for(i=1;i<=m;i++){
      l=read()%n+1;r=read()%n+1;
      if(l>r){y=r;r=l;l=y;}
      int p=(l-1)/llen+1,q=(r-1)/llen+1,ans=0;
      if(p==q)for(j=l;j<=r;j++)ans=max(ans,a[j]);
      else{
        ans=max(s2[p][l-(p-1)*llen],s1[q][r-(q-1)*llen]);
        if(q>p+1)ans=max(ans,max(st[p+1][x[q-p-1]],st[q-(1<<(x[q-p-1]))][x[q-p-1]]));
      }
      sum+=ans;
    }
    printf("%lld",sum);
}