#include <bits/stdc++.h>
using namespace std;
const int mod = 95542721, N = 1e5 + 10, inf = 0x3f3f3f3f;
int n, Q;
int a[N << 2][50], tag[N << 2];
void dopsd(int x, int v) {
  tag[x] += v;
  rotate(a[x], a[x] + v, a[x] + 48);
}
void psd(int x) {
  tag[x] %= 48;
  if (tag[x]) {
    dopsd(x << 1, tag[x]), dopsd(x << 1 | 1, tag[x]);
    tag[x] = 0;
  }
}
void upd(int x) {
  for (int i = 0; i <= 47; i++) {
    a[x][i] = (a[x << 1][i] + a[x << 1 | 1][i]) % mod;
  }
}
void build(int x, int l, int r) {
  if (l == r) {
    long long val;
    scanf("%lld", &val);
    a[x][0] = val;
    for (int i = 1; i <= 47; i++)
      a[x][i] = 1ll * a[x][i - 1] * a[x][i - 1] % mod * a[x][i - 1] % mod;
    return;
  }
  int mid = (l + r) >> 1;
  build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  upd(x);
}
long long query(int x, int l, int r, int lx, int rx) {
  if (lx <= l && r <= rx) return a[x][0];
  psd(x);
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (lx <= mid) ret = query(x << 1, l, mid, lx, rx);
  if (rx > mid) (ret += query(x << 1 | 1, mid + 1, r, lx, rx)) %= mod;
  return ret;
}
void modify(int x, int l, int r, int lx, int rx) {
  if (lx <= l && r <= rx) {
    tag[x]++;
    rotate(a[x], a[x] + 1, a[x] + 48);
    return;
  }
  psd(x);
  int mid = (l + r) >> 1;
  if (lx <= mid) modify(x << 1, l, mid, lx, rx);
  if (rx > mid) modify(x << 1 | 1, mid + 1, r, lx, rx);
  upd(x);
}
int main() {
  cin >> n;
  build(1, 1, n);
  cin >> Q;
  while (Q--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      printf("%lld\n", query(1, 1, n, l, r));
    } else {
      modify(1, 1, n, l, r);
    }
  }
  return 0;
}
