OI XXX - nww (Online_mle)

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

#include <bits/stdc++.h>

// #define GARY_DBG
#define GARY_LIB

#define int int64_t

constexpr int sizik = 100 * 1005;

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) {
    int res = 1;
    a %= M;
    while (b > 0) {
        if (b & 1) res = (res * a) % M;
        a = (a * a) % M;
        b >>= 1;
    }
    return res;
}

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

std::vector<Node> drz[4 * sizik];
std::vector<int> roots;

int make_node(int v, Node n) {
    drz[v].push_back(n);
    return drz[v].size() - 1;
}

int apply_lazy(int v, int prev_idx, int m, int a) {
    if (m == 1 && a == 0) return prev_idx;

    Node old = drz[v][prev_idx];
    Node nw = old;

    nw.hist = (old.hist + old.val * a) % M;
    nw.val = (old.val * m) % M;

    nw.mul = (old.mul * m) % M;
    nw.add = (old.add + old.mul * a) % M;

    return make_node(v, nw);
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        drz[v].push_back({1, 0, 1, 0, -1, -1});
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);

        int l_val = drz[2 * v][0].val;
        int r_val = drz[2 * v + 1][0].val;
        int l_hist = drz[2 * v][0].hist;
        int r_hist = drz[2 * v + 1][0].hist;

        drz[v].push_back({(l_val + r_val) % M, (l_hist + r_hist) % M, 1, 0, 0, 0});
    }
}

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

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

    int tm = (tl + tr) / 2;
    Node prev_node = drz[v][prev_idx];

    int pushed_l = apply_lazy(2 * v, prev_node.l, prev_node.mul, prev_node.add);
    int pushed_r = apply_lazy(2 * v + 1, prev_node.r, prev_node.mul, prev_node.add);

    int new_l = update(2 * v, tl, tm, l, std::min(r, tm), mul, add, pushed_l);
    int new_r = update(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, mul, add, pushed_r);

    Node curr;
    curr.l = new_l;
    curr.r = new_r;
    curr.mul = 1;
    curr.add = 0;

    int val_l = drz[2 * v][new_l].val;
    int val_r = drz[2 * v + 1][new_r].val;
    int hist_l = drz[2 * v][new_l].hist;
    int hist_r = drz[2 * v + 1][new_r].hist;

    curr.val = (val_l + val_r) % M;
    curr.hist = (hist_l + hist_r) % M;

    return make_node(v, curr);
}

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

    Node curr = drz[v][idx];

    if (l == tl && r == tr) {
        return curr.hist;
    }

    int tm = (tl + tr) / 2;

    int child_l_idx = curr.l;
    int child_r_idx = curr.r;

    if (curr.mul != 1 || curr.add != 0) {
        child_l_idx = apply_lazy(2 * v, child_l_idx, curr.mul, curr.add);
        child_r_idx = apply_lazy(2 * v + 1, child_r_idx, curr.mul, curr.add);
    }

    int res = 0;
    res = (res + query(2 * v, tl, tm, l, std::min(r, tm), child_l_idx)) % M;
    res = (res + query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, child_r_idx)) % M;

    return res;
}

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

    build(1, 1, n);
    roots.push_back(0);

    for (int i = 1; i <= n; i++) {
        int current_root = roots.back();

        for (auto& [p, cnt] : factors[i]) {
            int pid = prime_id[p];

            int p_pow = pow_mod(p, cnt);
            current_root = update(1, 1, n, i, i, p_pow, 0, current_root);

            int L_last = i;

            auto& s = st[pid];
            while (!s.empty()) {
                auto top = s.back();

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

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

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

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

            if (s.empty()) {
                if (1 < L_last) {
                    current_root = update(1, 1, n, 1, L_last - 1, p_pow, 0, current_root);
                }
                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(1, 1, n, 1, i, 1, 1, current_root);

        roots.push_back(current_root);
    }

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

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