#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 95542721;
int n, q, a[N];
int tree[50][N << 2];
int ptr[N << 2];
int laz[N << 2];
int get(int x) {
  int father = x;
  int cnt = 0;
  do {
    cnt++;
    x = x * 1ll * x % mod * 1ll * x % mod;
  } while (x != father);
  return cnt;
}
void build(int idx, int node, int s, int e) {
  if (s == e) {
    tree[idx][node] = a[s];
    return;
  }
  int md = (s + e) >> 1;
  build(idx, node << 1, s, md);
  build(idx, node << 1 | 1, md + 1, e);
  tree[idx][node] = tree[idx][node << 1] + tree[idx][node << 1 | 1];
  if (tree[idx][node] >= mod) tree[idx][node] -= mod;
}
void push(int node, int s, int e) {
  if (!laz[node]) return;
  ptr[node] += laz[node];
  if (ptr[node] >= 48) ptr[node] -= 48;
  if (s != e) {
    laz[node << 1] += laz[node], laz[node << 1 | 1] += laz[node];
    if (laz[node << 1] >= 48) laz[node << 1] -= 48;
    if (laz[node << 1 | 1] >= 48) laz[node << 1 | 1] -= 48;
  }
  laz[node] = 0;
}
void upd(int node, int s, int e, int l, int r) {
  push(node, s, e);
  if (r < s || e < l) return;
  if (l <= s && e <= r) {
    laz[node]++;
    if (laz[node] >= 48) laz[node] -= 48;
    push(node, s, e);
    return;
  }
  int md = (s + e) >> 1;
  upd(node << 1, s, md, l, r);
  upd(node << 1 | 1, md + 1, e, l, r);
  for (int i = 0; i < 48; i++) {
    int x = i + ptr[node];
    if (x >= 48) x -= 48;
    int y = i + ptr[node << 1], z = i + ptr[node << 1 | 1];
    if (y >= 48) y -= 48;
    if (z >= 48) z -= 48;
    tree[x][node] = tree[y][node << 1] + tree[z][node << 1 | 1];
    if (tree[x][node] >= mod) tree[x][node] -= mod;
  }
}
int qry(int node, int s, int e, int l, int r) {
  push(node, s, e);
  if (r < s || e < l) return 0;
  if (l <= s && e <= r) return tree[ptr[node]][node];
  int md = s + e >> 1;
  int x = qry(node << 1, s, md, l, r);
  x += qry(node << 1 | 1, md + 1, e, l, r);
  if (x >= mod) x -= mod;
  return x;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", a + i), a[i] %= mod;
  for (int j = 0; j < 48; j++) {
    build(j, 1, 0, n - 1);
    for (int i = 0; i < n; i++) {
      a[i] = a[i] * 1ll * a[i] % mod * 1ll * a[i] % mod;
    }
  }
  scanf("%d", &q);
  while (q--) {
    int tp, l, r;
    scanf("%d%d%d", &tp, &l, &r);
    --l, --r;
    if (tp == 1) {
      printf("%d\n", qry(1, 0, n - 1, l, r));
    } else {
      upd(1, 0, n - 1, l, r);
    }
  }
  return 0;
}
