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