#include <bits/stdc++.h>
using namespace std;
struct arr {
  int l, r, add, cnt, sum[48];
} a[100005 * 3];
int data[100005], i, n, m, opt, L, R;
const int P = 95542721;
inline int calc(int x) {
  while (x > 47) x -= 48;
  return x;
}
inline int Read() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void down(int k) {
  if (!a[k].cnt || a[k].l == a[k].r) return;
  int W = a[k].cnt;
  a[k].cnt = 0;
  a[(k << 1)].add = calc(a[(k << 1)].add + W);
  a[(k << 1)].cnt = calc(a[(k << 1)].cnt + W);
  a[(k << 1 | 1)].add = calc(a[(k << 1 | 1)].add + W);
  a[(k << 1 | 1)].cnt = calc(a[(k << 1 | 1)].cnt + W);
}
void build(int k, int l, int r) {
  a[k].l = l;
  a[k].r = r;
  a[k].add = a[k].cnt = 0;
  if (l == r) {
    a[k].sum[0] = data[l] % P;
    for (int i = 1; i <= 47; i++)
      a[k].sum[i] = (a[k].sum[i - 1] * 1ll * a[k].sum[i - 1] % P * 1ll *
                     a[k].sum[i - 1] % P);
    return;
  }
  int mid = (l + r) >> 1;
  if (l <= mid) build((k << 1), l, mid);
  if (r > mid) build((k << 1 | 1), mid + 1, r);
  for (int i = 0; i < 48; i++) {
    a[k].sum[i] = (a[(k << 1)].sum[i] + a[(k << 1 | 1)].sum[i]);
    if (a[k].sum[i] >= P) a[k].sum[i] -= P;
  }
}
void update(int k) {
  if (L <= a[k].l && a[k].r <= R) {
    a[k].cnt = calc(a[k].cnt + 1);
    a[k].add = calc(a[k].add + 1);
    return;
  }
  down(k);
  int mid = (a[k].l + a[k].r) >> 1;
  if (L <= mid) update((k << 1));
  if (R > mid) update((k << 1 | 1));
  a[k].add = 0;
  for (int i = 0; i < 48; i++)
    a[k].sum[i] = (a[(k << 1)].sum[calc(a[(k << 1)].add + i)] +
                   a[(k << 1 | 1)].sum[calc(a[(k << 1 | 1)].add + i)]) %
                  P;
}
int Query(int k) {
  if (L <= a[k].l && a[k].r <= R) return a[k].sum[a[k].add];
  down(k);
  int res = 0;
  int mid = (a[k].l + a[k].r) >> 1;
  if (L <= mid) res = Query((k << 1));
  if (R > mid) res += Query((k << 1 | 1));
  return res >= P ? res - P : res;
}
int main() {
  n = Read();
  for (i = 1; i <= n; i++) data[i] = Read();
  build(1, 1, n);
  m = Read();
  while (m--) {
    opt = Read();
    L = Read();
    R = Read();
    if (opt == 1)
      printf("%d\n", Query(1));
    else
      update(1);
  }
  return 0;
}
