OI XXX - nww

// 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 * 1001;

#define ar std::array

typedef std::vector<std::vector<int>> _kra;
typedef std::vector<std::pair<int, int>> D;
int n, q, M;

int vals[sizik];
D vals_D[sizik];

constexpr int MAX_V = 1000 * 1001;
constexpr int MAX_Q = 300 * 1001;
int pr[MAX_V + 1];
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;
                }
            }
        }
    }
}

D factor(int x) {
    D res;
    while (x > 1) {
        int curr = pr[x];
        int cnt = 0;
        while (curr == pr[x]) {
            cnt++;
            x /= pr[x];
        }
        res.push_back({curr, cnt});
    }
    return res;
}

int pow(int a, int b) {
    int w = 1;
    for (int i = 0; i < b; i++) {
        w *= a;
    }
    assert(1 <= w && w <= MAX_V);
    return w;
}

typedef std::pair<int, int> Query;
std::vector<Query> queries[sizik];
int ans[MAX_Q];

struct StackItem {
    int wykladnik, L, R;
    StackItem(int w = 0, int l = 0, int r = 0) : wykladnik(w), L(l), R(r) {}
};
std::stack<StackItem> st[sizik];

namespace seg_tree {

struct Node {
    int val, hist;
    Node(int v = 0, int h = 0) : val(v), hist(h) {}
};

struct Tag {
    int mul, add;
    Tag(int m = 0, int a = 0) : mul(m), add(a) {}
    inline bool active() const { return mul != 1 || add != 0; }
};

Node drz[4 * sizik];
Tag lazy[4 * sizik];

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

void build() {
    return build(1, 1, n);
}

void merge(Node& a, const Node& b, const Node& c) {
    a.val = b.val + c.val;
    if (a.val >= M) a.val -= M;
    a.hist = b.hist + c.hist;
    if (a.hist >= M) a.hist -= M;
}

void apply_tag(int v, int tl, int tr, const Tag& t) {
    drz[v].hist = ((int64_t)drz[v].hist + (int64_t)drz[v].val * (int64_t)t.add) % M;
    drz[v].val = ((int64_t)drz[v].val * (int64_t)t.mul) % M;

    int old_mul = lazy[v].mul;
    lazy[v].mul = ((int64_t)lazy[v].mul * (int64_t)t.mul) % M;
    lazy[v].add = ((int64_t)lazy[v].add + (int64_t)old_mul * (int64_t)t.add) % M;
}

void push(int v, int tl, int tr) {
    if (lazy[v].active()) {
        int tm = (tl + tr) / 2;
        apply_tag(2 * v, tl, tm, lazy[v]);
        apply_tag(2 * v + 1, tm + 1, tr, lazy[v]);
        lazy[v] = {1, 0};
    }
}

void set_leaf(int v, int tl, int tr, int idx, int val) {
    if (tl == tr) {
        drz[v] = {val, 0};
        lazy[v] = {1, 0};
    } else {
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        if (idx <= tm) {
            set_leaf(2 * v, tl, tm, idx, val);
        } else {
            set_leaf(2 * v + 1, tm + 1, tr, idx, val);
        }
        merge(drz[v], drz[2 * v], drz[2 * v + 1]);
    }
}

void set_leaf(int idx, int val) {
    return set_leaf(1, 1, n, idx, val);
}

void update(int v, int tl, int tr, int l, int r, int val, int a) {
    if (l > r) return;
    if (tl == l && tr == r) {
        apply_tag(v, tl, tr, {val, a});
        return;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, std::min(r, tm), val, a);
    update(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r, val, a);
    merge(drz[v], drz[2 * v], drz[2 * v + 1]);
}

void update_mult(int l, int r, int val) {
    return update(1, 1, n, l, r, val, 0);
}

void update_hist(int l, int r) {
    return update(1, 1, n, l, r, 1, 1);
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (tl == l && tr == r) {
        return drz[v].hist;
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    int res = query(2 * v, tl, tm, l, std::min(tm, r));
    res += query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
    if (res >= M) res -= M;
    return res;
}

int query(int l, int r) {
    return query(1, 1, n, l, r);
}

} // namespace seg_tree

void solve() {
    std::cin >> n >> q >> M;
    Sieve();
    for (int i = 1; i <= n; i++) {
        std::cin >> vals[i];
        vals_D[i] = factor(vals[i]);
    }

    for (int i = 1; i <= q; i++) {
        int l, r;
        std::cin >> l >> r;
        queries[r].push_back({l, i});
    }

    seg_tree::build();
    for (int i = 1; i <= n; i++) {
        seg_tree::set_leaf(i, 1);

        for (const auto& [p, cnt] : vals_D[i]) {
            seg_tree::update_mult(i, i, pow(p, cnt));

            int L_last = i;
            while (!st[prime_id[p]].empty()) {
                auto top = st[prime_id[p]].top();
                if (top.wykladnik >= cnt) {
                    if (top.R + 1 < L_last) {
                        seg_tree::update_mult(top.R + 1, L_last - 1, pow(p, cnt));
                    }
                    L_last = top.R + 1;
                    break;
                }
                if (top.R + 1 < L_last) {
                    seg_tree::update_mult(top.R + 1, L_last - 1, pow(p, cnt));
                }
                seg_tree::update_mult(top.L, top.R, pow(p, cnt - top.wykladnik));

                L_last = top.L;
                st[prime_id[p]].pop();
            }
            if (st[prime_id[p]].empty()) {
                if (1 < L_last) {
                    seg_tree::update_mult(1, L_last - 1, pow(p, cnt));
                }
                st[prime_id[p]].push({cnt, 1, i});
            } else {
                if (st[prime_id[p]].top().wykladnik == cnt) {
                    st[prime_id[p]].top().R = i;
                } else {
                    st[prime_id[p]].push({cnt, L_last, i});
                }
            }
        }

        seg_tree::update_hist(1, i);

        for (const auto& [l, idx] : queries[i]) {
            ans[idx] = seg_tree::query(l, i);
        }
    }

    for (int i = 1; i <= q; i++) {
        std::cout << ans[i] << '\n';
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}