MLE 80 pts，#2 #10 过不去。

悬关 qwq。

已经卡了一早上了，求调。

#include<bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

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;
}

void openFile() {
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
}

void fastio() {
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
}

void init() {
//	openFile();
	fastio();
}

const int N = 6e5 + 10;
const int M = 2e7 + 10;

struct ST {	
	
	int lg[N], n, F[20][N];
	
	void init(int x) {
		n = x;
		L(i, 2, n) lg[i] = lg[i>>1]+1;
		L(i, 1, lg[n]) L(j, 1, n) F[i][j] = max(F[i-1][j], F[i-1][j+(1<<i-1)]);
	}
	
	int query(int l, int r) {
		int k = lg[r-l+1];
		return max(F[k][l], F[k][r-(1<<k)+1]);
	}
	
}st;

struct block {
	
	int a[M], sz, bel[M], pos[M], pre[M], suf[M], n, id;
	
	ll F[M];
	
	void buildST() {
		int cur = 0, id = 1;
		pos[0] = -1;
		L(i, 1, n) {
			st.F[0][id] = max(st.F[0][id], a[i]);
			bel[i] = id;
			if(bel[i] != bel[i-1])
			  pos[i] = 0;
			else 
			  pos[i] = pos[i-1] + 1;
			if(++cur == sz)
			  cur = 0, id++;
		}
		if(n % sz == 0) id--;
		st.init(id);
	}
	
	void buildSubPre() {
		L(i, 1, n)
		  if(bel[i] != bel[i-1])
		   pre[i] = a[i];
		  else 
		   pre[i] = max(pre[i-1], a[i]);
		R(i, n, 1)
		  if(bel[i] != bel[i+1])
		   suf[i] = a[i];
		  else 
		   suf[i] = max(suf[i+1], a[i]);
	}
	
	void buildBlock() {
		static int s[100], tp;
		L(i, 1, n) {
			if(bel[i] != bel[i-1]) {
				tp = 0;
			}
			else F[i] = F[i-1];
			while(tp && a[s[tp]] <= a[i]) F[i] &= ~(1ull << pos[s[tp--]]);
			s[++tp] = i;
			F[i] |= (1ull << pos[i]);
		}
	}
	
	void init() {
		L(i, 1, n) a[i] = read();
		sz = log2(n)*1.5;
		buildST();
		buildSubPre();
		buildBlock();
		
	}
	
	int qmx(int l, int r) {
		int bl = bel[l], br = bel[r];
		if(bl != br) {
			int ans1 = 0, ans2 = 0;
			if(br - bl > 1) ans1 = st.query(bl+1, br-1);
			ans2 = max(suf[l], pre[r]);
			return max(ans1, ans2);
		}
		else 
		  return a[l + __builtin_ctz(F[r] >> pos[l])];
	}
}R;

int m, s;
void Main() {
	cin >> R.n >> m >> s;
	srand(s);
	R.init();
	unsigned ll ans = 0;
	int l, r;
	while(m--) {
		l = read() % R.n + 1;
		r = read() % R.n + 1;
		if(l > r) swap(l, r);
		ans += R.qmx(l, r);
	}
	cout << ans << '\n';
}

signed main() {
	init();
	int T = 1;
	while(T--)
	  Main();
	return 0;
}