#include <bits/stdc++.h>
using namespace std;
const int MOD = 95542721;
const int N = 262144;
const int MAS = 48;
int tree[N][MAS], push[N], cur[N], a[N];
void update(int &x, const int &mod) {
  if (x >= mod) {
    x -= mod;
  }
}
void merge(int i) {
  int i1 = cur[i * 2];
  int i2 = cur[i * 2 + 1];
  for (int ps = 0; ps < MAS; ps++) {
    tree[i][ps] = tree[i * 2][i1] + tree[i * 2 + 1][i2];
    update(tree[i][ps], MOD);
    i1++;
    update(i1, MAS);
    i2++;
    update(i2, MAS);
  }
  cur[i] = 0;
}
void build(int i, int l, int r) {
  if (l == r) {
    cur[i] = 0;
    tree[i][0] = a[l];
    for (int ps = 1; ps < MAS; ps++) {
      tree[i][ps] =
          1LL * tree[i][ps - 1] * tree[i][ps - 1] % MOD * tree[i][ps - 1] % MOD;
    }
    return;
  }
  int m = (l + r) / 2;
  build(i * 2, l, m);
  build(i * 2 + 1, m + 1, r);
  merge(i);
}
void make_push(int i) {
  if (push[i] == 0) {
    return;
  }
  cur[i * 2] += push[i];
  update(cur[i * 2], MAS);
  cur[i * 2 + 1] += push[i];
  update(cur[i * 2 + 1], MAS);
  push[i * 2] += push[i];
  update(push[i * 2], MAS);
  push[i * 2 + 1] += push[i];
  update(push[i * 2 + 1], MAS);
  push[i] = 0;
}
void modify(int i, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    cur[i]++;
    update(cur[i], MAS);
    push[i]++;
    update(push[i], MAS);
    return;
  }
  make_push(i);
  int m = (l + r) / 2;
  if (ql <= m) {
    modify(i * 2, l, m, ql, min(qr, m));
  }
  if (m < qr) {
    modify(i * 2 + 1, m + 1, r, max(ql, m + 1), qr);
  }
  merge(i);
}
int get(int i, int l, int r, int ql, int qr) {
  if (l == ql && r == qr) {
    return tree[i][cur[i]];
  }
  make_push(i);
  int m = (l + r) / 2;
  int res = 0;
  if (ql <= m) {
    res += get(i * 2, l, m, ql, min(qr, m));
  }
  if (m < qr) {
    res += get(i * 2 + 1, m + 1, r, max(ql, m + 1), qr);
  }
  update(res, MOD);
  return res;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i] %= MOD;
  }
  build(1, 1, n);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int type, l, r;
    scanf("%d %d %d", &type, &l, &r);
    if (type == 1) {
      printf("%d\n", get(1, 1, n, l, r));
    } else {
      modify(1, 1, n, l, r);
    }
  }
  return 0;
}
