#include <bits/stdc++.h>
using namespace std;
struct arr {
  int l, r, add, cnt, sum[50];
} a[110005 * 4];
int data[110005], i, n, m, opt, L, R;
const int P = 95542721;
inline int calc(int x) {
  while (x > 47) x -= 48;
  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);
}
inline void up(int k) {
  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;
}
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];
    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]) % 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;
  up(k);
}
int Query(int k) {
  if (L <= a[k].l && a[k].r <= R) return a[k].sum[calc(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))) %= P;
  return res;
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &data[i]);
  build(1, 1, n);
  scanf("%d", &m);
  while (m--) {
    scanf("%d%d%d", &opt, &L, &R);
    if (opt == 1)
      printf("%d\n", Query(1));
    else
      update(1);
  }
  return 0;
}
