#include <cstdio>
#include <cctype>

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> void read(T& x) {
  x = read<T>();
}

template <typename T, typename ...Others> void read(T& x, Others& ...y) {
  read(x);
  read(y...);
}

void read(char* x) {
  char ch = getchar();
  for (; isspace(ch); ch = getchar());
  for (; !isspace(ch); ch = getchar()) *x++ = ch;
  *x = 0;
}

void write(__int128 x) {
  if (x < 0) x = -x, putchar('-');
  int sta[64], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
}

template <typename T> void write(T x) {
  write((__int128)x);
}

void write(char x) {
  putchar(x);
}

void write(char* x) {
  while (*x) putchar(*x++);
}

void write(const char* x) {
  while (*x) putchar(*x++);
}

template <typename T, typename ...Others> void write(T x, Others ...y) {
  write(x);
  write(y...);
}

#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 10;

int n, m;
ll a[MAXN];

int main() {
  freopen("kdl.in", "r", stdin);
  freopen("kdl.out", "w", stdout);
  read(n, m);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  for (int op, l, r, x, y; m--; ) {
    read(op);
    if (op == 1) {
      read(l, r, x);
      if (l > r) l ^= r ^= l ^= r;
      for (int i = l; i <= r; ++i) a[i] += x;
    } else if (op == 2) {
      read(l, r, x);
      if (l > r) l ^= r ^= l ^= r;
      for (int i = l; i <= r; ++i) a[i] = x;
    } else if (op == 3) {
      read(l, r, x);
      if (l > r) l ^= r ^= l ^= r;
      function <ll(int, int, int)> work = [](int l, int r, int x) -> ll {
        vector<ll> v; v.reserve(l - r + 1);
        for (int i = l; i <= r; ++i) v.push_back(a[i]);
        sort(v.begin(), v.end());
        return v[x - 1];
      };
      write(work(l, r, x), '\n');
    } else if (op == 4) {
      read(l, r, x, y);
      if (l > r) l ^= r ^= l ^= r;
      function <ll(int, int, ll, ll)> work = [](int l, int r, ll x, ll y) -> ll {
        function <ll(ll, ll, ll)> kasumi = [](ll x, ll y, ll mod) -> ll {
          ll res = 1;
          while (y) {
            if (y & 1) res = res * x % mod;
            y >>= 1;
            x = x * x % mod;
          }
          return res;
        };
        ll res = 0;
        for (int i = l; i <= r; ++i) {
          res = (res + kasumi(a[i], x, y)) % y;
        }
        return res;
      };
      write(work(l, r, x, y), '\n');
    }
  }
  return 0;
}