#include <bits/stdc++.h>
using namespace std;
int p;
inline int add(int x, int y) {
  x += y;
  if (x >= p) {
    x -= p;
  }
  return x;
}
pair<int, int> ex_gcd(int a, int b) {
  if (!b) {
    return make_pair(1, 0);
  } else {
    auto res = ex_gcd(b, a % b);
    return make_pair(res.second, res.first - (a / b) * res.second);
  }
};
int inverse(int value) {
  auto res = ex_gcd(value, p);
  return (res.first + p) % p;
}
int qpow(int a, int n) {
  int res = 1;
  for (; n; n >>= 1, a = (long long)a * a % p) {
    if (n & 1) {
      res = (long long)res * a % p;
    }
  }
  return res;
}
vector<int> divisor;
int pow_d[12][2234567];
struct number {
  vector<int> power;
  int value;
  number() {
    power.resize(divisor.size());
    value = 1;
  }
  number(int n) {
    power.resize(divisor.size());
    for (int i = 0; i < divisor.size(); i++) {
      while (!(n % divisor[i])) {
        power[i]++;
        n /= divisor[i];
      }
    }
    value = n % p;
  }
  void operator*=(number a) {
    for (int i = 0; i < power.size(); i++) {
      power[i] += a.power[i];
    }
    value = (long long)value * a.value % p;
  }
  void operator/=(number a) {
    for (int i = 0; i < power.size(); i++) {
      power[i] -= a.power[i];
    }
    value = (long long)value * inverse(a.value) % p;
  }
  int calculate() {
    int res = value;
    for (int i = 0; i < divisor.size(); i++) {
      res = (long long)res * pow_d[i][power[i]] % p;
    }
    return res;
  }
} segment_tree[234567];
int sum[234567], tag_val[234567];
void add_tag(int u, number value, int val_int) {
  segment_tree[u] *= value;
  sum[u] = (long long)sum[u] * val_int % p;
  tag_val[u] = (long long)tag_val[u] * val_int % p;
};
void pull(int u, int l, int r) {
  int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
  sum[u] = add(sum[x], sum[y]);
};
void push(int u, int l, int r) {
  bool empty = tag_val[u] == 1 && segment_tree[u].value == 1;
  for (int i = 0; i < divisor.size(); i++) {
    if (segment_tree[u].power[i]) {
      empty = false;
    }
  }
  if (!empty) {
    int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
    add_tag(x, segment_tree[u], tag_val[u]);
    add_tag(y, segment_tree[u], tag_val[u]);
    segment_tree[u].value = tag_val[u] = 1;
    for (int i = 0; i < divisor.size(); i++) {
      segment_tree[u].power[i] = 0;
    }
  }
};
void build(int u, int l, int r, vector<int> &arr) {
  if (l == r) {
    segment_tree[u] = arr[l];
    sum[u] = arr[l] % p;
  } else {
    int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
    build(x, l, mid, arr);
    build(y, mid + 1, r, arr);
    pull(u, l, r);
  }
};
void modify_mul(int u, int l, int r, int ql, int qr, int value) {
  if (ql == l && qr == r) {
    add_tag(u, value, value);
  } else {
    push(u, l, r);
    int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
    if (qr <= mid) {
      modify_mul(x, l, mid, ql, qr, value);
    } else if (mid < ql) {
      modify_mul(y, mid + 1, r, ql, qr, value);
    } else {
      modify_mul(x, l, mid, ql, mid, value);
      modify_mul(y, mid + 1, r, mid + 1, qr, value);
    }
    pull(u, l, r);
  }
};
void modify_div(int u, int l, int r, int pos, int value) {
  if (l == r) {
    segment_tree[u] /= value;
    sum[u] = segment_tree[u].calculate();
  } else {
    push(u, l, r);
    int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
    if (pos <= mid) {
      modify_div(x, l, mid, pos, value);
    } else {
      modify_div(y, mid + 1, r, pos, value);
    }
    pull(u, l, r);
  }
};
int query(int u, int l, int r, int ql, int qr) {
  if (ql == l && qr == r) {
    return sum[u];
  } else {
    push(u, l, r);
    int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
    if (qr <= mid) {
      return query(x, l, mid, ql, qr);
    } else if (mid < ql) {
      return query(y, mid + 1, r, ql, qr);
    } else {
      return add(query(x, l, mid, ql, mid), query(y, mid + 1, r, mid + 1, qr));
    }
  }
};
int main() {
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n;
  cin >> n >> p;
  auto decompose = [&](int value) {
    for (int i = 2; i * i <= value; i++) {
      if (!(value % i)) {
        divisor.push_back(i);
        while (!(value % i)) {
          value /= i;
        }
      }
    }
    if (value != 1) {
      divisor.push_back(value);
    }
  };
  decompose(p);
  for (int i = 0; i < divisor.size(); i++) {
    pow_d[i][0] = 1;
    for (int j = 1; j < 2234567; j++) {
      pow_d[i][j] = (long long)pow_d[i][j - 1] * divisor[i] % p;
    }
  }
  for (int i = 0; i < n * 2; i++) {
    segment_tree[i] = 1;
    tag_val[i] = 1;
  }
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  build(0, 0, n - 1, arr);
  int q;
  cin >> q;
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      modify_mul(0, 0, n - 1, --l, --r, x);
    } else if (type == 2) {
      int pos, x;
      cin >> pos >> x;
      modify_div(0, 0, n - 1, --pos, x);
    } else {
      int l, r;
      cin >> l >> r;
      cout << query(0, 0, n - 1, --l, --r) << "\n";
    }
  }
  return 0;
}
