#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, m, type, x, y, an;
int tr[100010 * 4][50], d[100010], cov[100010 * 4], b[50];
inline void update(int x) {
  int i, y = x * 2, z = x * 2 + 1;
  for (i = 0; i <= 49; i++) tr[x][i] = (tr[y][i] + tr[z][i]) % 95542721;
}
void build(int q, int x, int y) {
  int mid = (x + y) / 2, i, k;
  if (x == y) {
    tr[q][0] = d[x];
    for (i = 1; i <= 49; i++) {
      k = tr[q][i - 1];
      tr[q][i] = (long long)k * k % 95542721 * k % 95542721;
    }
    return;
  }
  build(q * 2, x, mid);
  build(q * 2 + 1, mid + 1, y);
  update(q);
}
inline void inc(int x, int y) {
  int i;
  cov[x] = (cov[x] + y) % 48;
  for (i = 0; i <= 49; i++) b[i] = tr[x][i];
  for (i = 0; i <= 49; i++) tr[x][i] = b[(i + y) % 48];
}
inline void renew(int x) {
  if (cov[x]) inc(x * 2, cov[x]), inc(x * 2 + 1, cov[x]);
  cov[x] = 0;
}
void work(int q, int x, int y, int l, int r, int t) {
  int mid = (x + y) / 2;
  if (l <= x && y <= r) {
    if (t)
      inc(q, 1);
    else
      an = (an + tr[q][0]) % 95542721;
    return;
  }
  renew(q);
  if (l <= mid) work(q * 2, x, mid, l, r, t);
  if (mid < r) work(q * 2 + 1, mid + 1, y, l, r, t);
  update(q);
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &d[i]);
  build(1, 1, n);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d", &type, &x, &y);
    if (type == 1) {
      an = 0;
      work(1, 1, n, x, y, 0);
      printf("%d\n", an);
    } else
      work(1, 1, n, x, y, 1);
  }
  return 0;
}
