#include <bits/stdc++.h>
const int N = (int)1e5 + 228;
const int K = (int)48;
const int MOD = (int)95542721;
using namespace std;
int n, a[N], q;
long long t[N * 4][K], b[K], keep[N * 4];
void sift(int v, int k) {
  for (int i = 0; i < K; i++) {
    int j = (i + k) % K;
    b[i] = t[v][j];
  }
  for (int i = 0; i < K; i++) t[v][i] = b[i];
  return;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    t[v][0] = a[tl] % MOD;
    for (int i = 1; i < K; i++) {
      t[v][i] = t[v][i - 1] * t[v][i - 1] % MOD * t[v][i - 1] % MOD;
    }
    return;
  }
  int mid = (tl + tr) / 2;
  build(v * 2, tl, mid);
  build(v * 2 + 1, mid + 1, tr);
  for (int i = 0; i < K; i++) t[v][i] = (t[v * 2][i] + t[v * 2 + 1][i]) % MOD;
}
void push(int v) {
  keep[v] %= K;
  sift(v * 2, keep[v]);
  sift(v * 2 + 1, keep[v]);
  keep[v * 2] += keep[v];
  keep[v * 2 + 1] += keep[v];
  keep[v] = 0;
}
void upd(int l, int r, int v, int tl, int tr) {
  if (tl > r || tr < l) return;
  if (tl >= l && tr <= r) {
    sift(v, 1);
    keep[v]++;
    return;
  }
  push(v);
  int mid = (tl + tr) / 2;
  upd(l, r, v * 2, tl, mid);
  upd(l, r, v * 2 + 1, mid + 1, tr);
  for (int i = 0; i < K; i++) t[v][i] = (t[v * 2][i] + t[v * 2 + 1][i]) % MOD;
}
long long get(int l, int r, int v, int tl, int tr) {
  if (tl > r || tr < l) return 0ll;
  if (tl >= l && tr <= r) return t[v][0];
  push(v);
  int mid = (tl + tr) / 2;
  return (get(l, r, v * 2, tl, mid) + get(l, r, v * 2 + 1, mid + 1, tr)) % MOD;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  scanf("%d", &q);
  build(1, 1, n);
  for (int i = 1; i <= q; i++) {
    int type;
    scanf("%d", &type);
    int l, r;
    scanf("%d%d", &l, &r);
    if (type == 1) {
      printf("%lld\n", get(l, r, 1, 1, n));
    } else {
      upd(l, r, 1, 1, n);
    }
  }
  return 0;
}
