HW3D

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int start_period (vector <unsigned int> const & a, int N, int L) {
    unsigned int length = 0;
    int i, j;
    for (i = 0; i < L; i++) {
        for (j = i + 1; j < L ; j++) {
            if (i >= N || j >= N)
                break;
            if (a[j] == a[i])
                goto DoubleBreak;
        }
    }
    return -1;
DoubleBreak:
    if (i == 0) return 0;
    return i;
}

int period_length (vector <unsigned int> const & a, int N, int L) {
    int start = start_period(a, N, L);

    unsigned int length = 0;
    int i, j;
    for (i = 0; i < L; i++) {
        for (j = i + 1; j < L ; j++) {
            if (i >= N || j >= N)
                break;
            if (a[j] == a[i])
                goto DoubleBreak;
        }
    }
DoubleBreak:

    return j - i;
}

int plain_sum (vector <unsigned int> & a, int N, int L) {
    int sum = 0;
    bool odd = true;

    sort(a.begin(), a.end());
    for (int n = 0; n < N; n++) {
        if (odd) {
            sum += a[n] % L;
            odd = false;
        }
        else odd = true;
    }
    return sum % L;
}

int fast_sum (vector <unsigned int> const & a, int N, int L) {
    int length = period_length(a, N, L);

    vector <unsigned int> period(length);
    for (int i = 0; i < length; i++)
        period[i] = a[i];

    sort(period.begin(), period.end());

    unsigned int num_periods = N / length;
    unsigned int period_remainder = N % length;

    int sum = 0;
    bool odd = true;
    for (int j = 0; j < period_remainder; j++) {
        if (odd && (num_periods + 1) % 2) {
            odd = false;
            sum += ((num_periods + 1) / 2 + 1) * period[j] % L;
        }
        else if (!odd && (num_periods + 1) % 2) {
            odd = true;
            sum += ((num_periods + 1) / 2) * period[j] % L;
        }
        else if (!((num_periods + 1) % 2)) {
            sum += ((num_periods + 1) / 2) * period[j] % L;
        }
    }
    for (int j = period_remainder; j < length; j++) {
        if (odd && num_periods % 2) {
            odd = false;
            sum += (num_periods / 2 + 1) * period[j] % L;
        }
        else if (!odd && num_periods % 2) {
            odd = true;
            sum += (num_periods / 2) * period[j] % L;
        }
        else if (!(num_periods % 2)) {
            sum += (num_periods / 2) * period[j] % L;
        }
    }
    return sum % L;
}

int fast_sum_with_preperiod (vector <unsigned int> const & a, int N, int L) {
    int start = start_period(a, N, L);
    int length = period_length(a, N, L);

    vector <unsigned int> preperiod(start);
    for (int i = 0; i < start; i++)
        preperiod[i] = a[i];

    vector <unsigned int> period(length);
    for (int i = 0; i < length; i++)
        period[i] = a[i + start];

    sort(preperiod.begin(), preperiod.end());
    sort(period.begin(), period.end());

    unsigned int num_periods = (N - start) / length;
    unsigned int period_remainder = (N - start) % length;

    int sum = 0;
    bool odd = true;
    int i = 0, j = 0;
    while (i < start && j < length) {
        if (preperiod[i] < period[j]) {
            if (odd) {
                odd = false;
                sum += preperiod[i] % L;
                i++;
            }
            else {
                odd = true;
                i++;
            }
        }
        else if (preperiod[i] > period[j]) {
            if (j < period_remainder) {
                if (odd && (num_periods + 1) % 2) {
                    odd = false;
                    sum += ((num_periods + 1) / 2 + 1) * period[j] % L;
                    j++;
                }
                else if (!odd && (num_periods + 1) % 2) {
                    odd = true;
                    sum += ((num_periods + 1) / 2) * period[j] % L;
                    j++;
                }
                else if (!((num_periods + 1) % 2)) {
                    sum += ((num_periods + 1) / 2) * period[j] % L;
                    j++;
                }
            }
            else if (j >= period_remainder) {
                if (odd && num_periods % 2) {
                    odd = false;
                    sum += (num_periods / 2 + 1) * period[j] % L;
                    j++;
                }
                else if (!odd && num_periods % 2) {
                    odd = true;
                    sum += (num_periods / 2) * period[j] % L;
                    j++;
                }
                else if (!(num_periods % 2)) {
                    sum += (num_periods / 2) * period[j] % L;
                    j++;
                }
            }
        }
        else if (preperiod[i] = period[j]) {
            if (j < period_remainder) {
                if (odd && (num_periods + 2) % 2) {
                    odd = false;
                    sum += ((num_periods + 2) / 2 + 1) * period[j] % L;
                    i++; j++;
                }
                else if (!odd && (num_periods + 2) % 2) {
                    odd = true;
                    sum += ((num_periods + 2) / 2) * period[j] % L;
                    i++; j++;
                }
                else if (!((num_periods + 2) % 2)) {
                    sum += ((num_periods + 2) / 2) * period[j] % L;
                    i++; j++;
                }
            }
            else if (j >= period_remainder) {
                if (odd && (num_periods + 1) % 2) {
                    odd = false;
                    sum += ((num_periods + 1) / 2 + 1) * period[j] % L;
                    i++; j++;
                }
                else if (!odd && (num_periods + 1) % 2) {
                    odd = true;
                    sum += ((num_periods + 1) / 2) * period[j] % L;
                    i++; j++;
                }
                else if (!((num_periods + 1) % 2)) {
                    sum += ((num_periods + 1) / 2) * period[j] % L;
                    i++; j++;
                }
            }
        }
    }

    for (i; i < start; i++) {
        if (odd) {
            odd = false;
            sum += preperiod[i] % L;
        }
        else odd = true;
    }

    for (j; j < length; j++) {
        if (j < period_remainder) {
            if (odd && (num_periods + 1) % 2) {
                odd = false;
                sum += ((num_periods + 1) / 2 + 1) * period[j] % L;
            }
            else if (!odd && (num_periods + 1) % 2) {
                odd = true;
                sum += ((num_periods + 1) / 2) * period[j] % L;
            }
            else if (!((num_periods + 1) % 2)) {
                sum += ((num_periods + 1) / 2) * period[j] % L;
            }
        }
        else {
            if (odd && num_periods % 2) {
                odd = false;
                sum += (num_periods / 2 + 1) * period[j] % L;
            }
            else if (!odd && num_periods % 2) {
                odd = true;
                sum += (num_periods / 2) * period[j] % L;
            }
            else if (!(num_periods % 2)) {
                sum += (num_periods / 2) * period[j] % L;
            }
        }
    }
    return sum % L;
}

int main()
{
    unsigned int K;
    int N, M, L, sum;
    cin >> N >> K >> M >> L;

    vector <unsigned int> a(N);
    a[0] = K;

    for (int i = 0; i < N - 1; i++)
        a[i + 1] = (unsigned int)((a[i] * (unsigned long long)M) & 0xFFFFFFFFU) % L;

    /*for (int i = 0; i < N; i++)
        cout << a[i] << ' ';
    cout << endl;  */

    int start = start_period(a, N, L);
    if (start == -1) {
        sum = plain_sum(a, N, L);
        cout << sum;
        return 0;
    }

    if (start == 0) {
        sum = fast_sum (a, N, L);
        cout << sum;
        return 0;
    }

    sum = fast_sum_with_preperiod(a, N, L);
    cout << sum;
    return 0;
}