#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 111111;
int s[MAX_N << 2][48], tg[MAX_N << 2], d2[MAX_N << 2], d[MAX_N << 2];
int n;
int a[MAX_N];
inline int rd(int x) { return x >= 48 ? x - 48 : x; }
int cb(long long x) { return x * x % 95542721 * x % 95542721; }
void upd(int x) {
  for (int i = 0; i <= 47; ++i) {
    s[x][i] = s[(x << 1)][rd(i + d2[(x << 1)])] +
              s[((x << 1) + 1)][rd(i + d2[((x << 1) + 1)])];
    if (s[x][i] >= 95542721) s[x][i] -= 95542721;
  }
}
void build(int x, int l, int r) {
  if (l == r) {
    s[x][0] = a[l];
    for (int i = 1; i <= 47; ++i) s[x][i] = cb(s[x][i - 1]);
    return;
  }
  int mid = (l + r) >> 1;
  build((x << 1), l, mid);
  build(((x << 1) + 1), mid + 1, r);
  upd(x);
}
void push(int x) {
  if (tg[x]) {
    d[(x << 1)] = rd(d[(x << 1)] + tg[x]);
    tg[(x << 1)] = rd(tg[(x << 1)] + tg[x]);
    d[((x << 1) + 1)] = rd(d[((x << 1) + 1)] + tg[x]);
    tg[((x << 1) + 1)] = rd(tg[((x << 1) + 1)] + tg[x]);
    tg[x] = 0;
  }
}
int query(int x, int l, int r, int f, int t) {
  if (l < r) push(x);
  if (f <= l && r <= t) return s[x][d[x]];
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (f <= mid) ret += query((x << 1), l, mid, f, t);
  if (t > mid) ret += query(((x << 1) + 1), mid + 1, r, f, t);
  if (ret >= 95542721) ret -= 95542721;
  return ret;
}
void modify(int x, int l, int r, int f, int t) {
  if (l < r) push(x);
  if (f <= l && r <= t) {
    d2[x] = rd(d2[x] + 1);
    d[x] = rd(d[x] + 1);
    tg[x] = rd(tg[x] + 1);
    return;
  }
  int mid = (l + r) >> 1;
  if (f <= mid) modify((x << 1), l, mid, f, t);
  if (t > mid) modify(((x << 1) + 1), mid + 1, r, f, t);
  upd(x);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i] %= 95542721;
  build(1, 1, n);
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1)
      printf("%d\n", query(1, 1, n, l, r));
    else
      modify(1, 1, n, l, r);
  }
}
