#include <bits/stdc++.h>
using namespace std;
const int mo = 95542721;
const int maxn = 110000;
int n, Q;
int a[maxn];
int t, xx, yy;
inline long long mod(long long a, int mo) {
  if (a >= mo) a -= mo;
  return a;
}
long long tr[maxn * 3][48];
int ro[maxn * 3];
int x, y;
long long res, c;
void in(int p, int l, int r) {
  if (r < x || l > y) return;
  if (x <= l && r <= y) {
    ro[p]++;
    if (ro[p] >= 48) ro[p] -= 48;
    return;
  }
  int mid = (l + r) >> 1;
  in(p << 1, l, mid);
  in((p << 1) + 1, mid + 1, r);
  for (int i = 0; i < 48; i++)
    tr[p][i] = mod(tr[p << 1][mod(i + ro[p << 1], 48)] +
                       tr[(p << 1) + 1][mod(i + ro[(p << 1) + 1], 48)],
                   mo);
}
void insert(int _x, int _y) {
  x = _x;
  y = _y;
  in(1, 1, n);
}
void build(int p, int l, int r) {
  if (l == r) {
    tr[p][0] = a[l];
    for (int i = 1; i < 48; i++)
      tr[p][i] = tr[p][i - 1] * tr[p][i - 1] % mo * tr[p][i - 1] % mo;
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build((p << 1) + 1, mid + 1, r);
  for (int i = 0; i < 48; i++)
    tr[p][i] = mod(tr[p << 1][i] + tr[(p << 1) + 1][i], mo);
}
void q(int p, int l, int r, int t) {
  if (r < x || l > y) return;
  if (x <= l && r <= y) {
    res += tr[p][mod(t + ro[p], 48)];
    if (res >= mo) res = res % mo;
    return;
  }
  int mid = (l + r) >> 1;
  q(p << 1, l, mid, mod(t + ro[p], 48));
  q((p << 1) + 1, mid + 1, r, mod(t + ro[p], 48));
}
long long query(int _x, int _y) {
  x = _x;
  y = _y;
  res = 0;
  q(1, 1, n, 0);
  return res;
}
int main() {
  cin >> n;
  for (register int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  build(1, 1, n);
  cin >> Q;
  for (register int t = 1; t <= Q; t++) {
    scanf("%d%d%d", &t, &xx, &yy);
    if (t == 1)
      printf("%I64d\n", query(xx, yy));
    else {
      insert(xx, yy);
    }
  }
}
