Segtree2k17

#include <iostream>
#include <cmath>

using namespace std;

const int MAXN = 1111 * 1111;
long long a[MAXN];
long long mod;

unsigned s;
unsigned getNext(){
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}

long long addMod(long long a, long long b){
    a += b;
    if(a >= mod)
        a -= mod;
    return a;
}


long long mulMod(long long a, long long b){
    long long res = 0;
    a %= mod;
    while(b){
        if(b & 1LL) {
            res = addMod(res, a);
        }
        a = addMod(a, a);
        b /= 2;
    }
    return res;
}
int n, numblocks;
long long t[2 * MAXN];
long long BLOCK_SIZE = 1000;
long long bval[1111];
long long sqpre[1111][1111];
long long suff[1111][1111];
long long pref[1111][1111];

void build() {
    for (int i = n - 1; i > 0; --i) t[i] =  mulMod( t[i << 1], t[i << 1 | 1]);
}

void sqrtbuild() {
    numblocks = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
    for (int i = 0; i < numblocks; i++) bval[i] = 1;
    for(int i = 0; i < numblocks; i++)
        for(int j= 0; j < numblocks; j++)
            suff[i][j] = sqpre[i][j] = pref[i][j] = 1;

    for (int i = 0; i < n; i++) {
        bval[i / BLOCK_SIZE] = mulMod(bval[i / BLOCK_SIZE], t[i + n]);
    }
    for (int blockind = 0; blockind < numblocks; blockind++) {
        for (int i = 0; i < BLOCK_SIZE; i++) {
            int ind = blockind * BLOCK_SIZE + i;
            if (ind >= n) continue;
            pref[blockind][i] = t[ind + n];
            if (i > 0)
                pref[blockind][i] = mulMod(pref[blockind][i], pref[blockind][i - 1]);
        }
        for (int i = BLOCK_SIZE - 1; i >= 0; i--) {
            int ind = blockind * BLOCK_SIZE + i;
            if (ind >= n) continue;
            suff[blockind][i] = t[ind + n];
            if (i != BLOCK_SIZE - 1)
                suff[blockind][i] = mulMod( suff[blockind][i], suff[blockind][i + 1]);
        }
    }
    for (int i = 0; i < numblocks; i++) {
        sqpre[i][i] = bval[i];
        for (int j = i + 1; j < numblocks; j++) {
            sqpre[i][j] = mulMod(sqpre[i][j - 1], bval[j]);
        }
    }
}


inline long long segment_tree_query(int l, int r) {
    r++;
    long long res = 1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = mulMod(res, t[l++]);
        if (r & 1) res = mulMod(res, t[--r]);
    }
    return res;
}

inline long long query(int l, int r) {
    int leftq = l / BLOCK_SIZE, rightq = r / BLOCK_SIZE;
    if (leftq == rightq) {
        return segment_tree_query(l, r);
    }
    long long ans = 1;
    ans = suff[leftq][l % BLOCK_SIZE];
    ans = mulMod(ans, pref[rightq][r % BLOCK_SIZE]);
    if (leftq + 1 > rightq - 1)
        return ans;
    ans = mulMod(ans, sqpre[leftq + 1][rightq - 1]);
    return ans;
}


int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL

    unsigned m, seed ;
    cin >> n >> m >> mod >> seed;
    s = seed;
    for(int i = 0; i < n; i++){
        a[i] = getNext();
    }

    BLOCK_SIZE = sqrt(n) + 2;
    for (int i = 0; i < 2 * MAXN; i++) t[i] = 1;
    for (int i = 0; i < n; i++) t[i + n] = a[i];
    build();
    sqrtbuild();


    long long ans = 0;
    unsigned left = 0;
    unsigned right = 0;
    for(int i = 0; i < m; i++){
        left = getNext() % n;
        right = getNext() % n;
        if(left > right) swap(left, right);

        long long result = query(left, right) % mod;
        ans = (ans + result) % mod;
    }

    cout << ans;

    return 0;
}