#include <bits/stdc++.h>
const int mo = 95542721;
const int maxn = 100010;
const int T = 48;
const int maxtreetop = 270000;
struct Ttree {
  int start, stop;
  int tag;
  int a[T];
} tree[maxtreetop + 1];
int n;
int a[maxn + 1];
int result;
void init() {
  int i;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
}
void putdown(int p) {
  int l, r;
  l = p * 2;
  r = l + 1;
  tree[l].tag = (tree[l].tag + tree[p].tag) % T;
  tree[r].tag = (tree[r].tag + tree[p].tag) % T;
  tree[p].tag = 0;
}
void upload(int p) {
  int l, r, t1, t2, i;
  l = p * 2;
  r = l + 1;
  t1 = tree[l].tag;
  t2 = tree[r].tag;
  tree[p].tag = 0;
  for (i = 0; i < T; ++i) {
    tree[p].a[i] = tree[l].a[t1] + tree[r].a[t2];
    if (tree[p].a[i] >= mo) tree[p].a[i] -= mo;
    ++t1;
    if (t1 >= T) t1 = 0;
    ++t2;
    if (t2 >= T) t2 = 0;
  }
}
void init_tree(int p, int start, int stop) {
  tree[p].start = start;
  tree[p].stop = stop;
  tree[p].tag = 0;
  if (start < stop) {
    int mid = (start + stop) / 2;
    init_tree(p * 2, start, mid);
    init_tree(p * 2 + 1, mid + 1, stop);
    upload(p);
  } else {
    tree[p].a[0] = a[start] % mo;
    int i;
    long long t;
    for (i = 1; i < T; ++i) {
      t = tree[p].a[i - 1];
      t = (t * tree[p].a[i - 1]) % mo;
      t = (t * tree[p].a[i - 1]) % mo;
      tree[p].a[i] = t;
    }
  }
}
void ask_tree(int p, int start, int stop) {
  if ((start <= tree[p].start) && (stop >= tree[p].stop)) {
    result += tree[p].a[tree[p].tag];
    if (result >= mo) result -= mo;
    return;
  }
  putdown(p);
  int mid = (tree[p].start + tree[p].stop) / 2;
  if (start <= mid) ask_tree(p * 2, start, stop);
  if (stop > mid) ask_tree(p * 2 + 1, start, stop);
  upload(p);
}
void modify_tree(int p, int start, int stop) {
  if ((start <= tree[p].start) && (stop >= tree[p].stop)) {
    ++tree[p].tag;
    if (tree[p].tag >= T) tree[p].tag = 0;
    return;
  }
  putdown(p);
  int mid = (tree[p].start + tree[p].stop) / 2;
  if (start <= mid) modify_tree(p * 2, start, stop);
  if (stop > mid) modify_tree(p * 2 + 1, start, stop);
  upload(p);
}
void work() {
  int q, i, t, l, r;
  init_tree(1, 1, n);
  scanf("%d", &q);
  for (i = 1; i <= q; ++i) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      result = 0;
      ask_tree(1, l, r);
      printf("%d\n", result);
    } else
      modify_tree(1, l, r);
  }
}
int main() {
  init();
  work();
  return 0;
}
