#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
const int mod = 95542721, magic = 48;
int inf = 1e9;
int tr[4 * N][magic], lz[4 * N];
int a[N];
void build(int cn, int b, int e) {
  if (b == e) {
    int x = a[b];
    for (int i = 0; i < magic; i++) {
      tr[cn][i] = x;
      int y = 1ll * x * x % mod;
      y = 1ll * y * x % mod;
      x = y;
    }
    return;
  }
  int lc = cn << 1, rc = lc | 1, mid = b + e >> 1;
  build(lc, b, mid);
  build(rc, mid + 1, e);
  for (int i = 0; i < magic; i++) tr[cn][i] = (tr[lc][i] + tr[rc][i]) % mod;
}
void propagate(int u, int st, int en) {
  if (!lz[u]) return;
  if (st != en) {
    lz[2 * u] += lz[u];
    lz[2 * u] %= magic;
    lz[2 * u + 1] += lz[u];
    lz[2 * u + 1] %= magic;
  }
  int tmp[magic];
  for (int i = 0; i < magic; i++) tmp[i] = tr[u][(i + lz[u]) % magic];
  for (int i = 0; i < magic; i++) tr[u][i] = tmp[i];
  lz[u] = 0;
}
void update(int u, int st, int en, int l, int r) {
  propagate(u, st, en);
  if (r < st || en < l)
    return;
  else if (l <= st && en <= r) {
    lz[u]++;
    lz[u] %= magic;
    propagate(u, st, en);
  } else {
    int mid = (st + en) / 2;
    update(2 * u, st, mid, l, r);
    update(2 * u + 1, mid + 1, en, l, r);
    for (int i = 0; i < magic; i++)
      tr[u][i] = (tr[u << 1][i] + tr[(u << 1) | 1][i]) % mod;
  }
}
int query(int u, int st, int en, int l, int r) {
  propagate(u, st, en);
  if (r < st || en < l)
    return 0;
  else if (l <= st && en <= r)
    return tr[u][0];
  else {
    int mid = (st + en) / 2;
    return (query(2 * u, st, mid, l, r) + query(2 * u + 1, mid + 1, en, l, r)) %
           mod;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(1, 1, n);
  cin >> q;
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 2)
      update(1, 1, n, l, r);
    else
      cout << query(1, 1, n, l, r) << "\n";
  }
}
