#include <cstdio>
typedef long long ll;

const int MAXN = 5e5 + 10;

int n, m;
ll a[MAXN];

ll kasumi(ll x, ll y, ll p) {
  ll res = 1;
  while (y) {
    if (y & 1) res = res * x % p;
    y >>= 1;
    x = x * x % p;
  }
  return res;
}

ll kakasumi(int l, int r, ll p) {
  if (l == r) return a[l] % p;
  return kasumi(a[l], kakasumi(l + 1, r, p), p);
}

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("sjjgt.in", "r", stdin);
    freopen("sjjgt.out", "w", stdout);
  #endif

  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
  }

  while (m--) {
    int op, l, r; ll x, p;
    scanf("%d %d %d", &op, &l, &r);
    if (op == 1) {
      scanf("%lld", &x);
      for (int i = l; i <= r; ++i) a[i] += x;
    } else {
      scanf("%lld", &p);
      printf("%lld\n", kakasumi(l, r, p));
    }
  }
  return 0;
}