#include <bits/stdc++.h>
using namespace std;
long long rdtsc() {
  long long tmp;
  asm("rdtsc" : "=A"(tmp));
  return tmp;
}
inline int myrand() { return abs((rand() << 15) ^ rand()); }
inline int rnd(int x) { return myrand() % x; }
const int MOD = 95542721;
inline int mult(int x, int y) { return (long long)x * y % MOD; }
inline int sum(int x, int y) {
  int res = x + y;
  return res >= MOD ? res - MOD : res;
}
const int maxCnt = 48;
struct State {
  int a[maxCnt];
  int shift;
  State() {}
  State(int value) : shift(0) {
    a[0] = value % MOD;
    int cnt = 0;
    for (int i = 1; i <= maxCnt; ++i) {
      int value = mult(mult(a[i - 1], a[i - 1]), a[i - 1]);
      if (value == a[0]) {
        cnt = i;
        break;
      }
      assert(i < maxCnt);
      a[i] = value;
    }
    assert(!(maxCnt % cnt));
    for (int i = cnt; i < maxCnt; ++i) a[i] = a[i - cnt];
  }
  void update(const State &left, const State &right) {
    shift = 0;
    for (int i = 0; i < maxCnt; ++i) a[i] = sum(left.a[i], right.a[i]);
  }
  void addShift(int toadd) {
    rotate(a, a + toadd, a + maxCnt);
    shift += toadd;
    if (shift >= maxCnt) shift -= maxCnt;
  }
};
struct SegmTree {
  const static int maxn = (1 << 17);
  State a[2 * maxn];
  int n;
  void build(int _n, int *_a) {
    for (n = 1; n < _n; n <<= 1)
      ;
    for (int i = 0; i < n; ++i) a[i + n] = State(i < _n ? _a[i] : 0);
    for (int i = n - 1; i; --i) a[i].update(a[2 * i], a[2 * i + 1]);
  }
  void push(int v) {
    for (int it = 0; it < 2; ++it) {
      int u = 2 * v + it;
      a[u].addShift(a[v].shift);
    }
    a[v].shift = 0;
  }
  void shift(int v, int l, int r, int l0, int r0, int toadd) {
    if (l >= r0 || l0 >= r) return;
    if (l0 <= l && r <= r0) {
      a[v].addShift(toadd);
      return;
    }
    push(v);
    int m = (l + r) / 2;
    shift(2 * v, l, m, l0, r0, toadd);
    shift(2 * v + 1, m, r, l0, r0, toadd);
    a[v].update(a[2 * v], a[2 * v + 1]);
  }
  void shift(int l, int r, int toadd) { shift(1, 0, n, l, r, toadd); }
  int get(int v, int l, int r, int l0, int r0) {
    if (l >= r0 || l0 >= r) return 0;
    if (l0 <= l && r <= r0) {
      return a[v].a[0];
    }
    push(v);
    int m = (l + r) / 2;
    return sum(get(2 * v, l, m, l0, r0), get(2 * v + 1, m, r, l0, r0));
  }
  int get(int l, int r) { return get(1, 0, n, l, r); }
} s;
const int maxn = (int)1e5 + 10;
int a[maxn];
bool solve() {
  int n;
  if (scanf("%d", &n) < 1) return 0;
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  s.build(n, a);
  int q;
  scanf("%d", &q);
  for (int iter = 0; iter < q; ++iter) {
    int type, l, r;
    scanf("%d%d%d", &type, &l, &r);
    --l;
    if (type == 1) {
      printf("%d\n", s.get(l, r));
      continue;
    }
    if (type == 2) {
      s.shift(l, r, 1);
      continue;
    }
  }
  return 1;
}
int main() {
  srand(rdtsc());
  while (1) {
    if (!solve()) break;
  }
  return 0;
}
