OI XXX - nww (Online)

// https://szkopul.edu.pl/problemset/problem/N_oYus0VcBjsFD0qH-AEBw_h/site/?key=statement

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

constexpr int sizik = 100 * 1005;
constexpr int MAX_NODES = 20000000;

int n, q, M;

constexpr int MAX_V = 1000 * 1005;
int pr[MAX_V];
int prime_id[MAX_V];
int curr_id = 0;

void Sieve() {
    for (int i = 2; i < MAX_V; i++) {
        if (pr[i] == 0) {
            prime_id[i] = ++curr_id;
            for (int j = i; j < MAX_V; j += i) {
                if (pr[j] == 0) pr[j] = i;
            }
        }
    }
}

int pow_mod(int a, int b) {
    long long res = 1;
    long long base = a;
    while (b > 0) {
        if (b & 1) res = (res * base) % M;
        base = (base * base) % M;
        b >>= 1;
    }
    return res;
}

struct Node {
    int val;
    int hist;
    int mul;
    int add;
    int l, r;
};

Node pool[MAX_NODES];
int ptr = 1;

int new_node() {
    if (ptr >= MAX_NODES) return 0;
    return ptr++;
}

int copy_node(int src_idx) {
    if (ptr >= MAX_NODES) return 0;
    pool[ptr] = pool[src_idx];
    return ptr++;
}

std::vector<int> roots;

int apply_lazy(int idx, int m, int a) {
    int nw = copy_node(idx);

    long long v = pool[nw].val;
    long long h = pool[nw].hist;

    pool[nw].hist = (h + v * a) % M;
    pool[nw].val = (v * m) % M;

    long long old_m = pool[nw].mul;
    long long old_a = pool[nw].add;

    pool[nw].mul = (old_m * m) % M;
    pool[nw].add = (old_a + old_m * a) % M;

    return nw;
}

void build(int& v, int tl, int tr) {
    v = new_node();
    pool[v].mul = 1;
    pool[v].add = 0;

    if (tl == tr) {
        pool[v].val = 1;
        pool[v].hist = 0;
        pool[v].l = pool[v].r = 0;
    } else {
        int tm = (tl + tr) / 2;
        build(pool[v].l, tl, tm);
        build(pool[v].r, tm + 1, tr);

        long long lv = pool[pool[v].l].val;
        long long rv = pool[pool[v].r].val;
        long long lh = pool[pool[v].l].hist;
        long long rh = pool[pool[v].r].hist;

        pool[v].val = (lv + rv) % M;
        pool[v].hist = (lh + rh) % M;
    }
}

int update(int prev_node, int tl, int tr, int l, int r, int mul, int add) {
    if (l > r) return prev_node;

    if (l == tl && r == tr) {
        return apply_lazy(prev_node, mul, add);
    }

    int tm = (tl + tr) / 2;

    int curr = copy_node(prev_node);

    int pm = pool[curr].mul;
    int pa = pool[curr].add;

    if (pm != 1 || pa != 0) {
        pool[curr].l = apply_lazy(pool[curr].l, pm, pa);
        pool[curr].r = apply_lazy(pool[curr].r, pm, pa);
        pool[curr].mul = 1;
        pool[curr].add = 0;
    }

    pool[curr].l = update(pool[curr].l, tl, tm, l, std::min(r, tm), mul, add);
    pool[curr].r = update(pool[curr].r, tm + 1, tr, std::max(l, tm + 1), r, mul, add);

    long long lv = pool[pool[curr].l].val;
    long long rv = pool[pool[curr].r].val;
    long long lh = pool[pool[curr].l].hist;
    long long rh = pool[pool[curr].r].hist;

    pool[curr].val = (lv + rv) % M;
    pool[curr].hist = (lh + rh) % M;

    return curr;
}

int query(int idx, int tl, int tr, int l, int r, int passed_mul, int passed_add) {
    if (l > r) return 0;

    if (l == tl && r == tr) {
        long long h = pool[idx].hist;
        long long v = pool[idx].val;
        return (h + v * passed_add) % M;
    }

    int tm = (tl + tr) / 2;

    long long nm = pool[idx].mul;
    long long na = pool[idx].add;

    int next_mul = (nm * passed_mul) % M;
    int next_add = (na + nm * passed_add) % M;

    long long res = 0;
    res += query(pool[idx].l, tl, tm, l, std::min(r, tm), next_mul, next_add);
    res += query(pool[idx].r, tm + 1, tr, std::max(l, tm + 1), r, next_mul, next_add);

    return res % M;
}

struct StackItem {
    int exp, L, R;
};
std::vector<StackItem> st[MAX_V];
std::vector<std::pair<int, int>> factors[sizik];
int vals[sizik];

void solve() {
    std::cin >> n >> q >> M;
    Sieve();

    for (int i = 1; i <= n; i++) {
        std::cin >> vals[i];
        int x = vals[i];
        while (x > 1) {
            int p = pr[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            factors[i].push_back({p, cnt});
        }
    }

    int root = 0;
    build(root, 1, n);
    roots.push_back(root);

    int current_root = root;

    for (int i = 1; i <= n; i++) {
        for (auto& [p, cnt] : factors[i]) {
            int pid = prime_id[p];
            int p_pow = pow_mod(p, cnt);

            current_root = update(current_root, 1, n, i, i, p_pow, 0);

            int L_last = i;
            auto& s = st[pid];

            while (!s.empty()) {
                auto top = s.back();

                if (top.exp >= cnt) {
                    if (top.R + 1 < L_last) {
                        current_root = update(current_root, 1, n, top.R + 1, L_last - 1, p_pow, 0);
                    }
                    L_last = top.R + 1;
                    break;
                }

                if (top.R + 1 < L_last) {
                    current_root = update(current_root, 1, n, top.R + 1, L_last - 1, p_pow, 0);
                }

                int diff = cnt - top.exp;
                int mul = pow_mod(p, diff);
                current_root = update(current_root, 1, n, top.L, top.R, mul, 0);

                L_last = top.L;
                s.pop_back();
            }

            if (s.empty()) {
                if (1 < L_last) {
                    current_root = update(current_root, 1, n, 1, L_last - 1, p_pow, 0);
                }
                s.push_back({cnt, 1, i});
            } else {
                if (s.back().exp == cnt) {
                    s.back().R = i;
                } else {
                    s.push_back({cnt, L_last, i});
                }
            }
        }

        current_root = update(current_root, 1, n, 1, i, 1, 1);
        roots.push_back(current_root);
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        std::cout << query(roots[r], 1, n, l, r, 1, 0) << "\n";
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    solve();
    return 0;
}