#include <bits/stdc++.h>
using namespace std;
vector<int> primes(int n) {
  vector<int> ret;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n != 1) {
    ret.push_back(n);
  }
  return ret;
}
int phi(int n) {
  auto ps = primes(n);
  int ans = 1;
  for (int p : ps) {
    ans *= p - 1;
    n /= p;
    while (n % p == 0) {
      ans *= p;
      n /= p;
    }
  }
  return ans;
}
long long fpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n % 2 == 1) {
      res *= a;
      res %= mod;
    }
    a *= a;
    a %= mod;
    n /= 2;
  }
  return res;
}
const int max_pow = 2e6 + 179;
class segment_tree {
  int n, m, mphi;
  vector<int> m_primes;
  vector<array<int, max_pow>> pp;
  vector<int> t;
  vector<vector<int>> make_pair;
  vector<int> mod;
  vector<vector<int>> mod_mp;
  int get_sum(int v, int L, int R) {
    long long ans = t[v];
    ans = (ans * mod[v]) % m;
    vector<int>& w = (L == R - 1 ? make_pair[L] : mod_mp[v]);
    for (int i = 0; i < (int)(m_primes.size()); i++) {
      ans *= pp[i][w[i]];
      ans %= m;
    }
    return ans;
  }
  void update(int v, int L, int R) {
    t[v] = (get_sum(2 * v + 1, L, (L + R) / 2) +
            get_sum(2 * v + 2, (L + R) / 2, R)) %
           m;
  }
  void change_v(int v, int L, int R, int x, const vector<int>& xmp) {
    vector<int>& to_add = (L == R - 1 ? make_pair[L] : mod_mp[v]);
    for (int i = 0; i < (int)(m_primes.size()); i++) {
      to_add[i] += xmp[i];
    }
    if (L == R - 1) {
      t[v] = (1ll * t[v] * x) % m;
    } else {
      mod[v] = (1ll * mod[v] * x) % m;
    }
  }
  void push(int v, int L, int R) {
    change_v(2 * v + 1, L, (L + R) / 2, mod[v], mod_mp[v]);
    change_v(2 * v + 2, (L + R) / 2, R, mod[v], mod_mp[v]);
    mod[v] = 1;
    mod_mp[v].assign(m_primes.size(), 0);
    update(v, L, R);
  }
  void build(int v, int L, int R, const vector<int>& a) {
    mod[v] = 1;
    if (L == R - 1) {
      make_pair[L].resize(m_primes.size());
      t[v] = a[L];
      for (int i = 0; i < (int)(m_primes.size()); i++) {
        int p = m_primes[i];
        while (t[v] % p == 0) {
          t[v] /= p;
          make_pair[L][i]++;
        }
      }
    } else {
      mod_mp[v].resize(m_primes.size());
      build(2 * v + 1, L, (L + R) / 2, a);
      build(2 * v + 2, (L + R) / 2, R, a);
      update(v, L, R);
    }
  }
  void mul(int v, int L, int R, int l, int r, int x, const vector<int>& xmp) {
    if (R <= l || r <= L) {
      return;
    } else if (l <= L && R <= r) {
      change_v(v, L, R, x, xmp);
    } else {
      push(v, L, R);
      mul(2 * v + 1, L, (L + R) / 2, l, r, x, xmp);
      mul(2 * v + 2, (L + R) / 2, R, l, r, x, xmp);
      update(v, L, R);
    }
  }
  void div(int v, int L, int R, int i, int x, const vector<int>& xmp) {
    if (R <= i || i < L) {
      return;
    } else if (L == R - 1) {
      for (int j = 0; j < (int)(m_primes.size()); j++) {
        make_pair[L][j] -= xmp[j];
      }
      t[v] = (t[v] * fpow(x, mphi - 1, m)) % m;
    } else {
      push(v, L, R);
      div(2 * v + 1, L, (L + R) / 2, i, x, xmp);
      div(2 * v + 2, (L + R) / 2, R, i, x, xmp);
      update(v, L, R);
    }
  }
  int get_sum(int v, int L, int R, int l, int r) {
    if (R <= l || r <= L) {
      return 0;
    } else if (l <= L && R <= r) {
      return get_sum(v, L, R);
    } else {
      push(v, L, R);
      return (get_sum(2 * v + 1, L, (L + R) / 2, l, r) +
              get_sum(2 * v + 2, (L + R) / 2, R, l, r)) %
             m;
    }
  }
  vector<int> x_to_xmp(int& x) {
    vector<int> ans(m_primes.size());
    for (int i = 0; i < (int)(m_primes.size()); i++) {
      while (x % m_primes[i] == 0) {
        ans[i]++;
        x /= m_primes[i];
      }
    }
    return ans;
  }

 public:
  segment_tree(const vector<int>& a, int md)
      : n(a.size()),
        m(md),
        mphi(phi(m)),
        m_primes(primes(m)),
        pp(m_primes.size()),
        t(4 * n),
        make_pair(n),
        mod(4 * n),
        mod_mp(4 * n) {
    for (int i = 0; i < (int)(m_primes.size()); i++) {
      pp[i][0] = 1;
      for (int j = (int)(1); j < (int)(max_pow); j++) {
        pp[i][j] = (1ll * pp[i][j - 1] * m_primes[i]) % m;
      }
    }
    build(0, 0, n, a);
  }
  void mul(int l, int r, int x) {
    vector<int> xmp = x_to_xmp(x);
    mul(0, 0, n, l, r, x, xmp);
  }
  void div(int i, int x) {
    vector<int> xmp = x_to_xmp(x);
    div(0, 0, n, i, x, xmp);
  }
  int get_sum(int l, int r) { return get_sum(0, 0, n, l, r); }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for (int i = 0; i < (int)(n); i++) cin >> a[i];
  segment_tree st(a, m);
  int q;
  cin >> q;
  for (int i = 0; i < (int)(q); i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      l--;
      st.mul(l, r, x);
    } else if (type == 2) {
      int j, x;
      cin >> j >> x;
      j--;
      st.div(j, x);
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      cout << st.get_sum(l, r) << endl;
    }
  }
  return 0;
}
